2
$\begingroup$

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.

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

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}$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – rulonsw Dec 3 '15 at 17:44
  • $\begingroup$ 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$. $\endgroup$ – rVitale Dec 3 '15 at 18:09
  • $\begingroup$ Duly noted. I think I've got it now - thank you! $\endgroup$ – rulonsw Dec 3 '15 at 18:33
  • $\begingroup$ No problem, glad the answer helped! $\endgroup$ – rVitale Dec 3 '15 at 20:16

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.