Number of solutions to $x_1+x_2+\cdots+x_5=41$

Question

Use a generating function to count the number of integer solutions to $x_1+x_2+\cdots+x_5=41$ that satisfy $0\le x_i\le20$ for all $i$, $x_i$ is even when $i$ is even, and $x_i$ is odd when $i$ is odd.

Ignoring the conditions at the end, I believe that $g(x)=(1+x+x^2+\cdots+x^{20})^5$, and the answer to the problem is the coefficient of $x^{41}$ in $g(x)$. But, as I said, I have ignored the terms after all; I haven't the faintest idea of how to go about incorporating them. I'm (obviously) missing something, and I don't seem to be getting anywhere, no matter how many examples I go through. Any help is greatly appreciated!!

Answer 1

In the general scenario,

$$x_1 + x_2 + ... + x_n = r$$

where $x_k \geq 0$ for all $k$, we have a generating function $g$ that is a product of $n$ polynomials $P$:

$$g(x) = P_1(x)P_2(x)...P_n(x)$$

Each of these $P_k(x)$ is defined by the restrictions on the $x_k$. Each $P_k$ will be a sum of powers of $x$, where each exponent of a $x$ term is a valid value $x_k$ may take on in the above equation. Some examples are prudent:

---

Example $\#1$: We want to find the number of nonnegative integer solutions to $$x_1 + x_2 + x_3 = 10$$ where $x_i \geq 0$ for all $i$

This is the scenario you seem to be fine with: effectively no restrictions. Though it must be noted that there is an implicit maximum of $10$ here for each $x_k$: as you deal with more of these, you will learn whether to use $0 \le x_k \le 10$ or simply $0 \le x_k$ (and thus use an infinite sum). I won't bog us down on the details here regarding which to use, and simply assume finite sums.

Here, since $x_k$ can be $0,1,...,10$, then, each of the $P_k$ polynomials are

$$P_k(x) = 1 + x + x^2 + x^3 + ... + x^{10}$$

(Notice: $x^0 = 1$.) Then the generating function is the product of $P_1,P_2,P_3$ - which are all the same and thus give you the cube of the above.

---

Example $\#2$: We want to find the number of nonnegative integer solutions to $$x_1 + x_2 + x_3 = 10$$ where $x_i \geq 0$ for all $i$, and $x_i$ must be even.

In this scenario, the allowed values for $x_i$ have changed. Now we cannot have odd values! Thus, $x_k$ must be $0,2,4,6,8,$ or $10$ for all $k$. Since these are the allowed values, we see that

$$P_1(x) = P_2(x) = P_3(x) = 1 + x^2 + x^4 + x^6 + x^8 + x^{10}$$

Again, bear in mind how the exponents (when $1 = x^0$) correspond to the allowed values for $x_k$!

Again in this case, $P_1 = P_2 = P_3$, so $g$ is just the cube of any one of them.

---

Example $\#3$: We want to find the number of nonnegative integer solutions to $$x_1 + x_2 + x_3 = 10$$ where $x_i \geq 0$ for all $i$. Further, $x_1$ must be even, $x_2$ must be prime, and $x_3$ must be a perfect square.

Now have different conditions for all three numbers! But this is still doable! We first individually see what values are allowed per variable. On investigation...

• $x_1$ can be $0,2,4,6,8,10$
• $x_2$ can be $2,3,5,7$
• $x_3$ can be $0,1,4,9$

With these in mind, we construct the polynomials one by one. Again, the exponents are the permissibile powers of the corresponding summand, with $x_i^0 = 1$. Then we see

• $P_1(x) = 1 + x^2 + x^4 + x^6 + x^8 + x^{10}$
• $P_2(x) = x^2 + x^3 + x^7 + x^9$
• $P_3(x) = 1 + x + x^4 + x^9$

Our generating function, $g(x)$, this time is not a cube, but simply the product

$$g(x) = P_1(x)P_2(x)P_3(x)$$

If one wanted to write it explicitly they could with no trouble, just substitute in the expressions in the bullets.

---

With these in mind, we consider now your scenario:

$$x_1 + x_2 + x_3 + x_4 + x_5 = 41$$

where, for $k = 1,2,...,5$,

• $x_k \ge 0$
• $x_k \le 20$
• $x_k$ is even for even $k$
• $x_k$ is odd for odd $k$

We translate this into the sets of permissible values. Keep in mind that we cannot go any higher than $41$ necessarily for any value. If you want to, I think this is the kind of equation that would allow for an infinite sum instead of finite - and if you're familiar with that, the work is similar enough that you should be able to analogize it.

In any event, the set of permissible values:

• $x_2,x_4$ can be $0,2,4,6,...,20$
• $x_1,x_3,x_5$ can be $1,3,5,7,...,19$

Then the corresponding polynomials are? We again construct them by basing the exponents on the allowed values:

$$\begin{align} P_1(x) = P_3(x) = P_5(x) &= x + x^3 + x^5 + x^7 + ... + x^{19}\\ P_2(x) = P_4(x) &= 1 + x^2 + x^4 + x^6 + ... + x^{20} \end{align}$$

and then $g(x) = P_1(x)P_2(x)P_3(x)P_4(x)P_5(x)$.

Answer 2

You're a good deal of the way there. What you have so far is five copies of $1+x+\cdots+x^{20}$. They all stop at $20$ because no $x_i$ can be larger than $20$.

The limitation that $x_1$ can only be odd is similarily simple. It just means that the factor of the generating function that corresponds to $x_1$ only has odd-degree terms. So instead of $1+x+x^2+\cdots + x^{20}$, you get $x + x^3 + \cdots + x^{19}$. Do a similar thing for the other four variables, and you have your generating function.