Multinomial Coefficients

# Multinomial Coefficients

Recall from the Permutations of Elements in Multisets that if $A$ is a multiset containing $n$ distinct elements $x_1, x_2, ..., x_n$ and whose repetition numbers are $r_1, r_2, ..., r_n$ respectively then $A = \{ r_1 \cdot x_1, r_2 \cdot x_2, ..., r_n \cdot x_n \}$ and the total number of ($n$-)permutations of elements from $A$ will be:

(1)
\begin{align} \quad \binom{\sum_{i=1}^{n} r_i}{r_1, r_2, ..., r_n} = \frac{\left (\sum_{i=1}^{n} r_i \right )!}{\prod_{i=1}^{n} (r_i!)} = \frac{(r_1 + r_2 + ... + r_n)!}{r_1! \cdot r_2! \cdot ... \cdot r_n!} \end{align}

The notation we used earlier on is simply a further extension of the notation we used for Trinomial Coefficients. We now give a formal definition.

 Definition: If $r_1, r_2, ..., r_n$ are nonnegative integers and $n = r_1 + r_2 + ... + r_m = \sum_{i=1}^{m} r_i$ then the Multinomial Coefficient $\displaystyle{\binom{n}{r_1, r_2, ..., r_m}}$ is given by the formula $\displaystyle{\binom{n}{r_1, r_2, ..., r_m} = \frac{n!}{r_1! \cdot r_2! \cdot ... \cdot r_m!}}$.

We will later look at a further extension of the Binomial Theorem and the Trinomial Theorem known as The Multinomial Theorem page which will make use of these coefficients. Let's first look at an example of computing a multinomial coefficient.

Suppose that we want to compute $\displaystyle{\binom{17}{2, 3, 3, 4, 5}}$. Then by applying the formula we get:

(2)
\begin{align} \quad \binom{17}{2, 3, 3, 4, 5} = \frac{17!}{2! \cdot 3! \cdot 3! \cdot 4! \cdot 5!} \end{align}

Once again, if $r_1 + r_2 + ... + r_m = n$ where each $r$ is distinct, then there will be precisely $m!$ many ways to represent the same multinomial coefficient.