# How many natural solutions to $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 24$ if $x_1 + x_2 + x_3 > x_4 + x_5 + x_6$?

Here's a problem in my combinatorics textbook:

Find how many solutions exist to the following equation over the natural numbers

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

if

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

I think that the problem can be solved with a generating function. First because $x_1+x_2+x_3>x_4+x_5+x_6$ then we can deduce that $x_1+x_2+x_3=x_4+x_5+x_6+y$ where $y\ge1$ because by problem definition we're dealing with natural numbers. Thus we get the following: $2x_4+2x_5+2x_6+y=24$ which translates into the following function: $$(1+x^2+x^4+...)^3(x+x^2+x^3+...)=(1+x^2+x^4+...)^3x(1+x+x^2+x^3+...)=$$ $$=\frac{1}{(1-x^2)^3}*\frac{1}{1-x}$$ now we need to find the coefficient of $x^{23}$. Is the correct solution so far and if yes is there any closed form of the generating function or any other tip to find the coefficient or I should just open the brackets by brute force?

• Your approach with the generating function has a flaw that you are implicitely assuming that $x_1=x_4$, $\ldots$, $x_3=x_6$. This may not happen. Only the sums of three are equal. – Sungjin Kim Sep 20 '16 at 19:21

This problem has a nice symmetry.

Total number of solutions without restriction: $\binom {29} 5=118755$.

Number of solutions with $x_1+x_2+x_3 = x_4+x_5+x_6$ : $\binom {14} 2^2=91^2=8281$.

Number of solutions with $x_1+x_2+x_3 > x_4+ x_5 + x_6$ : $\frac {118755-8281}2=55237$.

This counting is based on the following analysis: Define $$S=\{(x_1,\ldots, x_6): x_i\textrm{'s are natural }, x_1+ \cdots + x_6 = 24\}.$$ Also, define $$A=\{ (x_1,\ldots, x_6) \in S: x_1+x_2+x_3 > x_4+x_5+x_6\},$$ and

$$B=\{(x_1,\ldots, x_6) \in S : x_1+x_2+x_3 < x_4+x_5+x_6\}$$ Then $A$ and $B$ are bijective via changing the role of $x_1$, $x_2$, $x_3$ by $x_4$, $x_5$, $x_6$.

Define $$C=\{(x_1,\ldots, x_6) \in S: x_1+x_2+x_3=x_4+x_5+x_6\}.$$ Then we have $S=A\cup B\cup C$. Since $A$ and $B$ are bijective, they have the same cardinality, i.e. $|A|=|B|$. To solve for $|A|$, we use $$|A|=\frac{|S|-|C|}2.$$

• Nice! 2 questions: 1) why is $\binom{14}{2}$ set to the power of $2$? 2) why do we need to divide the $118755-8281$ by $2$? – Yos Sep 20 '16 at 19:04
• 1) power of 2 is because we consider solutions satisfying $x_1+x_2+x_3=12$, and $x_4+x_5+x_6=12$. – Sungjin Kim Sep 20 '16 at 19:08
• 2) dividing by 2 is because the number of solutions satisfying $x_1+x_2+x_3> x_4+x_5+x_6$ is equal to the number of solutions satisfying $x_1+x_2+x_3 < x_4+ x_5 + x_6$. – Sungjin Kim Sep 20 '16 at 19:09
• Thank you for the answer! But shouldn't the number of solutions without restrictions be $\binom{29}{5}$? – Yos Sep 20 '16 at 19:25
• Since your question is over natural numbers. If you meant to include $0$ in the natural numbers, then you are right about $\binom {29}5$. – Sungjin Kim Sep 20 '16 at 19:26