# Thread: Number of solutions to linear equation

1. ## Number of solutions to linear equation

How many solutions are there to the equation x1+x2+x3+x4 = 10, where for every i, 1 <= xi <= 4 ?

2. One way is to find the coefficient of $x^{10}$ in the expansion of $(x^4+x^3+x^2+x)^4$, which can be done in WolframAlpha. I would not say that this restatement makes the counting easier; it just reduces the problem to a well-known question for which automatic tools exist.

3. Can you solve it without that trick? I mean without using automatic tools, let's say its a question on the test, what would you do then?:P

4. You could also try brute force. Consider the following table. Let $a_{i,j}$ be the element at row $i$ and column $j$. We want $a_{i,j}$ be the number of solutions of $x_1+\dots+x_i=j$ where $1\le x_k\le 4$ for all $1\le k\le i$.

$
\begin{array}{c|cccccccccc}
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\hline
1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
2 & 0 & 1 & 2 & 3 & 4 & 3 & 2 & 1 & 0 & 0\\
3 & 0 & 0 & 1 & & & \mathbf{10} & \mathbf{12} & \mathbf{12} & \mathbf{10} & \\
4 & 0 & 0 & 0 & 1 & & & & & & \mathbf{44}
\end{array}
$

The non-bold elements of the table are computed directly. Next, for $i>1$ and $j>4$, we have $a_{i,j}=a_{i-1,j-4}+a_{i-1,j-3}+a_{i-1,j-2}+a_{i-1,j-1}$.

5. OK, its nice and all, I have tried to solve it in a different way that seems so correct but doesn't work and I'm confused. Look what I did:

because xi >= 1 we can change variable to xi = yi + 1 then we have y1 + 1 + y2 + 1 + y3 + 1 + y4 + 1 = 10 => y1+y2+y3+y4= 6. now we want to find the number of solutions to y1+y2+y3+y4= 6 where for every i, 0<=yi<=4.
for getting the number of solutions to the latter equation where yi >=0, we can use the formula for dividing 6 identical objects into 4 different boxes it's |U|= nCr(4-1+6,4-1)=84, the size of our universe. now we can use the inclusion & exclusion in order to find number of solutions where y1 >= 5 or y2 >= 5 or y3 >= 5 or y4 >= 5, there are only 16 such solutions. so the final answer is 84-16=68. but the answer is incorrect. where is my mistake? I cant figure it out, just looking for it for hours.

6. oh, just one little detail that makes a big different, it should be yi <=3 instead of 4, but thanks!

7. because xi >= 1 we can change variable to xi = yi + 1 then we have y1 + 1 + y2 + 1 + y3 + 1 + y4 + 1 = 10 => y1+y2+y3+y4= 6. now we want to find the number of solutions to y1+y2+y3+y4= 6 where for every i, 0<=yi<=4.
It should be, 0 <= y_i <= 3.

Your method is otherwise correct. I was just looking into it at this thread. Let s be the sum of all $y_i$'s, namely, 6, and let m be the maximum of $y_i$'s, namely, 3. What makes it easy to subtract the number of variants where some $y_i>m$ is that $s\le 2m+1$. In this case, when $y_1=m+1$, $y_2+y_3+y_4=s-(m+1)\le m$, so the restriction that $y_i\le m$ does not have to be taken into account and the number of solutions of $y_2+y_3+y_4=s-(m+1)$ can be calculated by the general formula.

8. ## You don't need alpha for this one

Here is a way to get the coefficient of x^10 from the generating function. The ordinary power series generating function (as already noted) is

$f(x) = (x + x^2 + x^3 + x^4)^4$
$= x^4 (1 + x + x^2 + x^3)^4$
$=x^4 \left( \frac{1-x^4}{1-x} \right) ^4$
$=x^4 (1-x^4)^4 (1-x)^{-4}$
$=x^4 (1 -4x^4 + 6x^8 -4x^{12} + x^{16}) \sum_{i=0}^{\infty} \binom{4+i-1}{i} x^i$

Looking at the last equation, we can see the coefficient of x^10 is

$\binom{9}{3} - 4 \binom{5}{2}$

9. Hello, Ginsburg!

A slight variation of emarakov's solution . . .

$\text{How many solutions are there to the equation}$

. . $x_1+x_2+x_3+x_4 \:=\: 10\:\text{ where }1 \le x_i \le 4\,?$

. . $\begin{array}{ccc}
x_1,x_2,x_3,x_4 & \text{Permutations} \\ \hline \\[-4mm]
(1,1,4,4) & \frac{4!}{2!\,2!} \;=\;6 \\ \\[-3mm]
(1,2,3,4) & 4! \;\;=\;24 \\ \\[-3mm]
(1,3,3,3) & \frac{4!}{1!\,3!} \;=\;4 \\ \\[-3mm]
(2,2,2,4) & \frac{4!}{3!\,1!} \;=\;4 \\ \\[-3mm]
(2,2,3,3) & \frac{4!}{2!\,2!} \;=\;6 \\ \\[-4mm] \hline \\[-4mm]

