1. ## Stirling numbers

I need to show

$S(n,n-2) = \binom{n}{3} + 3\binom{n}{4}$

I understand how to get $\binom{n}{3}$ but the 3 $\binom{n}{4}$ is throwing me off a little bit, can anyone help?

2. Originally Posted by Jrb599
I need to show

$S(n,n-2) = \binom{n}{3} + 3\binom{n}{4}$

I understand how to get $\binom{n}{3}$ but the 3 $\binom{n}{4}$ is throwing me off a little bit, can anyone help?
The $\binom{n}{3}$ comes from partitioning the n elements into 1 set of size 3 and n - 3 sets of size 1.

Then you have to add the number of ways of partitioning the n elements into 2 sets of size 2 and n - 4 sets of size 1. This is equal to (the number of ways of choosing 4 elements from the n elements) times (number of ways of choosing 2 elements from 4)/2:

${n \choose 4} \, \frac{{4 \choose 2}}{2}$.

You divide by 2 because otherwise you've double counted .... Think about it.

3. Originally Posted by Jrb599
$S(n,n-2) = \binom{n}{3} + 3\binom{n}{4}$
I understand how to get $\binom{n}{3}$ but the 3 $\binom{n}{4}$ is throwing me off a little bit, can anyone help?
First, these must be Stirling Numbers of the second kind.
S(n,k) is the number of ways to partition a set of n individuals into k non-empty cells.
Therefore, in this problem we must have $n \ge 4$.
So if $n=4$ then how many ways can one partition the set in two non-empty subsets?
It is clear that we can have one cell with three elements and one with one element: $\binom {4}{3}$ ways.

Or we can have two cells with two elements each: $\frac {\binom {4}{2}} {2}$.

Can you continue?

4. Originally Posted by Plato
First, these must be Stirling Numbers of the second kind.
S(n,k) is the number of ways to partition a set of n individuals into k non-empty cells.
Therefore, in this problem we must have $n \ge 4$.
So if $n=4$ then how many ways can one partition the set in two non-empty subsets?
It is clear that we can have one cell with three elements and one with one element: $\binom {4}{3}$ ways.

Or we can have two cells with two elements each: $\frac {\binom {4}{2}} {2}$.

Can you continue?
According to the problem n>2.

Thanks for your help, I did get it.

5. Originally Posted by Jrb599
According to the problem n>2.

Thanks for your help, I did get it.
There's no problem with n = 2 or n = 3 ....

n = 2: S(2, 0) = 0, since there's no way to partition 2 elements into zero sets .... (note that in general, $S(n, 0) = \delta_{n\, 0}$, where $\delta_{n\, 0}$ is the Kronecker delta).

n = 3: S(3, 1) = 1, since there's only one way to partition 3 elements into one set ....

However ..... these values of n cannot be used in the formula (since the combinatorials are undefined for n < 4), which is what I think Plato was refering to.

One might try to argue a case that ${3 \choose 4} = 0$, ${2 \choose 3} = 0$ and ${2 \choose 4} = 0$ ......