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

combinatoricsdiscrete mathematicsstirling-numbers

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.

Best Answer

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

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}$.
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$].

Related Solutions

[Math] Stirling Numbers of the Second Kind

Martin has already explained the notation, but you might also find the following connection with Stirling numbers of the second kind useful, since those are the ones mentioned in your title.

If you calculate the $c(n,k)$ for $n=0,1,2,3,4,5$, you get the following array of $0$-th diagonals:

   n\k:  0   1   2   3   4   5  
   ---------------------------  
   0 |   1  
   1 |   0   1  
   2 |   0   1   2  
   3 |   0   1   6   6  
   4 |   0   1  14  36  24  
   5 |   0   1  30 150 240 120

This triangle can be found as A131689 at OEIS, where you can discover that the entry in row $n$, column $k$ is $$k!\left\{\matrix{n\\k}\right\},$$ where $\displaystyle\left\{\matrix{n\\k}\right\}$ is the Stirling number of the second kind. And sure enough, if we divide each entry in column $k$ by $k!$ we get the following table:

   n\k:  0   1   2   3   4   5  
   ---------------------------  
   0 |   1  
   1 |   0   1  
   2 |   0   1   1  
   3 |   0   1   3   1  
   4 |   0   1   7   6   1  
   5 |   0   1  15  25  10   1

This is readily recognizable as the table of Stirling numbers of the second kind.

[Math] Ways to put $5$ balls in $3$ boxes if each box must contain at least $1$ ball.

First we assume that the balls are indistinguishable.

Line up the $5$ balls like this $$ B\qquad B \qquad B \qquad B \qquad B$$ We will choose $2$ from the $4$ gaps between $B$'s to put a separator into. Then all $B$ up to the first separator go into the first box, all $B$'s between the two separators go into the second box, and the rest go into the third.

There are exactly as many ways to insert separators as there are ways to distribute the balls between the boxes. So there are $\binom{5-1}{3-1}$ ways to do the job.

Remark: The idea generalizes. Please see the Wikipedia article on Stars and Bars.

Next we assume the balls are distinguishable. We use Inclusion/Exclusion. There are $3^5$ ways to distribute the balls, with no restriction.

There are $2^5$ patterns in which the first box is empty, and the same number with the second empty, and the same with the third empty.

However, if we subtract $3\cdot 2^5$ from $3^5$, we have subtracted too many times the patterns in which two of the boxes are empty. So we need to add back $3\cdot 1^5$, giving count $3^5-3\cdot 2^5+3\cdot 1^5$.

Best Answer

Related Solutions

[Math] Stirling Numbers of the Second Kind

[Math] Ways to put $5$ balls in $3$ boxes if each box must contain at least $1$ ball.

Related Question