1

Find the number of integer solutions of the equation $ x_{1}+x_{2}+...+x_{6}=7, \text{ with } 0\leq x_{i} \leq 2,i=1,...,6 $ .I found that it has $\binom{12}{7}-5\binom{9}{4} $ solutions..Could you tell me if my result is right?

evinda
  • 7,823
  • 1
    How did you get the result? If you write an outline of the path to your solution, we can probably tell whether or not it is the right approach. – Ragnar Jan 27 '14 at 15:48
  • 2
    http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle is a good approach anyway. Or you could calculate the number of possibilities for each distribution (the number of zeros, ones and twos). – Ragnar Jan 27 '14 at 15:48
  • I did it like that: $|A|=\binom{12}{7}-|UA_{i}|$,where $|UA_{i}|=\sum_{k=1}^{6}(-1)^{k-1}\sum_{J \subseteq [n],|J|=k}|\cap A_{i}|$ ,and I found that the latter is equal to $5\binom{9}{4}$,so
    $A=\binom{12}{7}-5\binom{9}{4}$ .But,in my textbook,there is an other solution.Could you tell me if my result is right?     – evinda Jan 27 '14 at 15:57

4 Answers4

1

I obtained a different result. You can use generating functions. This approach relies in multiplying polynomials (or power series) and then looking at the right coefficient (in this case $7$). It is not too hard.

Since each variable may have only $0,1,2$ elements. We need to multiply:

$$ (1+x+x^2)(1+x+x^2)...(1+x+x^2) = (1+x+x^2)^6 = \sum_{k_1+k_2+k_3=6} \frac{6!}{k_1!k_2!k_3!}x^{k_2+2k_3}$$

Now, can we find the coefficient of $x^7$ in that expression (note the $k_i$ are just integers between $0$ and $6$). We know $k_2+2k_3=7$.

Therefore, we need all the 3-tuples satisfying $$ k_1+k_2+k_3=6 $$ $$ k_2+2k_3=7 $$ and the solutions are $$ (k_1,k_2,k_3) \in \{ (2,1,3),(1,3,2),(0,5,1) \} $$ Thus, the desired coefficient is $$ \frac{6!}{2!1!3!} + \frac{6!}{1!3!2!} + \frac{6!}{0!5!1!} = \frac{6!}{3!}+\frac{6!}{5!} =126$$

Is this the result in your textbook? I might have messed up.

Mauricio Tec
  • 2,624
1

I would say your result is incorrect. The answer I came up with is 126 and your result evaluates to 162.

You are essentially looking for partitions of 7 with the restrictions that you can not have more than 6 numbers, the numbers must be between 0 and 2 inclusive, and (unlike partitions) the order of the elements matters. From the 15 possible partitions, there are only 3 that meet the stated criterion: 2+1+1+1+1+1, 2+2+1+1+1+0 and 2+2+2+1+0+0.

For each of these, you just need to count the number of possible permutations using $\dfrac{6!}{n_0! n_1! n_2!}$ where $n_i$ refers to the number of times you use $i$ in the sequence.

John Habert
  • 4,001
1

if in your solution there are k '2', there are 7 - 2 * k '1'. There has to be at least 1 '2' and maximum 3 '2' so k =1 or 2 or 3

$\sum_{k=1}^3 \binom{6}{k} \binom{6-k}{7-2k}$ which can be done by hand

Note : this is related to the answer with $(1 + x + x^2)^6$

Thomas
  • 1,124
1

Hint: Use the inclusion/exclusion principle.

First consider the case with all $x_i$>=0. Then we get $\binom{12}{5} $ .

Next consider exactly one $x_i$>2.From this we get $6\binom{9}{5}$ .

Next consider exactly two $x_i$s such that $x_i$>2. From this we get $\binom{6}{5}$$\binom{6}{2}$.

Since no 3 $x$s' can be greater than 2 I hope you can guess what the answer is

Heisenberg
  • 3,227