Question

Find the number of non-negative integral solutions of

$x_1 + x_2 + x_3 + 4x_4 = 20$.

Answer 1

536

Answer 2

The problem asks for the number of non-negative integral solutions of the equation $x_1 + x_2 + x_3 + 4x_4 = 20$.

Since $x_1, x_2, x_3, x_4$ must be non-negative integers, the term $4x_4$ can take values that are multiples of 4 and less than or equal to 20. This means $x_4$ can take values $0, 1, 2, 3, 4, 5$. We will consider each case for $x_4$.

The number of non-negative integral solutions for an equation of the form $y_1 + y_2 + \dots + y_k = n$ is given by the stars and bars formula: $\binom{n+k-1}{k-1}$.

Case 1: $x_4 = 0$

The equation becomes $x_1 + x_2 + x_3 = 20$. Here, $n=20$ and $k=3$.

Number of solutions = $\binom{20+3-1}{3-1} = \binom{22}{2} = \frac{22 \times 21}{2} = 11 \times 21 = 231$.

Case 2: $x_4 = 1$

The equation becomes $x_1 + x_2 + x_3 + 4(1) = 20 \implies x_1 + x_2 + x_3 = 16$. Here, $n=16$ and $k=3$.

Number of solutions = $\binom{16+3-1}{3-1} = \binom{18}{2} = \frac{18 \times 17}{2} = 9 \times 17 = 153$.

Case 3: $x_4 = 2$

The equation becomes $x_1 + x_2 + x_3 + 4(2) = 20 \implies x_1 + x_2 + x_3 = 12$. Here, $n=12$ and $k=3$.

Number of solutions = $\binom{12+3-1}{3-1} = \binom{14}{2} = \frac{14 \times 13}{2} = 7 \times 13 = 91$.

Case 4: $x_4 = 3$

The equation becomes $x_1 + x_2 + x_3 + 4(3) = 20 \implies x_1 + x_2 + x_3 = 8$. Here, $n=8$ and $k=3$.

Number of solutions = $\binom{8+3-1}{3-1} = \binom{10}{2} = \frac{10 \times 9}{2} = 5 \times 9 = 45$.

Case 5: $x_4 = 4$

The equation becomes $x_1 + x_2 + x_3 + 4(4) = 20 \implies x_1 + x_2 + x_3 = 4$. Here, $n=4$ and $k=3$.

Number of solutions = $\binom{4+3-1}{3-1} = \binom{6}{2} = \frac{6 \times 5}{2} = 3 \times 5 = 15$.

Case 6: $x_4 = 5$

The equation becomes $x_1 + x_2 + x_3 + 4(5) = 20 \implies x_1 + x_2 + x_3 = 0$. Here, $n=0$ and $k=3$.

Number of solutions = $\binom{0+3-1}{3-1} = \binom{2}{2} = 1$. (This solution is $x_1=0, x_2=0, x_3=0$).

To find the total number of non-negative integral solutions, we sum the solutions from all possible cases:

Total solutions = $231 + 153 + 91 + 45 + 15 + 1 = 536$.