Exercise 0.7

Binomial coefficients count the number of subsets of an n element set having k elements in them. The Stirling number here counts the number of partitions of a set of n elements into k disjoint blocks. Prove these two statements.

Solution:

The subsets of an n element  set of size k are of two kinds.

Those which do not contain the nth element: these are actually k element subsets of an the n-1 element set obtained by ignoring n.

and those that contain n: these all have k-1 elements of the remaining n-1.

This gives the recursion

C(n, k) = C(n-1, k) + C(n-1, k-1)

which is what is computed in the first spreadsheets.

A partition of an n element set into k blocks can also be of either of two kinds. In one the element n is all by itself in a block; and we have a partition of the rest into k-1 blocks.

Otherwise, it comes from a partition of the rest into k blocks, and then it can go into any one of them; so there are k * (the number of partitions of an n-1 element set into k blocks) different ways that this second possibility can happen.

This gives the recursion used in the spreadsheet here, which is

S(n, k) = S(n-1 ,k-1) + k*S(n-1, k)

which can be read as "n stands alone, or with one of the k blocks that exist without it".