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)