Results 1 to 3 of 3

Math Help - Justify S(n,n-1)= nC2

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

    Justify S(n,n-1)= nC2

    Is the following a valid combinatorial proof of the Stirling identity?

    Prove S(n,n-1) = \left({n\atop 2}\right).

    First look at the partition of n into n blocks. We then have blocks n_{1},n_{2},...,n_{n}. Now if we partition n into n-1 blocks, some n_{i},n_{j} will have to share a block. This is the same as choosing 2 from n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    Is the following a valid combinatorial proof of the Stirling identity?

    Prove S(n,n-1) = \left({n\atop 2}\right).

    First look at the partition of n into n blocks. We then have blocks n_{1},n_{2},...,n_{n}. Now if we partition n into n-1 blocks, some n_{i},n_{j} will have to share a block. This is the same as choosing 2 from n.
    Hi oldguynewstudent,

    I think you have the right idea, but I find your notation confusing. You seen to be using n_i both to denote a block (i.e., a subset) and an element of the set S. Try using different symbols for the blocks and the elements and I think it will be clearer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by oldguynewstudent View Post
    Is the following a valid combinatorial proof of the Stirling identity?

    Prove S(n,n-1) = \left({n\atop 2}\right).

    First look at the partition of n into n blocks. We then have blocks n_{1},n_{2},...,n_{n}. Now if we partition n into n-1 blocks, some n_{i},n_{j} will have to share a block. This is the same as choosing 2 from n.
    The Stirling Numbers of the Second Kind have this nifty recurrence relation:  \left\{{n\atop k}\right\} = \left\{{n-1\atop k-1}\right\} +k \left\{{ n-1 \atop k }\right\} .

    This comes with a fairly straightforward combinatorial proof which can be found here.


    So  \left\{{n\atop n-1}\right\} = \left\{{n-1\atop n-2}\right\} +(n-1) \left\{{ n-1 \atop n-1 }\right\} = \left\{{n-1\atop n-2}\right\} +(n-1) .

    Now  \binom{n}{2} = \binom{n-1}{2}+\binom{n-1}{1} = \binom{n-1}{2}+(n-1) (Pascal's Identity).

    Last but not least we need to notice  \left\{{1\atop 0}\right\} = \binom{1}{2} = 1 .

    So we see both formulas have the same base case and same recurrence relation and hence are equal, which can be shown inductively.
    Last edited by chiph588@; July 15th 2010 at 07:58 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Justify basis
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: January 21st 2010, 05:19 PM
  2. How do you justify this limit?
    Posted in the Calculus Forum
    Replies: 5
    Last Post: November 5th 2009, 07:12 PM
  3. Replies: 5
    Last Post: September 6th 2009, 02:53 PM
  4. Latex justify
    Posted in the LaTeX Help Forum
    Replies: 2
    Last Post: May 7th 2009, 01:34 PM
  5. simplify each expression. Justify each step
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 8th 2008, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum