Results 1 to 5 of 5

Math Help - Stirling numbers - hard proofs

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    12

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Krakowie View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    12
    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...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Krakowie View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
    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\}
    Last edited by Renji Rodrigo; June 2nd 2011 at 06:14 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Stirling numbers of the second kind identity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 7th 2010, 06:46 PM
  2. Stirling numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 22nd 2010, 07:52 AM
  3. Stirling's Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 11:16 PM
  4. Stirling numbers
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 17th 2008, 07:43 PM
  5. Question regarding Stirling Numbers!!!!!!!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 30th 2007, 09:17 AM

Search Tags


/mathhelpforum @mathhelpforum