1
$\begingroup$

What is the number of solutions of $$x_1+x_2+x_3+x_4+x_5+x_6=19$$ if every $x_i \ge 2$ and all $x_i$ are integers?

I know how to compute the number of solutions when every $x_i \geq 0$, but how do I do this for $x_i\geq 2$?

$\endgroup$
4
$\begingroup$

Hint: Let $x_i = y_i+2 \to y_1+y_2+y_3+y_4+y_5+y_6 = 7, y_i \in \mathbb{Z_{\geq0}}$. The number of solutions to this and then the original equation is quite well-known. In fact, it is: $\binom{7+6-1}{6-1}= \binom{12}{5}$.

$\endgroup$
2
  • $\begingroup$ How it is done I have no idea : ( $\endgroup$ – Pham kim hong Jan 14 '15 at 13:46
  • $\begingroup$ See here for the partition function and then use combinatorics to find the number of ways to order each partition. $\endgroup$ – Eleven-Eleven Jan 14 '15 at 13:56
1
$\begingroup$

For each $x_i$ on the left hand side, put $x_i= y_1 + 2,\;\;y_i \geq 0.\,$. Then ($y_i = x_i-2$.

That gives you the equation $$(x_1 -2) + (x_2-2) + \cdots +(x_6 - 2) = 19 - (6\cdot 2)$$ $$ = y_1 + y_2+y_3+y_4+y_5+y_6 = 19 - (2\cdot 6) = 7$$

Now use the stars-and-bars (Theorem 2) for the number of non-negative solutions:

For any pair of natural numbers $n$ and $k,$ the number of distinct $k$-tuples of non-negative integers whose sum is $n$ is given by the binomial coefficient $$\binom{n + k - 1}{n}.$$

Here, we have $k = 6$ and $n = 7$, which means the number of non-negative solutions to the equation is given by: $$\binom{7+6-1}{7} = \binom{12}{7} = \binom{12}{5} = \dfrac{12!}{7!5!} = 792$$

$\endgroup$
1
  • $\begingroup$ Note that $$\binom{12}{7} = \dfrac{12!}{7!5!} = \binom{12}{5}$$ $\endgroup$ – amWhy Jan 14 '15 at 14:12
0
$\begingroup$

Elaborating on the idea that $x_i=y_i+2$

You are looking for the number of integer partitions with six summands. We know there are 15 ways of partitioning the number 7 by the partition function Listing them out as $6$-tuples yields

$$(7,0,0,0,0,0), (6,1,0,0,0,0)$$ $$(5,1,1,0,0,0),(5,2,0,0,0,0)$$ $$(4,1,1,1,0,0),(4,2,1,0,0,0)$$ $$(4,3,0,0,0,0),(3,1,1,1,1,0)$$ $$(3,2,1,1,0,0),(3,2,2,0,0,0)$$ $$(3,3,1,0,0,0),(2,1,1,1,1,1)$$ $$(2,2,1,1,1,0),(2,2,2,1,0,0)$$

(Note there are only 14 here but $\pi(7)=15$. This is because the last partition is $(1,1,1,1,1,1,1),$ which is a $7$-tuple, not a $6$-tuple.)

Now each of these $6$-tuples can be counted accordingly. For example then number of ways to write $(3,2,2,0,0,0)$ is $\frac{6!}{2!3!}$ since 2 occurs twice and $0$ occurs 3 times in the tuple. Applying this to all 14 partitions yields

$$6!\left(\frac{2}{5!}+\frac{4}{4!}+\frac{1}{3!}+\frac{6}{2!3!}+\frac{1}{2!2!}\right)=792$$


$\endgroup$

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.