For each, give the generating function for the number of solutions

Question

For each, give the generating function for the number of solutions to the equation with the constraints given. You do not need to find the number of solutions, just the generating function.

a) $x_1 + x_2 + x_3 = n$ with $x_1$ odd and $x_2$ even and $x_2$ ≤ 20 and $x_3$ ≥ 10.
b) $x_1 + x_2 + x_3 ≤ n$ with $x_1$ odd and $x_2$ even and $x_2$ ≤ 20 and $x_3$ ≥ 10.
c) $x_1 + x_2 + x_3 = n$ with $x_1$ a multiple of 5 and $x_2$ prime and 5 ≤ $x_3$ ≤ 15.

For a)
I found that for $x_1$ i got $1/(1-X^1)$.
For $x_2$ I got $(1-X^{21})/(1-X)$
For $x_3$ I got $X^{10}/(1-X)$
So my final answer was $[X^n](1/(1-X^1))((1-X^{21})/(1-X))(X^{10}/(1-X))$

For part B I am confused on what to do when you have $x_1 + x_2 + x_3 ≤ n$. I thought maybe you would use factorial since it is ≤ n.
For Part C I am not sure how I would represent prime numbers.

Answer 1

Your solution to (a) doesn’t take into account the parity requirements: $x_1$ has to be odd, and $x_2$ has to be even. To get the odd numbers you need

$$x+x^3+x^5+x^7+\ldots=x\left(1+x^2+x^4+x^6+\ldots\right)=\frac{x}{1-x^2}\;.$$

To get the even numbers up through $20$ you need

$$1+x^2+x^4+\ldots+x^{20}=\frac{1-x^{22}}{1-x^2}\;.$$

What you’ve done with $x_3$ is fine, so you want

$$\frac{x}{1-x^2}\cdot\frac{1-x^{22}}{1-x^2}\cdot\frac{x^{10}}{1-x}=\frac{x^{11}(1-x^{22})}{(1-x)(1-x^2)^2}\;.$$

Note that you were asked for the generating function itself, so you don’t want the coefficient operator $[x^n]$.

The trick for (b) is to use a fourth variable to take up the slack: count the solutions to $$x_1+x_2+x_3+x_4=n$$ that satisfy the given restrictions (and of course $x_4\ge 0$).

To the best of my knowledge there is no nice closed form for the factor $$\sum_{p\text{ prime}}x^p$$ that you want for (c), and you’ll just have to leave it as a summation.