Stirling numbers

**Krakowie** · May 27th 2011, 03:02 PM

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.

**Plato** · May 27th 2011, 03:13 PM

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.

**Krakowie** · May 28th 2011, 10:17 AM

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...

**Plato** · May 28th 2011, 12:28 PM

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<k\le n$ 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$ .

**Renji Rodrigo** · June 2nd 2011, 06:03 PM

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\}$

Thread: Stirling numbers - hard proofs

LinkBack

Thread Tools

Display

Stirling numbers - hard proofs

Similar Math Help Forum Discussions

Stirling numbers of the second kind identity

Stirling's Numbers

Stirling numbers

Question regarding Stirling Numbers!!!!!!!

Search Tags