Stirling numbers

stirling numbers of the second kind are used to determine how many ways an n-set can be partitioned into m non-empty subsets. it goes a little something like this..

                                    m
     0      1      2      3      4      5      6      7      8      9..
   ________________________________________________________________________
  0| 1
  1| 0      1
  2| 0      1      1
  3| 0      1      3      1
  4| 0      1      7      6      1
n 5| 0      1      15     25     10     1
  6| 0      1      31     90     65     15     1
  7| 0      1      63     301    350    140    21     1
  8| 0      1      127    966    1701   1050   266    28     1
  9| 0      1      255    3025   7770   6951   2646   462    36     1
  :|

these numbers are also sometimes represented in a triangle, since half the chart is empty where m > n, that is, where the number of partitions is 0. how do you get these numbers (if, for example, you wanted to fill in row 10)? a general rule for filling in the chart is S(n,m) = (n-1,m-1) + m(n-1,m).

Where does that formula come from?

For simplicity, let the n-set we are partitioning be the set of integers from 1 to n. And now assume we know how many ways there are to partition a set of cardinality n-1 (in other words, we know all the S numbers for n-1).

Every partition of the n-set will either put the number n in a set all by itself, or it will put it in a set with some other numbers as well.

The number of possible partitionings which put n in its own set is equal to the number of partitionings of a set of cardinality n-1 into m-1 non-empty subsets, which is precisely the value S(n-1,m-1).

The number of possible partitionings which put n in a subset with some other numbers can be computed as follows. For any given partitioning of the set of cardinality n-1 into m non-empty subsets, we can insert the number n into any of the m subsets. So we just multiply that number of partitionings, which is S(n-1,m), by m.

So the total number of partitionings of a set of cardinality n into m non-empty subsets is the sum of those two quantities. So the final formula is:

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