Multinomial Coefficients

Multinomial coefficients are generalizations of binomial coefficients, with a similar combinatorial interpretation. They are the coefficients of terms in the expansion of a power of a multinomial, in the multinomial theorem.

The multinomial coefficient, like the binomial coefficient, has several combinatorial interpretations.

Let \( b_1,\ldots, b_k \) be nonnegative integers, and let \( n = b_1+b_2+\cdots+b_k\). The multinomial coefficient \( \binom{n}{b_1,b_2,\ldots,b_k}\) is:

(1) the number of ways to put \( n \) interchangeable objects into \(k\) boxes, so that box \(i \) has \( b_i \) objects in it, for \( 1\le i \le k\).

(2) the number of ways to choose \( b_1 \) interchangeable objects from \(n \) objects, then to choose \( b_2\) from what remains, then to choose \( b_3\) from what remains, ..., then to choose \( b_{k-1} \) from what remains.

(3) the number of unique permutations of a word with \( n \) letters and \( k \) distinct letters, such that the \(i\)th letter occurs \(b_i\) times.

(4) the product \[ \binom{n}{b_1}\binom{n-b_1}{b_2}\binom{n-b_1-b_2}{b_3}\cdots\binom{b_{k-1}+b_k}{b_{k-1}}\binom{b_k}{b_k}. \]

(5) the quotient \[ \frac{n!}{b_1!b_2!\cdots b_k!}. \]

(1) and (2) are clearly equivalent, and (2) and (4) are equivalent from the definition of the binomial coefficient. (4) and (5) are equivalent by simple algebra. There are a few ways to see that (3) is equivalent to the others. Arguing combinatorially, note that a permutation of a word as in (3) corresponds to choices of spots to put each of the repeated letters in; out of the spots \( 1, \ldots, n\), choose \( b_1 \) of those spots to put the first letter in, then \(b_2 \) spots out of the remaining \( n-b_1 \) to put the second letter in, and so on. So (3) is equivalent to (2).

(One can also count permutations directly, by taking \( n! \) permutations and dividing by factors that account for duplicates: divide by a factor of \( b_1! \) to account for the fact that permuting all of the first letters doesn't change the permutation, divide by \( b_2!\) to do the same for the second letters, and so on, which gives the formula from (5).)

How many unique permutations of the word ABRACADABRA are there?

---

Solution: Using definition (3), this is the multinomial coefficient \( \binom{11}{5,2,1,1,2} = 83{,}160.\)

For a fixed \( n \) and \( k \), what is the sum of all the multinomial coefficients \( \binom{n}{b_1,b_2,\ldots,b_k}\)?

---

Using definition (1), this is the number of ways to put \(n\) objects into \( k \) boxes (each specific multinomial coefficient gives a different breakdown of how many objects are in each box). Each object has \( k \) choices for its destination, so the total number is \(k \cdot k \cdot k \cdots \cdot k = k^n \).

This example has a different solution using the multinomial theorem; see that wiki for details.

The multinomial coefficients are the coefficients of the terms in the expansion of \( (x_1+x_2+\cdots+x_k)^n\); in particular, the coefficient of \( x_1^{b_1} x_2^{b_2} \cdots x_k^{b_k}\) is \( \binom{n}{b_1,b_2,\ldots,b_k}\). This is the multinomial theorem.