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.

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
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 .

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It's funny to see two identical answers. $\endgroup$
    – Wadim Zudilin
    Commented Jun 6, 2010 at 9:04
  • 1
    $\begingroup$ See oeis.org/A019538. $\endgroup$
    – Tom Copeland
    Commented Sep 9, 2015 at 20:27
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .