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

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.

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.

• Then the number of solutions would be ${2n+1\choose 1}=2n+1$ – Yos Jun 29 '18 at 12:43
• @Yos Not quite. Remember (by the "stars-and-bars method") that the number of ordered partitions of $n$ items into $k$ bins is $\frac{(n+k-1)!}{n!(k-1)!}$, so you should have $\frac{(n+2)!}{n! 2!} \frac{(2n+1)!}{(2n)!1!} \frac{(2n+2)!}{(2n!)2!)}$, where each factor represents the number of solutions to one of the equations. (Note that this expression can be considerably simplified!) – Connor Harris Jun 29 '18 at 13:40
• @ConnorHarris I'm not familiar with the formula you posted. As far as I know there're ${n-1+k\choose k}$ solutions (over $\mathbb N\cup \{0\}$) to equation of type $x_1+x_2+\dots +x_n=k$ I'm not sure where you get the factorial. – Yos Jun 29 '18 at 13:44
• It's the same formula - he's just expanded the binomial coefficient. The answer $2n+1$ is false though – asdf Jun 29 '18 at 13:46
• oh I noticed the mistake it's ${2n+2\choose 2n}=(2n+1)(n+1)$ – Yos Jun 29 '18 at 13:55