Question

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.

Answer 1

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 .

Answer 2

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