# Count the number of integer solutions of a linear equation

What kind of approach can be used to solve this specific problem? An easy one if possible.

I thought about the Inclusion-Exclusion Principle; I think using generating functions will be more difficult.

Given that the variables $x_i$ are natural numbers.

Find how many solutions exist for the equation:

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 24$$

when given

$$x_1 + x_2 + x_3 > x_4 + x_5 + x_6$$

• I think this needs clarification. Are you assuming the $x_i$ are in some particular order? Non-ascending, maybe, or non-descending? Have you looked at the same problem for, smaller numbers than 24? – lulu Jul 7 '15 at 18:45
• Also, are they positive integers or nonnegative integers? – Ashkay Jul 7 '15 at 18:46
• True. I assumed they were nonnegative integers but I frequently assume things incorrectly. – lulu Jul 7 '15 at 18:46
• I edited. non-negative – idan di Jul 7 '15 at 18:56

Outline: Let $A$ be the number of solutions (in non-negative integers) with $x_1+x_2+x_3\gt x_4+x_5+x_6$. Let $B$ be the number of solutions with $x_1+x_2+x_3\lt x_4+x_5+x_6$. And let $T$ be the number of solutions with equality.

By symmetry $A=B$. We know the total number $N$ of solutions with no restriction. So $2A+T=N$ and therefore $A=\frac{N-T}{2}$.

Now we only need $T$. This is $W^2$, where $W$ is the number of solutions of $y_1+y_2+y_3=12$.

• wow, thanks. the speed you answered it . I thought its a very hard question. maybe my foundations not that strong – idan di Jul 7 '15 at 19:01
• You are welcome. Symmetry is our friend. – André Nicolas Jul 7 '15 at 19:35
• (Should C be T?) – user84413 Jul 7 '15 at 22:30
• Yes, thank you, fixed. – André Nicolas Jul 7 '15 at 22:48

Assuming that they are nonnegative integers:

The number of solutions to $x_1 + x_2 + x_3 = k$ is $\dbinom{k+2}{2}$ by the Stars and Bars approach.

Therefore, we can add up the number of ways for every combination of $k$ that works - if the first three add to $k$, the second three add to $24-k$. In addition, we let $k$ go from $13$ to $24$, so that the inequality holds.

Thus, the answer is $$\sum_{k=13}^{24} \dbinom{k+2}{2} \cdot \dbinom{26 - k}{2}$$

EDIT: The other answer is much better! But I'll leave this here.

• I do not agree that the other answer (mine) is better. They are different. Your procedure can be easily generalized, with sum of the first $k$ less than the sum of the last $l$.. Mine only deals with sum of first $k$ greater than the sum of the last $k$. – André Nicolas Jul 7 '15 at 20:02
• Haha, I come from a math contest background, so I always try to find ways to make the calculations as simple as possible. With problems like this, it's always best to exploit any symmetries. – Ashkay Jul 7 '15 at 20:06
• I also have a contest background, but for the last many years on the other side of the game, making up problems, marking. – André Nicolas Jul 7 '15 at 20:12
• Ooh, that's awesome. What contests do you write for? – Ashkay Jul 7 '15 at 20:15
• I should avoid specifics. Never IMO, but a national contest, an international one, and a regional much lower level one. – André Nicolas Jul 7 '15 at 20:20