# Finding number of restricted integer solutions to equation using multinomial theorem

How can I solve the diophantine equation

$$x_1 +x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 30,$$

where $x_1, x_2, x_3, x_4, x_5, x_6, x_7$ can take the values $0,2,3,4,5$?

I am having problems in solving this one. The expansion is getting very big.

I need the number of solutions of this equation.

Thanks

• Do you need all the solutions, or one solution? – Jimmy R. Feb 19 '14 at 8:50
• I need number of solutions. – AJ_ Feb 19 '14 at 8:53
• As you need the number of solutions, this is about combinatorics, not about diophantine equations. – Marc van Leeuwen Feb 19 '14 at 9:05
• @MarcvanLeeuwen, Oops, that was my edit. Thanks for revising that! – Christoph Feb 19 '14 at 9:15

By setting $x_i=5-y_i$, we can instead solve $$(5-y_1)+(5-y_2)+\cdots+(5-y_7)=30$$ for $y_1,\ldots,y_7 \in \{0,1,2,3,5\}$. This is equivalent to $$y_1+y_2+\cdots+y_7=5.$$

From here, the possible multisets of $y$-values are:

• $\{5,0,0,0,0,0,0\}$, enumerated by $\binom{7}{1,6}=7$,
• $\{3,2,0,0,0,0,0\}$, enumerated by $\binom{7}{1,1,5}=42$,
• $\{3,1,1,0,0,0,0\}$, enumerated by $\binom{7}{1,2,4}=105$,
• $\{2,2,1,0,0,0,0\}$, enumerated by $\binom{7}{2,1,4}=105$,
• $\{2,1,1,1,0,0,0\}$, enumerated by $\binom{7}{1,3,3}=140$,
• $\{1,1,1,1,1,0,0\}$, enumerated by $\binom{7}{5,2}=21$.

This gives $420$ possibilities.

Assume none of the $x_i, i=1,\ldots,7$ is equal to $5$. Then the highest you can achieve is $7\times4=28$ which is $2$ less than the desired. So you need at least two $5$'s. Without loss of generality let $x_6=x_7=5$ (you can choose whichever 2 $x_i$ you want). Then the above equation reduces to $$x_1+x_2+x_3+x_4+x_5=20,$$ with $x_i \in {0,2,3,4,5}$. No you can treat different cases based on the minimum (or maximum) of the $x_i$ as @Rebecca's treatment (which is by the way much more elegant). For example

1.Case: $x_1=x_2=0$. No such solution possible.

2.Case: $x_1=0$.Then $x_2=x_3=x_4=x_5=5$. So the first solution is: $6$ fives and $1$ zero. You have $7$ such solutions (permutations).

3.Case: $x_1=2$. Then you have that $$x_2+x_3+x_4+x_5=18,$$ and you have one possibility to solve, which is $x_2=3, x_3=x_4=x_5=5$. So the solution consists of $5$ fives, $1$ three and $1$ two. You have $7\times6=42$ such solutions. There are no other solutions in which 2 appears.

4.Case: $x_1=3$. Then you have that $$x_2+x_3+x_4+x_5=17$$ and you have two possibilities to solve. The first is three fives and a two (but you already had it, so it is rejected. Remember that we take cases according to minimum and 2 as minimum is already treated above) and the other is $3$ fours and $1$ five. So the solution consists of $3$ fives, $3$ fours and $1$ three. You have $7\times \dbinom{6}{3}=140$. (choose one $x$ to be equal to 3 (you have $7$ such possibilities and choose $3$ out of the remaining $6$ to be equal to $5$ (you have $\dbinom{6}{3}=20$ such possibilities).

5.Case: $x_1=x_2=3$.Then you have that $$x_3+x_4+x_5=14$$ and you have one possibility to solve which is $x_3=4,x_4=x_5=5$. So the solution consists of $4$ fives, $2$ fours and $2$ threes. There are $\dbinom{7}{2}\times\dbinom{5}{2}=210$ such solutions. (choose two $x_i$ to be equal to 3 (you have $\dbinom{7}{2}=21$ such possibilities and choose $2$ out of the remaining $5$ to be equal to $4$ (you have $\dbinom{5}{2}=10$ such possibilities. set the remaining two to be equal to 5).

6.Case: $x_1=x_2=x_3=3$.Then you have that $$x_4+x_5=11$$ which is impossible. So no more cases where a $3$ appears are possible.

7.Case: $x_1=4$. Then you have that $$x_2+x_3+x_4+x_5=16$$ and all the $x_i$ must be greater or equal than $4$. So the only possible solution is $x_2=x_3=x_4=x_5=4$. So the solution consists of $2$ fives and $5$ fours. You have (in the same manner as above) $\dbinom{7}{2}$ such solutions.

So to sum up. List of possible solutions (ordered vector and number of such vectors)

1. $(0,5,5,5,5,5,5)$. $7$ such solutions

2. $(2,3,5,5,5,5,5)$. $42$ such solutions

3. $(3,4,4,4,5,5,5)$. $140$ such solutions

4. $(3,3,4,5,5,5,5)$. $210$ such solutions

5. $(4,4,4,4,4,5,5)$. $21$ such solutions

which gives 420 solutions.