A Stirling number Snk is definedc as the number of ways of partitioning the set of positive numbers (1,2,3,....n) into k non empty subsets.
We can show that by considering if the singleton subset (n) is a partition or not that Snk = Sn-1, k-1 + kSn-1,k
Another recurrence relation comes from considering the number of partitions that have:
(i) either (n,n-1) or both (n) and (n-1) as subsets
(ii) either (n) or (n-1) but not both as subsets
(iii) none of (n,n-1) (n) (n-1) as subsets
Show this leads to
Snk = Sn-2, k-2 + (2k-1)Sn-2,k-1 + k^2Sn-2,k