Where $S(n,k)$ is the stirling number of the second kind.
In my combinatorics course $S(n,k)$ has only been defined as the "number of ways to put $n$ distinguishable balls in $k$ non-distinguishable cells that cannot be empty".
I know the correct answer is $S(n, n-2) = {n\choose3} + 3{n\choose4}$ (from Stirling number proof, proving that $s(n, n-2) = 2{n\choose3} + 3{n\choose4}$) but have no clue how to start the problem. I feel that the hint in the link I just gave did not help me. Would anyone have any other help?
Thanks
Such an arrangement would be of two possible types: (i) $3$ balls in one box, with the remaining $n-3$ boxes with one ball apiece, (ii) $2$ balls in one box, $2$ in another box, and $n-4$ boxes with one ball apiece.
To count the type (i) arrangements, all you have to do is specify the $3$ balls that go together. There are $\binom n3$ ways to do this. For type (ii), there are $\binom n4$ ways to choose the non-lonely balls, but then what?