Trinomial Coefficient Identities

Recall from the Trinomial Coefficients page that if $r_1$, $r_2$, and $r_3$ are nonnegative integers and $n = r_1 + r_2 + r_3$ then the trinomial coefficient $\displaystyle{\binom{n}{r_1, r_2, r_3}}$ is defined to be:

(1)

\begin{align} \quad \binom{n}{r_1, r_2, r_3} = \frac{n!}{r_1! \cdot r_2! \cdot r_3!} \end{align}

We will now look an identity for $\binom{n}{r_1, r_2, r_3}$ in Theorem 1.

Theorem 1: If $r_1$, $r_2$, and $r_3$ are nonnegative integers and $n = r_1 + r_2 + r_3$ then $\displaystyle{\binom{n}{r_1, r_2, r_3} = \binom{n}{r_1} \cdot \binom{n - r_1}{r_2} \cdot \binom{n - r_1 - r_2}{r_3}}$.

Note that since $n = r_1 + r_2 + r_3$ that then $n - r_1 - r_2 = r_3$. The term $\binom{n - r_1 - r_2}{r_3} = \binom{r_3}{r_3} = 1$ does not need to be included in the product on the righthand side of the formula in Theorem 1 above, however, we include regardless.

Now recall previous that for any row $n$ on Pascal's triangle that we had the sum of the binomial coefficients along that row is equal to $2^n$, that is $\sum_{k=0}^{n} \binom{n}{k} = 2^n$. We will now see an analogous relationship for trinomial coefficients in the following theorem.

• Proof 1: Noting that $n = r_1 + r_2 + r_3$ so $n - r_1 - r_2 - r_3 = 0$, we algebraically simplify the righthand side of the equation:

(2)

\begin{align} \quad \binom{n}{r_1} \cdot \binom{n - r_1}{r_2} \cdot \binom{n - r_1 - r_2}{r_3} = \frac{n!}{r_1! (n - r_1)!} \cdot \frac{(n - r_1)!}{r_2! (n - r_1 - r_2)!} \cdot \frac{(n - r_1 - r_2)!}{r_3! (n - r_1 - r_2 - r_3)!} = \frac{n!}{r_1! \cdot r_2! \cdot r_3!} = \binom{n}{r_1, r_2, r_3} \quad \blacksquare \end{align}

• Proof 2: The trinomial coefficient $\binom{n}{r_1, r_2, r_3} = \frac{n!}{r_1! \cdot r_2! \cdot r_3!}$ represents the number of ways we can place $3$ distinct objects, $x$, $y$, and $z$ where there are $r_1$ many $x$'s, $r_2$ many $y$'s, and $r_3$ many $z$'s in $n = r_1 + r_2 + r_3$ many positions.

• The lefthand side of the equation says that out of the $n$ positions we first choose $r_1$ of them to place the $x$'s, then out of the $n - r_1$ remaining positions we choose $r_2$ of them to place the $y$'s, and out of the remaining $n - r_1 - r_2 = r_3$ remaining positions we choose all $r_3$ of them to place the $z$'s.

• We are counting the same thing on the lefthand side as we are on the righthand side. Therefore:

(3)

\begin{align} \quad \binom{n}{r_1, r_2, r_3} = \binom{n}{r_1} \cdot \binom{n - r_1}{r_2} \cdot \binom{n - r_1 - r_2}{r_3} \end{align}

Theorem 2: If $r_1$, $r_2$, and $r_3$ are nonnegative integers and $n = r_1 + r_2 + r_3$ then $\displaystyle{\sum_{r_1 + r_2 + r_3 = n} \binom{n}{r_1, r_2, r_3} = 3^n}$.

• Proof: The lefthand side of the equation counts the number of ways to distribute $r_1$ many $x$'s, $r_2$ many $y$'s, and $r_3$ many $z$'s between $n$ positions for all partitions of the $n$ many variables for which we assign $r_1$ of them to $x$, $r_2$ of them to $y$, and $r_3$ of them to $z$.

• The righthand side of the equation counts the number of ways to which we place either $x$, $y$ or $z$ (one of $3$ options) for each of the $n$ positions.

• Since both sides of the equation count the same thing, we have that:

(4)

\begin{align} \quad \displaystyle{\sum_{r_1 + r_2 + r_3 = n} \binom{n}{r_1, r_2, r_3} = 3^n} \quad \blacksquare \end{align}