?

Combinatorics

Free Version

Upgrade subject to access all content

Difficult

Stirling Numbers Summation Recurrence I

COMBIN-4RYEXY

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 = 0}^{n-1}a(i,n,k)S(i,k-1)$$

...for some coefficient $a(i,n,k)$.

What is $a(i,n,k)$? (Note: $S(n,k) = 0$ if $k > n$.)

A

${n - 1 \choose i}$

B

${k - 1 \choose i}$

C

${n - k \choose i}$

D

${n - i \choose i}$