Results 1 to 4 of 4

Math Help - Stirling numbers of the second kind identity

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Stirling numbers of the second kind identity

    I am understanding this a little better. Could someone let me know if I am on the right track with the following proof?

    Give combinatorial proof: n \geq1 and k \geq1 then

    S(n,k)=\sum_{i=0}^{n-1}\left({n-1\atop i}\right)S(i,k-1).

    Condition on whether the element n is in a block by itself. If it is, then all such partitions can be constructed by first specifying a (k-1) partition of [n-1] and then adding the block {n}. There are S(n-1,k-1) such partitions.

    We can continue the next case by putting n and n-1 into a block by themselves. We construct these partitions by first specifying a (k-1) partition of [n-2] and then adding the block {n,n-1}. There are \left({n-1\atop n-2}\right)S(n-2,k-1) such partitions. We can continue in this same manner until we reach a (k-1) partition of [n-n] by noting that S(n,k)=0 for all n<k. Then we use the sum principle for all terms.

    Please note that in my text [n]={1,2,3,...,n}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2010
    Posts
    9
    On the right track, but \binom{n-1}{n-2} means you can choose n-1 or n again, either creating an overcount or making your blocks not a partition of [n]. Think about why. (Hint: Think about what i is supposed to represent).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    9
    Sorry, in either case, it would make your blocks not a partition of [n]. No overcounting would occur since if n or n-1 showed up twice, we don't have a partition. (which we don't want to count anyways)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by chaoticmindsnsync View Post
    Sorry, in either case, it would make your blocks not a partition of [n]. No overcounting would occur since if n or n-1 showed up twice, we don't have a partition. (which we don't want to count anyways)
    Yes, thanks, I talked to my professor today. I am finally getting close to understanding these concepts. The major problem is that I restricted the second member to n-1 instead of any other member besides n. If we let the second member partitioned with n be any of the n-1 other elements, then the \left({n-1\atop n-2}\right) makes sense.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 4th 2010, 04:58 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