Combinatorics: Generating functions

Printable View

October 14th 2012, 07:01 PM
BrownianMan

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.
October 15th 2012, 01:41 AM
chiro

Re: Combinatorics: Generating functions

Hey BrownianMan.

Do you need to come up with an analytic expression or can you use a computer?
October 15th 2012, 06:26 AM
Plato

Re: Combinatorics: Generating functions

Quote:

Originally Posted by BrownianMan

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

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.
October 15th 2012, 12:49 PM
BrownianMan

Re: Combinatorics: Generating functions

Quote:

Originally Posted by chiro

Hey BrownianMan.

Do you need to come up with an analytic expression or can you use a computer?

I can use a computer.
October 15th 2012, 01:40 PM
BrownianMan

Re: Combinatorics: Generating functions

Quote:

Originally Posted by Plato

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?
October 15th 2012, 01:47 PM
Plato

Re: Combinatorics: Generating functions

Quote:

Originally Posted by BrownianMan

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.