0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$].
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.