# Stirling numbers - hard proofs

• May 27th 2011, 03:02 PM
Krakowie
Stirling numbers - hard proofs
I have problem with prooving those two identities. Any help would be much appriciated!

Show that:

a)
$\begin{Bmatrix} m+n+1\\ m\end{Bmatrix}= \sum_{k=0}^{m} k\begin{Bmatrix}n+k\\k \end{Bmatrix}$

b)
$\sum_{k=0}^{n} \begin{pmatrix}n\\k \end{pmatrix}\begin{Bmatrix}k\\m \end{Bmatrix}= \begin{Bmatrix}n+1\\m+1 \end{Bmatrix}$

Where:
$\begin{Bmatrix}k\\m \end{Bmatrix}$
is a Stirling number of the second kind.
• May 27th 2011, 03:13 PM
Plato
Quote:

Originally Posted by Krakowie
Show that:
a) $\begin{Bmatrix} m+n+1\\ m\end{Bmatrix}= \sum_{k=0}^{m} k\begin{Bmatrix}n+k\\k \end{Bmatrix}$

b) $\sum_{k=0}^{n} \begin{pmatrix}n\\k \end{pmatrix}\begin{Bmatrix}k\\m \end{Bmatrix}= \begin{Bmatrix}n+1\\m+1 \end{Bmatrix}$

Where:
$\begin{Bmatrix}k\\m \end{Bmatrix}$
is a Stirling number of the second kind.

Do you understand that this is not a homework service nor is it a tutorial service? Please either post some of your own work on these problems or explain what you do not understand about the questions.
• May 28th 2011, 10:17 AM
Krakowie
I have been working on this problem for a long time before I decided to post it here. If you don't want to help, don't help me.

Firstly, I tried to use the following identity, the definition of a Stirling number of the second kind:

$\begin{Bmatrix}n\\k \end{Bmatrix} = \frac{1}{k!} \sum_{j=0}^{k}(-1)^{j}\begin{pmatrix}k\\j \end{pmatrix}(k-j)^{n}$

but it was of no use, since the summations index differ...
Then, i tried using some of the identities for Stirling numbers I found, and eventually realized that this problem is expressed as identities no. 6.15 and 6.22 in Knuth, Patashnik "Concrete Matematics" book. So, I'm not sure if I'm allowed to use all the other identities that I found there to prove this one...
I guess the best way to prove it would be by induction, but it also doesn't work.
I've also tried to calculate right and left handsides in WolframAlpha, but the results were just what we have here, no middle-steps.
If you could just give me a clue...
• May 28th 2011, 12:28 PM
Plato
Quote:

Originally Posted by Krakowie
I have been working on this problem for a long time before I decided to post it here. If you don't want to help, don't help me.

I will be blunt with you: I do not care for the above comment.
You are the one who simply posted the question without any explanation as to what you did not understand. Do you understand what the Stirling Numbers of the second kind count? $\mathcal{S}^{(n)}_k=\left\{ {\begin{array}{c} n \\ k \\ \end{array} } \right\}$,
counts the number of ways to place n distinguishable objects into k indistinguishable cells where no cells may be empty.

It would seem as if these problems are calling for combinational proofs.

Do you know this recursion?
$f(n,k)= \mathcal{S}^{(n)}_k$ so that $0 gives
$f(n,k)=f(n-1,k-1)+kf(n-1,k)$ where $f(n,k)=0$ if $k>n$, $f(n,1)=0,~f(n,n)=1$ and if $n>0,~f(n,0)=0$.
• Jun 2nd 2011, 06:03 PM
Renji Rodrigo
Using the recurrence relation of the stirling numbers os the second kind

$\bigg\{^{n}_{k}\bigg\}=k.\bigg\{^{n-1}_{\;\;k}\bigg\}+\bigg\{^{n-1}_{k-1}\bigg\}$

in the place of n, put n+1+k, so

$\bigg\{^{n+1+k}_{\;\;k}\bigg\}- \bigg\{^{n+k}_{k-1}\bigg\} =k.\bigg\{^{n+k}_{\;\;k}\bigg\}$

take

$f(k) = \bigg\{^{n+k}_{k-1}\bigg\}$

then

$f(k+1)- f(k) = k.\bigg\{^{n+k}_{\;\;k}\bigg\}$

apply the summation $\sum\limits^m_{k=0}$, the first summation is telescopic

$\sum\limits^m_{k=0}k.\bigg\{^{n+k}_{\;\;k}\bigg\} = \bigg\{^{n+m+1}_{\;\;\;m}\bigg\}$