Restricted Nonnegative Integral Solutions to Simple Equation

Restricted Nonnegative Integral Solutions to Simple Equation

Recall from the Combinations of Elements in Multisets with Infinite Repetition Numbers that if $A$ is a multiset with $n$ distinct elements $x_1, x_2, ..., x_n$, all of which have $\infty$ repetition numbers then the number of $k$-combinations of elements from $A$ is $\displaystyle{\binom{k + n - 1}{k} = \binom{k + n - 1}{n - 1}}$ which as we noted on the Nonnegative Integral Solutions to Simple Equations page, corresponding to the number of nonnegative integral solutions $b_1 \geq 0$, $b_2 \geq 0$, …, $b_n \geq 0$ to the equation $b_1 + b_2 + ... + b_n = k$.

We recently saw on the $Combinations of Elements in Multisets with Finite Repetition Numbers that if$A$is multiset with$n$distinct elements$x_1, x_2, ..., x_n$, all of which have finite repetition numbers then the number of$k$-combinations of elements from$A$can be obtained The Inclusion-Exclusion Principle. As a consequence, we can now determine the number of nonnegative integral solutions to simple equations of the form$b_1 + b_2 + ... + b_n = k$where$b_1, b_2, ..., b_n$can be restricted even more. In particular, the number of$k$-combinations of elements in$A = \{ r_1 \cdot x_1, r_2 \cdot x_2, ..., r_n \cdot x_n \}$is the number of integral solutions to$b_1 + b_2 + ... + b_n = k$that now satisfy all of the inequalities:$0 \leq b_1 \leq r_1$,$0 \leq b_2 \leq r_2$, …,$0 \leq b_n \leq r_n. For example, consider the following equation: (1) \begin{align} \quad b_1 + b_2 + b_3 = 13 \end{align} Suppose that we want to count the number of integral solutions to this equation that satisfy0 \leq b_1 \leq 10$,$0 \leq b_2 \leq 7$, and$0 \leq b_3 \leq 5$. The number of integral solutions to this problem is precisely the number of$13$-combinations from elements in the set$Agiven by: (2) \begin{align} \quad A = \{ 10 \cdot x_1, 7 \cdot x_2, 5 \cdot x_3 \} \end{align} LetA^{+}$be the set of all possible$13$-combinations of elements from$A$without restrictions on the numbers of$x_1$,$x_2$, and$x_3$we can choose. Then$\displaystyle{\mid A^{+} \mid = \binom{13 + 3 - 1}{3} = \binom{15}{3} = 455}$. Let$A_1$be the set of all$13$-combinations where$b_1 \geq 11$. The number of$13$-combinations where$b_1 \geq 11$is equal to$\binom{2 + 3 - 1}{2} = \binom{4}{2} = 6$, so$\mid A_1 \mid = 13$. Let$A_2$be the set of all$13$-combinations where$b_2 \geq 8$. The number of$13$-combinations where$b_2 \geq 8$is$\binom{5 + 3 - 1}{5} = \binom{7}{5} = 21$, so$\mid A_2 \mid = 21$. Let$A_3$be the set of all$13$-combinations where$b_3 \geq 6$. The number of$13$-combinations where$b_3 \geq 6$is$\binom{7 + 3 - 1}{7} = \binom{9}{7} = 36$, so$\mid A_3 \mid = 36$. It should be noted that$\mid A_1 \cap A_2 \mid = \mid A_1 \cap A_3 \mid = \mid A_2 \cap A_3 \mid = \mid A_1 \cap A_2 \cap A_3 = 0$since it is impossible for two or more of inequalities:$b_1 \geq 11$,$b_2 \geq 8$,$b_3 \geq 6$to hold for any$13$-combination of elements from$A. By the inclusion-exclusion principle we have that: (3) \begin{align} \quad \mathrm{number \: of} \: k-\mathrm{combinations} = \mid A^{+} \mid - \left ( \mid A_1 \mid + \mid A_2 \mid + \mid A_3 \mid \right ) + \left ( \mid A_1 \cap A_2 \mid + \mid A_1 \cap A_3 \mid + \mid A_2 \cap A_3 \mid \right ) - \mid A_1 \cap A_2 \cap A_3 \mid \\ \quad \mathrm{number \: of} \: k-\mathrm{combinations} = 455 - (13 + 21 + 36) + (0 + 0 + 0) - 0 = 385 \end{align} Therefore, for0 \leq b_1 \leq 10$,$0 \leq b_2 \leq 7$, and$0 \leq b_3 \leq 5$there are exactly$385$integral solutions to the equation$b_1 + b_2 + b_3 = 13\$.