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:


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.