# Generating Functions question

• Oct 11th 2009, 12:17 PM
mathgirlie
Generating Functions question
Alright I have two problems both of which i THINK need to be done with a generating function.... any tips would really be appreciated (Rofl)

First question:
1)Find the number of solutions to the equation
2x + 3y + 6z = 73
where x, y, and z are non-negative integers.

I just took each case individually and got 78 possible solutions, but I was wondering if there was an easier way to do this rather than just finding each solution and counting it.

Also I am getting stuck on this one too:
How many ways are there to put 5 identical objects into n bins, where each
bin can have at most 2 objects?

2)From what we learned in class, I would guess that the generating function would be:

G(x)=(1+x+x^2)^n which is equal to [(x^3-1)/(x-1)]^n which is equal to
(x^3-1)^n*(1/(x-1))^n.

Then that implies that it equals ((x^3-1)^n)*SUM((a_k)x^k)
where a_k= C(k+n-1,k)

Usually I would just plug in 5 for k, and get my answer, but what do I do with the (x^3-1)^n??

Any help would be great!!!!
• Oct 12th 2009, 08:16 AM
awkward
Quote:

Originally Posted by mathgirlie
Alright I have two problems both of which i THINK need to be done with a generating function.... any tips would really be appreciated (Rofl)

First question:
1)Find the number of solutions to the equation
2x + 3y + 6z = 73
where x, y, and z are non-negative integers.

I just took each case individually and got 78 possible solutions, but I was wondering if there was an easier way to do this rather than just finding each solution and counting it.
Also I am getting stuck on this one too:
How many ways are there to put 5 identical objects into n bins, where each
bin can have at most 2 objects?

2)From what we learned in class, I would guess that the generating function would be:

G(x)=(1+x+x^2)^n which is equal to [(x^3-1)/(x-1)]^n which is equal to
(x^3-1)^n*(1/(x-1))^n.

Then that implies that it equals ((x^3-1)^n)*SUM((a_k)x^k)
where a_k= C(k+n-1,k)

Usually I would just plug in 5 for k, and get my answer, but what do I do with the (x^3-1)^n??

Any help would be great!!!!

On 1), did you find the generating function? I think that's the point of the exercise. But in the end, I don't think the generating function will save you much work, in this case. (If someone else sees a shortcut, I hope they will post it.)

For 2), you have found G correctly. Notice that
$\displaystyle G(x) = (1-x^3)^n \; (1-x)^{-n}$
$\displaystyle = \sum_i (-1)^i \binom{n}{i} x^{3i} \cdot \sum_j (-1)^j \binom{-n}{j} x^j$
(I'm assuming you feel comfortable with binomial coefficients like $\displaystyle \binom{-n}{j}$.)
To end up with $\displaystyle x^5$ in this product, you need to consider $\displaystyle x^0 \cdot x^5$ and $\displaystyle x^3 \cdot x^2$. Do you see where they come from?
• Oct 12th 2009, 10:52 AM
mathgirlie
Alright thanks for the help on the 2nd one, I think I understand it, but I really don't understand where you got the (-1)^i and (-1)^j part. Is that because we are subtracting x?. Also, I'm not too sure about how to set up the generating function for the first part... any tips?
• Oct 12th 2009, 06:00 PM
awkward
Quote:

Originally Posted by mathgirlie
Alright thanks for the help on the 2nd one, I think I understand it, but I really don't understand where you got the (-1)^i and (-1)^j part. Is that because we are subtracting x?. Also, I'm not too sure about how to set up the generating function for the first part... any tips?

The $\displaystyle (-1)^i$ is there because we are expanding $\displaystyle (1- x^3)^n = (1 + (-1 \cdot x)^3)^n$.

For the first part, consider the more general problem of determining the number of solutions of

$\displaystyle 2x + 3y + 6z = r$
where x, y, z are non-negative integers.
Let's say the number of solutions is $\displaystyle a_r$.
We want the generating function $\displaystyle f(x) = \sum_{r=0}^{\infty} a_r x^r$.
All I can say is that it's easy once you see it-- just think about how you multiply polynomials:

$\displaystyle f(x) = (1 + x^2 + x^4 + x^6 + \dots) \cdot (1 + x^3 + x^6 + x^9 + \dots) \cdot (1 + x^6 + x^{12} + x^{18} + \dots)$

Then you shoud use your knowledge of series to simplify that expression.
• Oct 12th 2009, 07:25 PM
mathgirlie
thanks so much for your help, I really appreciate it!
• Oct 12th 2009, 08:02 PM
mathgirlie
quick question though, one of those coefficients will be negative, so does that mean I ignore the negative sign and add them together or do I subtract the smaller number from the larger number?
• Oct 13th 2009, 09:08 AM
gmatt
hey mathgirlie,

I think you can greatly simplify things for the first question by considering, given
$\displaystyle 2x+3y+6z=73$

$\displaystyle 2x \equiv 1 \bmod{3} \iff x \equiv 2 \bmod{3} \iff x = 3x'+2$

for some $\displaystyle x'$ and similarily

$\displaystyle y \equiv 1 \bmod{2} \iff y= 2y'+1$

for some $\displaystyle y'$ so that

$\displaystyle 2x+3y+6z=73 \iff 2(3x'+2) + 3(y'+1) + 6z = 73 \iff x'+y'+z = 11$

for some $\displaystyle x',y'$

so a generating function like

$\displaystyle f(x)=(1+x+x^2+x^3+...)^3$

suffices :)
• Oct 13th 2009, 01:43 PM
awkward
Quote:

Originally Posted by mathgirlie
quick question though, one of those coefficients will be negative, so does that mean I ignore the negative sign and add them together or do I subtract the smaller number from the larger number?

Don't ignore the negative sign! Follow the usual rules for adding signed numbers.