How many solutions are there to the equation?

Question

I need to find the number of solutions in positive integers to the following equation:

$$x_1 + x_2 + x_3 + x_4 = 19$$

where $x_2 \neq 2x_3$ and $x_1 \neq x_2$

I know to solve the cases like $x_1 \ge 2x_3$, but I don't understand how to do the jump from this inequality to the case where they're not equal.

Any hint or guide would be much appreciated!

Answer 1

A generating function approach. We start with the number of solutions of \begin{align*} &\color{blue}{x_1+x_2+x_3+x_4=19}\tag{1}\\ &\color{blue}{x_1,x_2,x_3,x_4\geq 1} \end{align*} We represent the solutions of a variable $x_j\geq 1, 1\leq j\leq 4$ as generating function for $x_j$ which is \begin{align*} z+z^2+z^3+\cdots=\frac{z}{1-z} \end{align*} Using the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series, the number of solutions of (1) is \begin{align*} [z^{19}]\left(\frac{z}{1-z}\right)^4&=[z^{15}]\frac{1}{(1-z)^4}=\binom{-4}{15}(-1)^{15}\color{blue}{=816} \end{align*}

Condition $x_2\ne 2x_3$:

• We respect this condition by subtracting from (1) all solutions with $\color{blue}{x_2=2x_3}$. This gives \begin{align*} \color{blue}{x_1+3x_3+x_4=19}\tag{2} \end{align*} A generating function for $3x_3$ is $z^3+z^6+\cdots=\frac{z^3}{1-z^3}$ The number of positive solutions of (2) is \begin{align*} [z^{19}]\left(\frac{z}{1-z}\right)^2\left(\frac{z^3}{1-z^3}\right)=[z^{14}]\frac{1}{(1-z)^2}\,\frac{1}{1-z^3}\color{blue}{=45} \end{align*}

Condition $x_1\neq x_2$:

• We respect this condition by subtracting from (1) all solutions with $x_1=x_2$. This gives \begin{align*} \color{blue}{2x_2+x_3+x_4=19}\tag{3} \end{align*} The number of positive solutions of (3) is \begin{align*} [z^{19}]\frac{z^2}{1-z^2}\left(\frac{z}{1-z}\right)^2=[z^{15}]\frac{1}{(1-z)^2}\,\frac{1}{1-z^2}\color{blue}{=72} \end{align*}

Conditions $x_2\ne 2x_3$ and $x_1\neq x_2$:

• In (2) and (3) we did some overcounting, since we counted $x_2=2x_3$ and $x_1= x_2$ twice. We have to compensate this by subtracting once the number of solutions of (1) with $x_1=x_2=2x_3$, which gives \begin{align*} \color{blue}{5x_3+x_4=19}\tag{4} \end{align*} The number of positive solutions of (4) is \begin{align*} [z^{19}]\frac{z^5}{1-z^5}\,\frac{z}{1-z}=[z^{14}]\frac{1}{1-z^5}\,\frac{1}{1-z}\color{blue}{=3} \end{align*}

Combining (1) to (4) we find the number of wanted solutions is \begin{align*} \color{blue}{816-45-72+3=702} \end{align*}