How many positive integer solutions are to a system of linear equations?

667 Views Asked by At

Given the linear system of equations: $$ \begin{cases} x_1 + x_2 + x_3 = n\\ x_1 + x_2 + x_3 + x_4 + x_5 = 3n\\ 2x_1 +2x_2 +2x_3 +x_4 +x_5 +3x_6 +3x_7 +3x_8 =10n \end{cases} $$ how many solutions are in $\mathbb N\cup\{0\}$?

The solution must not be using sum notation like $\sum y$.

I know how to find the number of solutions to the regular equations like $x_1+x_2+x_3+\dots=n$ but I'm not sure how to do this for a system of equations. I thought of substituting some $x$'s: $$ x_1 + x_2 + x_3 =3n - (x_4 + x_5)\\ x_4 +x_5=10n-2(x_1 +x_2 +x_3) -3(x_6 +x_7 +x_8)\\ \implies x_1 + x_2 + x_3=3n-(10n-2(x_1 +x_2 +x_3) -3(x_6 +x_7 +x_8))\\ \implies x_1+x_2+x_3+3(x_6+x_7+x_8)=7n \quad * $$ As far as I understand finding the number of solutions for the system is equivalent to finding the number of solutions to the equation *.

The only next step from here I can think of is using generating functions: $$ (1+x+x^2+\dots)^3(1+x^3+x^6+x^9+\dots)^3 $$ and we need to find the coefficient of $x^{7n}$.

From the closed form identities we have: $$ \sum_{k=0}^{\infty} {3-1+k\choose k}x^k\cdot \sum_{i=0}^{\infty} {3-1+i\choose i}x^{3i} $$ But I have no idea now how to find the coefficient of $7n$ from here and certainly not without using some kind of sum notation.

1

There are 1 best solutions below

6
On BEST ANSWER

This is more of a hint rather than a solution, but still:

You have $$x_1+x_2+x_3=n.$$ Substituting this into your second equation gives $$x_4+x_5=2n.$$ Substituting both in the third gives $$x_6+x_7+x_8=2n.$$

If I’ve understood correctly you can solve this new system of equations since each $x_i$ appears in exactly $1$ equation.