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.

2. ## Re: Combinatorics: Generating functions

Hey BrownianMan.

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

3. ## Re: Combinatorics: Generating functions

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.

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.

4. ## Re: Combinatorics: Generating functions

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.

5. ## Re: Combinatorics: Generating functions

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?

6. ## Re: Combinatorics: Generating functions

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.