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.

Re: Combinatorics: Generating functions

Hey BrownianMan.

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

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 $\displaystyle A\cap B$ well $\displaystyle 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 $\displaystyle x^{24}$ in

$\displaystyle \left( {\sum\limits_{k = 1}^9 {x^k } } \right)\left( {\sum\limits_{k = 0}^9 {x^k } } \right)^8 $ gives the answer.

See this.

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.

Re: Combinatorics: Generating functions

Quote:

Originally Posted by

**Plato** You say that you know how the do it for $\displaystyle A\cap B$ well $\displaystyle 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 $\displaystyle x^{24}$ in

$\displaystyle \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?

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.