How many solutions are there to the equation x1+x2+x3+x4 = 10, where for every i, 1 <= xi <= 4 ?
One way is to find the coefficient of $\displaystyle x^{10}$ in the expansion of $\displaystyle (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.
You could also try brute force. Consider the following table. Let $\displaystyle a_{i,j}$ be the element at row $\displaystyle i$ and column $\displaystyle j$. We want $\displaystyle a_{i,j}$ be the number of solutions of $\displaystyle x_1+\dots+x_i=j$ where $\displaystyle 1\le x_k\le 4$ for all $\displaystyle 1\le k\le i$.
$\displaystyle
\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 $\displaystyle i>1$ and $\displaystyle j>4$, we have $\displaystyle a_{i,j}=a_{i-1,j-4}+a_{i-1,j-3}+a_{i-1,j-2}+a_{i-1,j-1}$.
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.
It should be, 0 <= y_i <= 3.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.
Your method is otherwise correct. I was just looking into it at this thread. Let s be the sum of all $\displaystyle y_i$'s, namely, 6, and let m be the maximum of $\displaystyle y_i$'s, namely, 3. What makes it easy to subtract the number of variants where some $\displaystyle y_i>m$ is that $\displaystyle s\le 2m+1$. In this case, when $\displaystyle y_1=m+1$, $\displaystyle y_2+y_3+y_4=s-(m+1)\le m$, so the restriction that $\displaystyle y_i\le m$ does not have to be taken into account and the number of solutions of $\displaystyle y_2+y_3+y_4=s-(m+1)$ can be calculated by the general formula.
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
$\displaystyle f(x) = (x + x^2 + x^3 + x^4)^4$
$\displaystyle = x^4 (1 + x + x^2 + x^3)^4$
$\displaystyle =x^4 \left( \frac{1-x^4}{1-x} \right) ^4$
$\displaystyle =x^4 (1-x^4)^4 (1-x)^{-4}$
$\displaystyle =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
$\displaystyle \binom{9}{3} - 4 \binom{5}{2}$
Hello, Ginsburg!
A slight variation of emarakov's solution . . .
$\displaystyle \text{How many solutions are there to the equation}$
. . $\displaystyle x_1+x_2+x_3+x_4 \:=\: 10\:\text{ where }1 \le x_i \le 4\,?$
. . $\displaystyle \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]
\text{Total:} & \qquad\quad 44 \end{array}$
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
$\displaystyle x_1 + x_2 + x_3 + x_4 = 10$
with $\displaystyle 1 \leq x_i \leq 4$
is the number of solutions to (substitue $\displaystyle y_i = x_i - 1$)
$\displaystyle y_1 + y_2 + y_3 + y_4 = 10 - 4 = 6$
with $\displaystyle 0 \leq y_i \leq 3$
Number of solutions to
$\displaystyle y_1 + y_2 + y_3 + y_4 = 6$
with $\displaystyle 0 \leq y_i$
is $\displaystyle \binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}$
We need to throw away solutions where one of $\displaystyle y_i \geq 4$.
For the case of $\displaystyle y_1 \geq 4$, let $\displaystyle z = y_1 - 4$, the number of solutions to
$\displaystyle z + y_2 + y_3 + y_4 = 6 - 4 = 2$
is $\displaystyle \binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$
Since exactly one of $\displaystyle y_i$ could be larger than 3 in any solution.
We have $\displaystyle 4\binom{5}{3}$.
Subtracting invalid solutions, the number of possible solutions is:
$\displaystyle \binom{9}{3} - 4\binom{5}{3}$
Consistent with awkward's solution.
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