0
$\begingroup$

We know that stirling number second kind, which has the recurrence relation as $f(n, k) = f(n - 1, k - 1) + k \times f(n - 1, k)$, counts the number of ways to put n elements in k non-empty partition.

If every partition contains at least r elements, what would be the recurrence? I'm guessing that would be $$f(n, k) = \binom{n - 1}{r - 1} \times f(n - r, k - 1) + k \times f(n - r, k)$$

Is that right? If there's any other way, please mention that too.

Thanks in advance!

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The second part should be $kf(n-1,k)$ because you are taking one element and placing it in the current $k$ partitions.
This numbers are called Associated Stirling numbers of the second kind.

As an introduction point see https://oeis.org/A008299 when $r=2.$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.