Results 1 to 6 of 6

Math Help - Combinatorics: Generating functions

  1. #1
    Member
    Joined
    Oct 2009
    Posts
    114
    Thanks
    1

    Combinatorics: Generating functions

    1. Find the generating function for the ways of distributing n loonies to 5 people so that the first two people have together either at most 8 loonies or an even number.

    2. How many 9 digit numbers are there whose sum of digits is equal to 24?

    For #1, I know how to find the generating function if the first two people have at most 8 loonies together AND an even number. But I am not sure how to approach this problem.

    For #2, isn't this equivalent to asking how many solutions there are to to x1+x2+...+x9=24 with x1=>1? My solution is as follows: C(23+9-1, 9-1) - C(23+8-1, 8-1) = C(31,8) - C(30-7) = 5,852,925. But apparently the answer is 5,949,615.

    Any help would be appreciated.
    Last edited by BrownianMan; October 14th 2012 at 07:56 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Combinatorics: Generating functions

    Hey BrownianMan.

    Do you need to come up with an analytic expression or can you use a computer?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,406
    Thanks
    1488
    Awards
    1

    Re: Combinatorics: Generating functions

    Quote Originally Posted by BrownianMan View Post
    1. Find the generating function for the ways of distributing n loonies to 5 people so that the first two people have together either at most 8 loonies or an even number.
    [/SIZE][/FONT][/SIZE][/FONT]
    [FONT=CMR10][SIZE=3][FONT=CMR10][SIZE=3]For #1, I know how to find the generating function if the first two people have at most 8 loonies together AND an even number. But I am not sure how to approach this problem.
    You say that you know how the do it for A\cap B well A\cup B=A+B-(A\cap B).
    I would like to see your solution.

    Quote Originally Posted by BrownianMan View Post
    How many 9 digit numbers are there whose sum of digits is equal to 24?
    Assuming the first digit is not zero the coefficient of x^{24} in
    \left( {\sum\limits_{k = 1}^9 {x^k } } \right)\left( {\sum\limits_{k = 0}^9 {x^k } } \right)^8 gives the answer.

    See this.
    Last edited by Plato; October 15th 2012 at 07:50 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    Posts
    114
    Thanks
    1

    Re: Combinatorics: Generating functions

    Quote Originally Posted by chiro View Post
    Hey BrownianMan.

    Do you need to come up with an analytic expression or can you use a computer?
    I can use a computer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    Posts
    114
    Thanks
    1

    Re: Combinatorics: Generating functions

    Quote Originally Posted by Plato View Post
    You say that you know how the do it for A\cap B well A\cup B=A+B-(A\cap B).
    I would like to see your solution.


    Assuming the first digit is not zero the coefficient of x^{24} in
    \left( {\sum\limits_{k = 1}^9 {x^k } } \right)\left( {\sum\limits_{k = 0}^9 {x^k } } \right)^8 gives the answer.

    See this.
    Ok, I got #1. Thank you.

    For #2, I am not sure how you got that expression? I know it gives the right answer, but could you explain it a bit?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,406
    Thanks
    1488
    Awards
    1

    Re: Combinatorics: Generating functions

    Quote Originally Posted by BrownianMan View Post
    For #2, I am not sure how you got that expression? I know it gives the right answer, but could you explain it a bit?
    The first factor counts the non-zero digits for the lead digit. The next factor counts any digit for the last eight positions in the nine digit number.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating Functions
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: April 25th 2010, 02:28 PM
  2. combinatorics - generating functions 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2009, 04:06 PM
  3. Combinatorics question - generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 4th 2009, 04:22 PM
  4. Functions and Combinatorics?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 27th 2009, 02:37 PM
  5. Generating functions
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 8th 2009, 10:50 AM

Search Tags


/mathhelpforum @mathhelpforum