Explore BrainMass

Recurrence Relations : Stirling Numbers

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

Solution Summary

Recurrence Relations and Stirling Numbers are investigated.