2
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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 .

$\endgroup$
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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