Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

2 Answers

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 http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind .

share|improve this answer
    
It's funny to see two identical answers. –  Wadim Zudilin Jun 6 '10 at 9:04
add comment

We have $R(k, n) = k! \cdot S(n, k)$, where $S(n, k)$ is a Stirling number of the second kind: http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

share|improve this answer
add comment

Your Answer

 
discard

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.