Nonnegative Integral Solutions to Simple Equations

Nonnegative Integral Solutions to Simple Equations

Perhaps the simplest equations in $n$ variables $b_1, b_2, ..., b_n$ to solve are those of the form:

(1)
\begin{align} \quad b_1 + b_2 + ... + b_n = k \end{align}

The equation above represents an $n$-dimensional hyperplane in $\mathbb{R}^n$, and there are an infinite number of solutions. Namely, if we set $b_1 = b_2 = ... = b_{n-1} = 0$ and then set $b_n = p$ then the ordered $n$-tuple $(0, 0, ..., 0, k)$ is a solution to the equation above.

Now suppose that $b_1, b_2, ..., b_n$ and $k$ are all nonnegative integers. Solving the equation for nonnegative integral solutions (solutions for which each $b_1, b_2, ..., b_n$ is a nonnegative integer) above becomes a tad more difficult, but fortunately, the following theorem tells us that the process is not too difficult.

Theorem 1: The number of integral solutions to the equation $b_1 + b_2 + ... + b_n = k$ where $b_1, b_2, ..., b_n$ and $k$ are all nonnegative integers is equal to the number of $k$-combinations of a multiset $A$ with $n$ distinct elements that each have infinite repetition numbers, that is, $\binom{n + k - 1}{k}$.
  • Proof: Let $A$ be a multiset with $n$ distinct elements that each have an infinite repetition number. Then we have that $A$ is of the form:
(2)
\begin{align} \quad A = \{ \infty \cdot x_1, \infty \cdot x_2, ..., \infty \cdot x_n \} \end{align}
(3)
\begin{align} \quad B = \{ b_1 \cdot x_1, b_2 \cdot x_2, ..., b_n \cdot x_n \} \end{align}
  • Each $k$-combination will correspond to a submultiset $B$ of $A$ whose repetition numbers satisfies the equation:
(4)
\begin{align} \quad b_1 + b_2 + ... + b_n = k \end{align}
  • Conversely, each solution to the equation above yields a selection of $k$-elements contained in the multiset $A$.
  • Therefore the number of $k$-combinations of a multiset with $n$ distinct elements and whose repetition numbers are infinite is equal to the number of solutions to $b_1 + b_2 + ... + b_n = k$, but this number is simply $\binom{n + k - 1}{k}$. $\blacksquare$

For example, for $b_1$, $b_2$, and $b_3$ as nonnegative integers, suppose that we want to find the number of solutions to the equation:

(5)
\begin{align} \quad b_1 + b_2 + b_3 = 16 \end{align}

From Theorem 1 above, we see that this problem is equivalent to finding the number of $k=16$-combinations of a multiset with $n=3$ distinct elements and whose repetition numbers are infinite, and so the number of solutions to the equation above will be:

(6)
\begin{align} \quad \binom{n + k - 1}{k} = \binom{3+16-1}{16} = \binom{18}{16} = \frac{18!}{16! \cdot (18 - 16)!} = \frac{18!}{16! \cdot 2!} = 153 \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License