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*)