Stirling Numbers of the Second Kind

In set theory, a partition of a set is a distribution of the elements of the set into some number of blocks. Each element of the original set is placed in exactly one of the r blocks, and the order of the distribution does not matter. For example, if we were to look at a distribution of 7 elements into 4 blocks, one such partition would be as follows:

{1,2,7}, {3,4}, {5}, {6}.

This partition is identical to the following:

{1,2,7}, {4,3}, {6}, {5}.

As previously stated, order does not matter when looking at partitions, within or regarding the sets.

Definition:
A Stirling number of the second kind, denoted by S(n,k), is the number of partitions of a set with n elements into k blocks.

We can easily see that S(n,0) = 0 (if n > 0), because there is no way to place a positive number of elements into zero sets. Similarly, S(0,0) = 1.

The first few values of the Stirling numbers of the second kind are shown below:

 n    |    k
 1 2 3 4 5
 1
 1    
 2 1
 1
   
 3 1 3
 1  
 4 1 7
 6 1
 
 5 1 15 
 25
 10 1


We will prove a recurrence relation for the Stirling numbers of the second kind which is very similar to that of the numbers of the first kind:


Proof:
We look at the nth element of the set being partitioned. If n is in its own set, then we have S(n-1,k-1) ways to partition the remaining n-1 elements. If n is in an additional partition, then we merely choose one of the k partitions for every possible set of partitions, which is k*S(n-1,k). Therefore we have what we started with.

To conclude we look for an explicit formula for S(n,r).

For all positive integers n and r, we have


Proof: Finding an ordered partition of n into r blocks is identical to finding an onto function from n into r. To solve this problem, we may use the inclusion-exclusion principle to find all onto functions from n into r. There are r^n ways to assign each of the distinct n elements a block. We then subtract and add (r choose i) * (r-i)^n repeatedly until we have counted all possible onto functions, which is a standard application of the principle of inclusion-exclusion and is exactly what the theorem states. This gives us an explicit formula for S(n,k).

Subpages (1): Sample Problems
Comments