1. ## 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

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!!!!

2. 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

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
$G(x) = (1-x^3)^n \; (1-x)^{-n}$
$= \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 $\binom{-n}{j}$.)
To end up with $x^5$ in this product, you need to consider $x^0 \cdot x^5$ and $x^3 \cdot x^2$. Do you see where they come from?

3. 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?

4. 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 $(-1)^i$ is there because we are expanding $(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

$2x + 3y + 6z = r$
where x, y, z are non-negative integers.
Let's say the number of solutions is $a_r$.
We want the generating function $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:

$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.

5. thanks so much for your help, I really appreciate it!

6. 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?

7. hey mathgirlie,

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

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

for some $x'$ and similarily

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

for some $y'$ so that

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

for some $x',y'$

so a generating function like

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

suffices

8. 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.