How many solutions to the (general) equation?

I've been trying to hash this one out for the last few days.

Please determine the number of solutions to the equation $x_1 + x_2 + x_3 + x_4 = n$, where $x_i \in N$, $x_1$ is even, $0 \leq x_2 \leq 2$, 3 divides $x_3$, and $x_4 \in \left\{0,1\right\}$.

My thoughts, so far: The possible combinations of $x_2$ and $x_4$ are fairly straightforward; I'm more concerned about dealing with $x_1, x_3$. I initially thought, since the range of numbers covered by these two are, for all intents and purposes, infinite, that there would be an infinite amount of solutions. But, n is obviously some finite number, so any value exceeding n would not be a viable solution.

Am I overthinking this? Could this still be the same stars-and-bars problem from previous SE entries?

Thanks for your input.

• If you set limiting value for n then its totally easy or number of solutions are $\infty$ – Archis Welankar Dec 3 '15 at 16:48

Here is a generating function solution.

First your constraints can be encoded by power series which include all powers of $x$ that satisfy your constraint:

$\bullet$ $x_1$ is even$\rightarrow 1 + x^2 + x^4 + \cdots$

$\bullet$ $0 \leq x_2 \leq2 \rightarrow 1+x+x^2$

$\bullet$ $3|x_3 \rightarrow 1+x^3+x^6+ \cdots$

$\bullet$ $x_4 \in \{0,1\} \rightarrow 1+x$.

Now consider the product of all of these:

$$(1 + x^2 + x^4 + \cdots)(1+x+x^2)(1+x^3+x^6+ \cdots)(1+x) =\frac{(1+x+x^2)(1+x)}{(1-x^2)(1-x^3)}$$

If you expand the right hand side above out in a series and find the coefficient of $x^n$, that will tell you the number of solutions to $x_1+x_2+x_3+x_4=n$. This works since the coefficient is the number of ways to pick one term from each factor of the above product so that the exponents add to $n$. For example if $n=8$ you have $4+1+3+0$ as a solution taking $x^4$ from the first factor, $x^1$ from the second, and so on.

So, you're left to expand the rational function in a series. First notice all the cancellation you get:

$$\frac{(1+x+x^2)(1+x)}{(1-x^2)(1-x^3)}=\frac{(1+x+x^2)(1+x)}{(1-x)(1+x)(1-x)(1+x+x^2)}=\left(\frac{1}{1-x}\right)^2$$

Now since $\frac{1}{1-x}=\sum x^i$ we have $\left(\frac{1}{1-x} \right)^2=_*\sum ix^{i-1}$ , so the coefficient of $x^n$ is $n+1$, and there are $n+1$ tuples $(x_1,x_2,x_3,x_4)$ meeting your constraints so that $x_1+x_2+x_3+x_4=n.$

$*:$ you can see this by noticing $\left(\frac{1}{1-x}\right)^2$ is the derivative of $\frac{1}{1-x}$ or just squaring the series for $\frac{1}{1-x}$

• This answer is incredibly well-detailed and awesome - but I'm being sort-of dense on how your product of the series evaulates to what you've gotten. How did $(1-x^2)$ and $(1-x^3)$ end up in the denominator? – rulonsw Dec 3 '15 at 17:44
• That's since two of the factors are geometric series. In general $\sum u^i = \frac{1}{1-u}$, so replace $u$ by $x^2$ and $x^3$. – rVitale Dec 3 '15 at 18:09
• Duly noted. I think I've got it now - thank you! – rulonsw Dec 3 '15 at 18:33
• No problem, glad the answer helped! – rVitale Dec 3 '15 at 20:16