Thread: Justify S(n,n-1)= nC2

Is the following a valid combinatorial proof of the Stirling identity?

Prove S(n,n-1) = .

First look at the partition of n into n blocks. We then have blocks . Now if we partition n into n-1 blocks, some will have to share a block. This is the same as choosing 2 from n.

Originally Posted by oldguynewstudent

Is the following a valid combinatorial proof of the Stirling identity?

Prove S(n,n-1) = .

First look at the partition of n into n blocks. We then have blocks . Now if we partition n into n-1 blocks, some will have to share a block. This is the same as choosing 2 from n.

Hi oldguynewstudent,

I think you have the right idea, but I find your notation confusing. You seen to be using both to denote a block (i.e., a subset) and an element of the set S. Try using different symbols for the blocks and the elements and I think it will be clearer.

Originally Posted by oldguynewstudent

Is the following a valid combinatorial proof of the Stirling identity?

Prove S(n,n-1) = .

First look at the partition of n into n blocks. We then have blocks . Now if we partition n into n-1 blocks, some will have to share a block. This is the same as choosing 2 from n.

The Stirling Numbers of the Second Kind have this nifty recurrence relation: .

This comes with a fairly straightforward combinatorial proof which can be found here.


So .

Now (Pascal's Identity).

Last but not least we need to notice .

So we see both formulas have the same base case and same recurrence relation and hence are equal, which can be shown inductively.