# Unable to prove a relation which Stirling Numbers of 2nd kind must satisfy

I am trying exercises of Richard Brualdi Introductory Combinatorics and I am unable to think about this question in exercise of Chapter 8 .

Prove that Stirling numbers of 2nd Kind satisfy S(n, n-2) = $${n \choose 3 } + 3{n \choose 4 }$$ . for n$$\geq$$2 .

I am trying to use Combinatorial definition by which Stirling numbers of 2nd kind S(p,k)equals no. Of partition of p objects into k indistinguishable boxes so that no box remain empty. Using that in case no. box is empty and 1 box contain 3objects I can get the term 4* $${n \choose 3 }$$ but how to obtain the other term. Can someone please help.

## 1 Answer

For a partition of $$n$$ (distinguishable) objects into $$n-2$$ (indistinguishable) subsets, two cases are possible:

1. We have a subset consisting of $$3$$ objects, and all other subsets contain $$1$$ object each. The number of such partitions is equal to the number of ways to select those $$3$$ objects, which is equal to $$\binom{n}{3}$$.
2. We have two subsets consisting of $$2$$ objects each, and all other subsets contain $$1$$ object each. The number of such partitions is equal to the number of ways to select $$4$$ objects [equal to $$\binom{n}{4}$$] multiplied by the number of ways to make $$2$$ pairs out of these $$4$$ objects [equal to $$3$$].