?

Combinatorics

Free Version

Upgrade subject to access all content

Difficult

Stirling Numbers Summation Recurrence II

COMBIN-KLXQLG

Let $S(n,k)$ be the number of ways to partition an $n$ element set with $k$ blocks. Then for $n > 0$:

$$S(n,k) = \sum_{i = 1}^{n}b(i,n,k)S(n-i,k-1)$$

...for some coefficient $b(i,n,k)$. What is $b(i,n,k)$? (Note: $S(n,k) = 0$ if $k > n$.)

A

${k - 1 \choose i - 1}$

B

${n - 1 \choose i - 1}$

C

${n - 1 \choose k-i}$

D

${n - i \choose k-1}$