10. By the Erdos principle, there is always a simple explanation for a simple answer

Ginsburg was quite close in an earlier post.

Number of solutions to

$x_1 + x_2 + x_3 + x_4 = 10$
with $1 \leq x_i \leq 4$

is the number of solutions to (substitue $y_i = x_i - 1$)

$y_1 + y_2 + y_3 + y_4 = 10 - 4 = 6$
with $0 \leq y_i \leq 3$

Number of solutions to

$y_1 + y_2 + y_3 + y_4 = 6$
with $0 \leq y_i$

is $\binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}$

We need to throw away solutions where one of $y_i \geq 4$.
For the case of $y_1 \geq 4$, let $z = y_1 - 4$, the number of solutions to

$z + y_2 + y_3 + y_4 = 6 - 4 = 2$

is $\binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$

Since exactly one of $y_i$ could be larger than 3 in any solution.
We have $4\binom{5}{3}$.

Subtracting invalid solutions, the number of possible solutions is:

$\binom{9}{3} - 4\binom{5}{3}$

Consistent with awkward's solution.

11. Originally Posted by snowtea
By the Erdos principle, there is always a simple explanation for a simple answer

Ginsburg was quite close in an earlier post.

Number of solutions to

$x_1 + x_2 + x_3 + x_4 = 10$
with $1 \leq x_i \leq 4$

is the number of solutions to (substitue $y_i = x_i - 1$)

$y_1 + y_2 + y_3 + y_4 = 10 - 4 = 6$
with $0 \leq y_i \leq 3$

Number of solutions to

$y_1 + y_2 + y_3 + y_4 = 6$
with $0 \leq y_i$

is $\binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}$

We need to throw away solutions where one of $y_i \geq 4$.
For the case of $y_1 \geq 4$, let $z = y_1 - 4$, the number of solutions to

$z + y_2 + y_3 + y_4 = 6 - 4 = 2$

is $\binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$

Since exactly one of $y_i$ could be larger than 3 in any solution.
We have $4\binom{5}{3}$.

Subtracting invalid solutions, the number of possible solutions is:

$\binom{9}{3} - 4\binom{5}{3}$

Consistent with awkward's solution.
And is consistent with a direct count!

CB

12. Originally Posted by CaptainBlack
And not consistent with a direct count!

CB
CB, I find 44 solutions, listed below. Do you differ with that list?

Code:
1	1	1	4	4
2	1	2	3	4
3	1	2	4	3
4	1	3	2	4
5	1	3	3	3
6	1	3	4	2
7	1	4	1	4
8	1	4	2	3
9	1	4	3	2
10	1	4	4	1
11	2	1	3	4
12	2	1	4	3
13	2	2	2	4
14	2	2	3	3
15	2	2	4	2
16	2	3	1	4
17	2	3	2	3
18	2	3	3	2
19	2	3	4	1
20	2	4	1	3
21	2	4	2	2
22	2	4	3	1
23	3	1	2	4
24	3	1	3	3
25	3	1	4	2
26	3	2	1	4
27	3	2	2	3
28	3	2	3	2
29	3	2	4	1
30	3	3	1	3
31	3	3	2	2
32	3	3	3	1
33	3	4	1	2
34	3	4	2	1
35	4	1	1	4
36	4	1	2	3
37	4	1	3	2
38	4	1	4	1
39	4	2	1	3
40	4	2	2	2
41	4	2	3	1
42	4	3	1	2
43	4	3	2	1
44	4	4	1	1

13. Originally Posted by awkward
CB, I find 44 solutions, listed below. Do you differ with that list?

Code:
1	1	1	4	4
2	1	2	3	4
3	1	2	4	3
4	1	3	2	4
5	1	3	3	3
6	1	3	4	2
7	1	4	1	4
8	1	4	2	3
9	1	4	3	2
10	1	4	4	1
11	2	1	3	4
12	2	1	4	3
13	2	2	2	4
14	2	2	3	3
15	2	2	4	2
16	2	3	1	4
17	2	3	2	3
18	2	3	3	2
19	2	3	4	1
20	2	4	1	3
21	2	4	2	2
22	2	4	3	1
23	3	1	2	4
24	3	1	3	3
25	3	1	4	2
26	3	2	1	4
27	3	2	2	3
28	3	2	3	2
29	3	2	4	1
30	3	3	1	3
31	3	3	2	2
32	3	3	3	1
33	3	4	1	2
34	3	4	2	1
35	4	1	1	4
36	4	1	2	3
37	4	1	3	2
38	4	1	4	1
39	4	2	1	3
40	4	2	2	2
41	4	2	3	1
42	4	3	1	2
43	4	3	2	1
44	4	4	1	1
It is a gross typo (or a time slip)it is consistent is what the post should say, and will do presently.

CB