# Math Help - Justify S(n,n-1)= nC2

1. ## Justify S(n,n-1)= nC2

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

Prove S(n,n-1) = $\left({n\atop 2}\right)$.

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

2. Originally Posted by oldguynewstudent
Is the following a valid combinatorial proof of the Stirling identity?

Prove S(n,n-1) = $\left({n\atop 2}\right)$.

First look at the partition of n into n blocks. We then have blocks $n_{1},n_{2},...,n_{n}$. Now if we partition n into n-1 blocks, some $n_{i},n_{j}$ 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 $n_i$ 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.

3. Originally Posted by oldguynewstudent
Is the following a valid combinatorial proof of the Stirling identity?

Prove S(n,n-1) = $\left({n\atop 2}\right)$.

First look at the partition of n into n blocks. We then have blocks $n_{1},n_{2},...,n_{n}$. Now if we partition n into n-1 blocks, some $n_{i},n_{j}$ 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: $\left\{{n\atop k}\right\} = \left\{{n-1\atop k-1}\right\} +k \left\{{ n-1 \atop k }\right\}$.

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

So $\left\{{n\atop n-1}\right\} = \left\{{n-1\atop n-2}\right\} +(n-1) \left\{{ n-1 \atop n-1 }\right\} = \left\{{n-1\atop n-2}\right\} +(n-1)$.

Now $\binom{n}{2} = \binom{n-1}{2}+\binom{n-1}{1} = \binom{n-1}{2}+(n-1)$ (Pascal's Identity).

Last but not least we need to notice $\left\{{1\atop 0}\right\} = \binom{1}{2} = 1$.

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