I'm somewhat stuck on a problem involving using generating functions to determine the number of possible solutions to an equation. I've attempted to solve the problem by following an example in my textbook, however I am unsure still if I have correctly answered the problem.
The problem follows:
Find the generating function for the number of integer solutions of:
a) $2w + 3x +5y + 7z = n$ where $0 \leq w, x, y, z$
b) $2w + 3x + 5y + 7z = n$ where $ 0 \leq w, 4 \leq x, y, 5 \leq z$
Now, the work I've so far attempted to do is to assign the following functions to each of the terms:
$2w = 1+a^2+a^4+a^6+ ..$
$3x = 1 + a^3 + a^6 + a^9+..$
$5y = 1 + a^5 + a^{10} +a^{15} +..$
$7z = 1+a^7+a^{14}+a^{21}+..$
Again, I've only just followed the example in the textbook as I am unsure of what to do. Could anyone explain what this means? (if it is correct?)
Then, I've come up with the generating function by multiplying these values together:
$$f(x)=(1+a^2+a^4+..)(1+a^3+a^6+..)(1+a^5+a^10+..)(1+a^7+a^14+..) $$
Now as far as I know, this is a valid generating function. However, my textbook takes one more step, and I've followed suit:
$$f(x)=\frac{1}{1-x^2}*\frac{1}{1-x^3}*\frac{1}{1-x^5}*\frac{1}{1-x^7}$$
I don't understand the step that is taken here, but this is what I have come up with for my final answer to a).
Now for b), I've taken the equations that I lined out and simply eliminated the earlier terms according to the restrictions on $w,x,y,z$
$2w = 1+a^2+a^4+a^6+ ..$
$3x = a^9+a^{12}+..$
$5y = a^{15} + a^{20}+..$
$7z = a^{28}+a^{35}+..$
If anyone can offer any insight here I would greatly appreciate it. I'm having quite a bit of trouble with my combinatorics class..
Cheers everyone
Best Answer
The step from $$f(x)=(1+a^2+a^4+\ldots)(1+a^3+a^6+\ldots)(1+a^5+a^{10}+\ldots)(1+a^7+a^{14}+\ldots)$$ to $$f(x)=\frac1{(1-a^2)(1-a^3)(1-a^5)(1-a^7)}\tag{1}$$ just uses the formula for the sum of a geometric series. For example,
$$1+a^5+a^{10}+\ldots=\sum_{k\ge 0}a^{5k}=\sum_{k\ge 0}\left(a^5\right)^k=\frac1{1-a^5}\;.$$
And yes, $(1)$ is correct for the first problem.
You’ve made the right start on the second problem; now all you have to do is sum those geometric series. For example,
$$a^9+a^{12}+a^{15}+\ldots=\sum_{k\ge 3}a^{3k}=\sum_{k\ge 3}\left(a^3\right)^k=\frac{a^9}{1-a^3}$$ by the usual formula for the sum of an infinite geometric series. Convert the other three factors to closed forms in similar fashion, and you’ll get your generating function; it should have the same denominator as $(1)$, but a different numerator.