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 satisfy $0 \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 $A$ given by:

(2)

\begin{align} \quad A = \{ 10 \cdot x_1, 7 \cdot x_2, 5 \cdot x_3 \} \end{align}

Let $A^{+}$ 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, for $0 \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$.