# Stirling numbers of the second kind identity

• Jul 6th 2010, 09:10 PM
oldguynewstudent
Stirling numbers of the second kind identity
I am understanding this a little better. Could someone let me know if I am on the right track with the following proof?

Give combinatorial proof: n$\displaystyle \geq$1 and k$\displaystyle \geq$1 then

$\displaystyle S(n,k)=\sum_{i=0}^{n-1}\left({n-1\atop i}\right)S(i,k-1)$.

Condition on whether the element n is in a block by itself. If it is, then all such partitions can be constructed by first specifying a (k-1) partition of [n-1] and then adding the block {n}. There are S(n-1,k-1) such partitions.

We can continue the next case by putting n and n-1 into a block by themselves. We construct these partitions by first specifying a (k-1) partition of [n-2] and then adding the block {n,n-1}. There are $\displaystyle \left({n-1\atop n-2}\right)S(n-2,k-1)$ such partitions. We can continue in this same manner until we reach a (k-1) partition of [n-n] by noting that S(n,k)=0 for all n<k. Then we use the sum principle for all terms.

Please note that in my text [n]={1,2,3,...,n}
• Jul 7th 2010, 08:38 AM
chaoticmindsnsync
On the right track, but $\displaystyle \binom{n-1}{n-2}$ means you can choose $\displaystyle n-1$ or $\displaystyle n$ again, either creating an overcount or making your blocks not a partition of $\displaystyle [n]$. Think about why. (Hint: Think about what $\displaystyle i$ is supposed to represent).
• Jul 7th 2010, 08:41 AM
chaoticmindsnsync
Sorry, in either case, it would make your blocks not a partition of [n]. No overcounting would occur since if n or n-1 showed up twice, we don't have a partition. (which we don't want to count anyways)
• Jul 7th 2010, 06:46 PM
oldguynewstudent
Quote:

Originally Posted by chaoticmindsnsync
Sorry, in either case, it would make your blocks not a partition of [n]. No overcounting would occur since if n or n-1 showed up twice, we don't have a partition. (which we don't want to count anyways)

Yes, thanks, I talked to my professor today. I am finally getting close to understanding these concepts. The major problem is that I restricted the second member to n-1 instead of any other member besides n. If we let the second member partitioned with n be any of the n-1 other elements, then the$\displaystyle \left({n-1\atop n-2}\right)$ makes sense.