The number of integer solutions with restriction

Question

How many integer solutions are there to $$\begin{aligned} x_{1}+x_{2}+x_{3}=n \end{aligned}$$ where $x_{1}\ge 0$ and is even, $x_{2}\ge 0$ , and $0\le x_{3}\le 2$ .

I don't think this problem can be easily solved by inclusion-exclusion, so I tried to use generating function. By the restriction, the generating function should be $$\begin{aligned} &(1+x^2+x^4+\cdots )(1+x+x^2+x^3+\cdots )(1+x+x^2) \\ =& \frac{ 1}{1-x^2} \cdot \frac{ 1}{1-x} \cdot \frac{ 1-x^3}{1-x} \end{aligned}$$ Then I want to expand this so I can determine the coefficient in front of $x^n$, which is the number of integer solutions. However, I got stuck here. Any help or other method to approach this? Thanks.

Answer 1

You got the generating function $$ f(x)=\frac{ 1}{1-x^2} \cdot \frac{ 1}{1-x} \cdot \frac{ 1-x^3}{1-x}=\frac{x^2+x+1}{(x-1)^2(x+1)}. $$ From here the standard step is to use partial fractions decomposition. This way you would find $$ f(x)=\frac{1}{4}\frac{1}{1+x}+\frac{3}{2}\frac{1}{(1-x)^2}-\frac{3}{4}\frac{1}{1-x}. $$ Then we expand the individual summands using mainly geometric series sum and $\frac{1}{(1-x)^2}=\frac{d}{dx}(\frac{1}{1-x})$, hence we have $$ f(x)=\frac{1}{4}\sum_{n \geq 0} (-x)^n+\frac{3}{2}\sum_{n \geq 0} nx^{n-1}-\frac{3}{4}\sum_{n \geq 0} x^n. $$ Removing the term for $n=0$ for the middle sum and shifting the index we therefore arrive to $$ f(x)=\sum_{n \geq 0} \left[\frac{1}{4}(-1)^n+\frac{3}{2}(n+1)-\frac{3}{4}\right]x^n. $$ So the resulting formula is after some clean up $$ \frac{(-1)^n+6n+3}{4}. $$ I let you fill in the details which are mostly just algebraic manipulations (you can find very similar questions on the topic on this site as well, for example Using partial fractions to find explicit formulae for coefficients?).

Answer 2

Case.(1) $n=2k$ is even:

If $x_3=0$, then it is $x_1+x_2=n$, so $x_1$ can take $0,2,4,...,2k$.

If $x_3=1$, then it is $x_1+x_2=n-1$, so $x_1$ can take $0,2,4,...,2k-2$.

If $x_3=2$, then it is $x_1+x_2=n-2$, so $x_1$ can take $0,2,4,...,2k-2$.

So totally, $k+1+k+k=3k+1=\frac{3n}{2}+1$

Case.(2) $n=2k-1$ is odd:

If $x_3=0$, then it is $x_1+x_2=n$, so $x_1$ can take $0,2,4,...,2k-2$.

If $x_3=1$, then it is $x_1+x_2=n-1$, so $x_1$ can take $0,2,4,...,2k-2$.

If $x_3=2$, then it is $x_1+x_2=n-2$, so $x_1$ can take $0,2,4,...,2k-4$.

So totally, $k+k+k-1=3k-1=\frac{3(n+1)}{2}-1$

Answer 3

Continuing from your generating function

$$ f(x) = (1+x^2+x^4+\cdots) (1+x+x^2+\cdots) (1+x+x^2) $$

$$ f(x) = \left(\sum_{i=0}^\infty x^{2i} \right) \left(\sum_{j=0}^\infty x^j \right) (1+x+x^2) $$

When multiplying the first two terms, to find the coefficient of $x^k$ which is a sum of $x^{2i} x^j = x^k$ terms, we need the number of solutions to $2i+j=k, i \geq 0, j \geq 0$. Any solution to $0 \leq 2i \leq k$ gives a solution with $j=k-2i$. The count is $\left\lfloor \frac{k}{2} \right\rfloor + 1$.

$$ f(x) = \left(\sum_{k=0}^\infty \left(\left\lfloor \frac{k}{2} \right\rfloor +1\right) x^k \right) (1+x+x^2) $$

That is, $$ f(x) = (1+x+2x^2+2x^3+3x^4+3x^5+4x^6 +\cdots) (1+x+x^2) $$

Now multiplying in the $(1+x+x^2)$ gives

$$ f(x) = 1+2x+\sum_{n=2}^\infty \left(\left\lfloor \frac{n}{2}\right\rfloor+1 + \left\lfloor \frac{n-1}{2}\right\rfloor +1 + \left\lfloor \frac{n-2}{2} \right\rfloor + 1\right) x^n $$

Also for any integer $n$, $\left\lfloor \frac{n-1}{2} \right\rfloor + \left\lfloor \frac{n-2}{2} \right\rfloor = n-2$, so

$$ f(x) = 1 + 2x + \sum_{n=2}^\infty \left(n + \left\lfloor \frac{n}{2} \right\rfloor + 1\right) x^n $$

Since the first two terms do match the general expression,

$$ f(x) = \sum_{n=0}^\infty \left(n+\left\lfloor \frac{n}{2} \right\rfloor +1\right) x^n $$ $$ f(x) = 1+2x+4x^2+5x^3+7x^4+8x^5+10x^6+\cdots $$

The answer is then $n + \left\lfloor \frac{n}{2} \right\rfloor +1$. In other words, $\frac{3n}{2}+1$ if $n$ is even, or $\frac{3n+1}{2}$ if $n$ is odd.