4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sungjin Kim Sep 20 '16 at 19:21
4
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Yos Sep 20 '16 at 19:04
  • 1
    $\begingroup$ 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$. $\endgroup$ – Sungjin Kim Sep 20 '16 at 19:08
  • 1
    $\begingroup$ 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$. $\endgroup$ – Sungjin Kim Sep 20 '16 at 19:09
  • $\begingroup$ Thank you for the answer! But shouldn't the number of solutions without restrictions be $\binom{29}{5}$? $\endgroup$ – Yos Sep 20 '16 at 19:25
  • $\begingroup$ 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$. $\endgroup$ – Sungjin Kim Sep 20 '16 at 19:26

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.