Dgdrxrt

Use a generating function to count the number of integer solutions
to $x_1+x_2+cdots+x_5=41$ that satisfy $0le x_ile20$ 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!!

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:

$$beginalign
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
endalign$$

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

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.