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. 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.Definition: 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:
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: 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.Proof: To conclude we look for an explicit formula for S(n,r). For all positive integers n and r, we have 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).Proof: |