Question

How many solutions are there to the equation
x1+x2+x3+x4+x5=21,
where xi, i=1,2,3,4,5, is a nonnegative integer such that
a)x1>=1?
b)xi>=2, for i=1,2,3,4,5?
c)0<=x1<=10?
d)0<=x1<=3, 1<=x2<4, and x3>=15?

Answer 1

Answer on question 36977 – Math – Discrete Mathematics

How many solutions are there to the equation $x1 + x2 + x3 + x4 + x5 = 21$, where $xi, i = 1,2,3,4,5$, is a nonnegative integer such that

a) $x1 \geq 1$?

b) $x_{i}\geq = 2,for i = 1,2,3,4,5?$

c) $0 \leq x1 \leq 10$?

d) $0 \leq x1 \leq 3, 1 \leq x2 < 4$, and $x3 \geq 15$?

Solution

a) Let $y_{1} = x_{1} - 1, y_{2} = x_{2}, y_{3} = x_{3}, y_{4} = x_{4}, y_{5} = x_{5}$. Substitute these into our equation

$$y_{1} + y_{2} + y_{3} + y_{4} + y_{5} = 20$$

And $y_{i}\geq 0$ for $i = 1,2,3,4,5$.

There is a 1-1 correspondence between the solutions and reordering of 20 ones and 4 zeros ($y_{1}$ is the number of ones before the first zero, $y_{2}$ the number of ones between the first and the second zero, and so on).

Hence the answer is

$$C_{20+4}^{4} = C_{24}^{4} = 10626.$$

b) Let $y_{1} = x_{1} - 2, y_{2} = x_{2} - 2, y_{3} = x_{3} - 2, y_{4} = x_{4} - 2, y_{5} = x_{5} - 2$. Substitute these into our equation

$$y_{1} + y_{2} + y_{3} + y_{4} + y_{5} = 21 - 10 = 11$$

Similarly to the previous case we get

$$C_{11+4}^{4} = C_{15}^{4} = 1365.$$

c) Using the sum rule, the number of solutions with $0 \leq x1 \leq 10$ added to the number of solutions with $x_{1} \geq 11$ gives all non-negative integer solutions. Thus the number of solutions with $0 \leq x1 \leq 10$ is

$$C_{25}^{4} - C_{14}^{4} = 12650 - 1001 = 11649.$$

d) Let $y_{1} = x_{1}, y_{2} = x_{2} - 1, y_{3} = x_{3} - 15, y_{4} = x_{4}, y_{5} = x_{5}$. Substitute these into our equation

$$y_{1} + y_{2} + y_{3} + y_{4} + y_{5} = 21 - 1 - 15 = 5,$$

where $y_{1} \leq 3, y_{2} \leq 2, y_{i} \geq 0, i = 3, 4, 5$. Similarly to the previous case we get

$$C_{9}^{4} - C_{6}^{4} - C_{7}^{4} = 76.$$

Answer: a) 10626; b) 1365; c) 11649; d) 76.