MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can someone lead me to a method for calculating the number of sequences of length $n$ if the terms of the sequence are chosen (with replacement) from a set with $k$-elements under the condition that all $k$-elements are chosen at least once? It's not my field.

I lead myself to consider the recurrence relation $$ R(k,n) = k R(k,n-1) + k R(k-1,n-1) $$ where $R(k,k) = k!, R(k,n) = 0$ if $n \lt k$ and $R(1,n) = 1$ for all $n$, but struggled to close it out. Is there a method for this?

$R(n,k)$ is the number I want, so from my point of view I'm asking one question. From your point of view I'm sure I'm asking two. Many Thanks.

share|cite|improve this question
Because you "asked two", you got answers from two, and those two are twin answers. I see this on MO for the 1st time... – Wadim Zudilin Jun 6 '10 at 9:06
up vote 6 down vote accepted

These are related to Stirling numbers. These don't have a "closed form". Your $R(k,n)=k!S(n,k)$ where $S(n,k)$ is the Stirling number of the second kind as defined at .

share|cite|improve this answer
It's funny to see two identical answers. – Wadim Zudilin Jun 6 '10 at 9:04
See – Tom Copeland Sep 9 '15 at 20:27

We have $R(k, n) = k! \cdot S(n, k)$, where $S(n, k)$ is a Stirling number of the second kind:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.