Use combinatorial reasoning to show that Stirling number

Question

Use combinatorial reasoning to show

$\begin{Bmatrix} n\\ n-2 \end{Bmatrix} = \binom{n}{3} + 3\binom{n}{4}.$

The Stirling number is the number of permutation of n into $n-2$ parts.

Answer 1

No, the Stirling number $n\brace{n-2}$ of the second kind is the number of ways to partition $[n]$ into $n-2$ non-empty unlabelled parts; permutations are not involved.

HINT: If you divide $[n]$ into $n-2$ parts, you must necessarily end up either with

• one part of size $3$ and $n-3$ parts of size $1$ each

or with

• two parts of size $2$ and $n-4$ parts of size $1$ each.

In each case think about how many ways are there to pick the members of the parts that aren’t singletons.

Answer 2

Left Hand Side

You have $n-2$ indistinguishable rooms and $n$ people. The number of way to distribute the people so that no rooms are empty is given by the left hand side:

$$ \left\{n\atop n-2\right\} $$

Right Hand Side

Three people sleep in the same room while the others sleep alone. The number of way to select these three people is given by the first term on the right hand side.

$$ \binom{n}{3} $$

Another possible arrangement is four people do not sleep alone but sleep in pairs. To do this, select four people first then divide these people into two rooms.

$$ \binom{n}{4}\cdot\frac{1}{2}\binom{4}{2}=3\cdot\binom{n}{4} $$

Conclusion

Both left and right hand side gives the number of possible arrangement if we want to divide $n$ people into $n-2$ non - empty subsets so they must be equal, as requested:

$$ \left\{n\atop n-2\right\}=\binom{n}{3}+3\binom{n}{4} $$