On Stirling numbers of the second kind

Finding the number of partitions in a set is an interesting problem. It shows how many ways are there to classify the elements of a finite universe. (A partition corresponds to a collection of subsets whose union is A, they are non-empty and the intersection between any two of them is void) This problem was studied by James Stirling and Eric Bell. In particular, Bell numbers form a sequence

B[i] = { number of partitions for a set with i elements }.

You can restrict the problem to k subsets of an universe of n elements. Be S[n,k] the number of partitions of a set of n elements into k non-empty subsets. The S[n,k] are known as the Stirling numbers of the second kind. In this post, a recurrence for S[n,k] is defined.

Let's say that we have a set A with n elements and we want to divide it between k non empty subsets. We can then take out one element x from A and take it out of the set. We will now have one set with x, and another set with all of the n-1 elements but x. We can now start forming partitions of k elements of A as follows. For each partition of k-1 elements of A-{x}, we can add {x} as an extra set and we have a new partition of A into k subsets. According to the definition of S[n,k], A-{x} will have S[n-1,k-1] such partitions that contain {x} as a set.

 We can then insert back the {x}. For each partition of A-{x} in k subsets, each of those k subsets can be replaced successively by adding x to it, not as the set {x} but as an extra element of the set. So each partition of A-{x} into k, will correspond to k partitions of A into k. Since there are S[n-1,k] partitions of A-{x} into k subsets, there are k*S[n-1, k] partitions of A that don't contain {x} as a set.

 The total partitions will be those that contain {x} as a set plus those that don't contain {x} as a set, or in other words,
S[n,k] = S[n-1, k-1] + kS[n-1, k].

You can now build up a table to organize better those numbers. n can be in the rows and k in the columns. S[n,1] is always 1, because a partition into only one subset is a partition that contains the whole set. S[n,n] is also 1 because there is only one way of partitioning the set of n elements into n non empty disjoint subsets (each subset containing only one element). In any cell of the table, you can calculate the corresponding number by multiplying the upper cell times the column index and adding that to the upper left cell.

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
...

 Finally, we can also obtain the Bell numbers by adding all the elements in a given row, although there is a simpler triangle for calculating Bell numbers directly (See 2).

References

[1] Bell Number, http://en.wikipedia.org/wiki/Bell_number
[2] Stirling Number, http://en.wikipedia.org/wiki/Stirling_number