[Math] How many integer solutions are there to $x_1+x_2+x_3+x_4+x_5 = 28$ with certain restraints

combinationscombinatorics

How many integer solutions are there to $x_1+x_2+x_3+x_4+x_5 = 28$ with:
a) $x_i \ge 0$?
b) $x_i > 0$?
c) $x_i \ge i (i = 1, 2, 3, 4, 5)?$

I know how I would count these, for example, a) I would start with one integer being 28, the rest 0, its combinations, and then subtract and distribute, but how do I count when the numbers start getting smaller and the distributions are difficult to keep track of? Is there an easy method to do this?

Best Answer

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the non-negative integers?

A particular solution to the equation in the non-negative integers corresponds to the placement of four addition signs in a row of $28$ ones. For instance, $$1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 + + 1 1 1 1$$ corresponds to the solution $x_1 = 9$, $x_2 = 8$, $x_3 = 7$, $x_4 = 0$, and $x_5 = 4$. Thus, the number of solutions of the equation in the non-negative integers is the number of ways four addition signs can be placed in a row of $28$ ones, which is $$\binom{28 + 4}{4} = \binom{32}{4}$$ since we must choose which four of the $32$ symbols (four addition signs and $28$ ones) will be addition signs.

In general, the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the non-negative integers is equal to the number of ways $k - 1$ addition signs can be inserted into a row of $n$ ones, which is $$\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$$ since we must choose which $k - 1$ of the $n + k - 1$ symbols ($n$ ones and $k - 1$ addition signs) will be addition signs or, alternatively, which $n$ of the symbols will be ones.

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the positive integers?

A particular solution of the equation in the positive integers corresponds to the placement of four addition signs in the $27$ spaces between successive ones in a row of $28$ ones. For instance, $$1 1 1 1 1 1 + 1 1 1 1 1 1 1 + 1 1 1 1 1 1 + 1 1 1 1 1 + 1 1 1 1$$ corresponds to the solution $x_1 = 6$, $x_2 = 7$, $x_3 = 6$, $x_4 = 5$, and $x_5 = 4$. Thus, the number of solutions of the equation in the positive integers is the number of ways four addition signs can be placed in the $27$ gaps between successive ones in a row of $28$ ones, which is $$\binom{27}{4}$$ In general, the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the positive integers is the number of ways $k - 1$ addition signs can be placed in the $n - 1$ gaps between successive ones in a row of $n$ ones, which is $$\binom{n - 1}{k - 1}$$

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the integers subject to the restraints $x_k \geq k$, $1 \leq k \leq 5$.

Hint: Let $y_k = x_k - k$, $1 \leq k \leq 5$. Substitute $y_k + k$ for $x_k$, $1 \leq k \leq 5$, then solve the resulting equation in the non-negative integers.