Results 1 to 5 of 5

Math Help - Stirling numbers

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    30

    Stirling numbers

    I need to show

    S(n,n-2) = \binom{n}{3} + 3\binom{n}{4}

    I understand how to get \binom{n}{3} but the 3 \binom{n}{4} is throwing me off a little bit, can anyone help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Jrb599 View Post
    I need to show

    S(n,n-2) = \binom{n}{3} + 3\binom{n}{4}

    I understand how to get \binom{n}{3} but the 3 \binom{n}{4} is throwing me off a little bit, can anyone help?
    The \binom{n}{3} comes from partitioning the n elements into 1 set of size 3 and n - 3 sets of size 1.

    Then you have to add the number of ways of partitioning the n elements into 2 sets of size 2 and n - 4 sets of size 1. This is equal to (the number of ways of choosing 4 elements from the n elements) times (number of ways of choosing 2 elements from 4)/2:

    {n \choose 4} \, \frac{{4 \choose 2}}{2}.

    You divide by 2 because otherwise you've double counted .... Think about it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,798
    Thanks
    1690
    Awards
    1
    Quote Originally Posted by Jrb599 View Post
    S(n,n-2) = \binom{n}{3} + 3\binom{n}{4}
    I understand how to get \binom{n}{3} but the 3 \binom{n}{4} is throwing me off a little bit, can anyone help?
    First, these must be Stirling Numbers of the second kind.
    S(n,k) is the number of ways to partition a set of n individuals into k non-empty cells.
    Therefore, in this problem we must have n \ge 4.
    So if n=4 then how many ways can one partition the set in two non-empty subsets?
    It is clear that we can have one cell with three elements and one with one element: \binom {4}{3} ways.

    Or we can have two cells with two elements each: \frac {\binom {4}{2}} {2}.

    Can you continue?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2007
    Posts
    30
    Quote Originally Posted by Plato View Post
    First, these must be Stirling Numbers of the second kind.
    S(n,k) is the number of ways to partition a set of n individuals into k non-empty cells.
    Therefore, in this problem we must have n \ge 4.
    So if n=4 then how many ways can one partition the set in two non-empty subsets?
    It is clear that we can have one cell with three elements and one with one element: \binom {4}{3} ways.

    Or we can have two cells with two elements each: \frac {\binom {4}{2}} {2}.

    Can you continue?
    According to the problem n>2.

    Thanks for your help, I did get it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Jrb599 View Post
    According to the problem n>2.

    Thanks for your help, I did get it.
    There's no problem with n = 2 or n = 3 ....

    n = 2: S(2, 0) = 0, since there's no way to partition 2 elements into zero sets .... (note that in general, S(n, 0) = \delta_{n\, 0}, where \delta_{n\, 0} is the Kronecker delta).

    n = 3: S(3, 1) = 1, since there's only one way to partition 3 elements into one set ....

    However ..... these values of n cannot be used in the formula (since the combinatorials are undefined for n < 4), which is what I think Plato was refering to.

    One might try to argue a case that {3 \choose 4} = 0, {2 \choose 3} = 0 and {2 \choose 4} = 0 ......
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Stirling numbers - hard proofs
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 2nd 2011, 06:03 PM
  2. Stirling numbers of the second kind identity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 7th 2010, 06:46 PM
  3. Stirling numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 22nd 2010, 07:52 AM
  4. Stirling's Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 11:16 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