1
$\begingroup$

This question is prefaced by this part:

We use the notation S(k,n) to stand for the number of partitions of a k element set with n blocks. For historical reasons, S(k,n) is called a Stirling Number of the second kind.

Question:

In a partition of the set [k], the number k is either in a block by itself, or it is not. How does the number of partitions of [k] with n parts in which k is in a block with other elements of [k] compare to the number of partitions of [k - 1] into n blocks? Find a two-variable recurrence for S(k,n), valid for k and n larger than one.

So if I understand this correctly the answer will be a proof? Can I reach the answer by enumerating different example partitions of sets? I appreciate any tips and help. Thank you

1 Answers 1

3

The answer will be a recurrence together with an explanation justifying that recurrence. For example, the binomial coefficients satisfy the two-variable recurrence $\binom{k}n=\binom{k-1}{n-1}+\binom{k-1}n\tag{1}$ (which you may recognize as the rule used to form Pascal’s triangle). The Stirling numbers of the second kind, which are also written $\left\{\matrix{k\\n}\right\}$ instead of $S(k,n)$, satisfy a two variable recurrence quite similar to $(1)$, though a little more complicated. One term counts the partitions of $[k]$ in which $\{k\}$ is a block by itself; the other counts the partitions of $[k]$ in which $k$ is in a block with something else.

To get you started, if $\{k\}$ is a block by itself, the remaining $k-1$ elements of $[k]$ must make up the other $n-1$ blocks. There are $S(k-1,n-1)$ ways in which they can do this, so there are how many partitions of $[k]$ in which $\{k\}$ is a block by itself?

  • 0
    @Brian, Thank You Very Much! I'm slowly getting it, but still a bit puzzled(just the concept of Stirling #s itself), so I'll have to read more on wikipedia.2012-02-22