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)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:
- As we've previous seen on the Combinations of Elements in Multisets page, any submultiset $B$ of $A$ must be of the following form:
- Each $k$-combination will correspond to a submultiset $B$ of $A$ whose repetition numbers satisfies the equation:
- 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)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)