2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Then the number of solutions would be ${2n+1\choose 1}=2n+1$ $\endgroup$ – Yos Jun 29 '18 at 12:43
  • 1
    $\begingroup$ @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!) $\endgroup$ – Connor Harris Jun 29 '18 at 13:40
  • $\begingroup$ @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. $\endgroup$ – Yos Jun 29 '18 at 13:44
  • 1
    $\begingroup$ It's the same formula - he's just expanded the binomial coefficient. The answer $2n+1$ is false though $\endgroup$ – asdf Jun 29 '18 at 13:46
  • $\begingroup$ oh I noticed the mistake it's ${2n+2\choose 2n}=(2n+1)(n+1)$ $\endgroup$ – Yos Jun 29 '18 at 13:55

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.