Multinomial Coefficient

Definition

Multinomial Coefficient

Let $n_{1}, \dots, n_{k}$ be non-negative integers satisfying
$n_{1} + \dots + n_{k} = n .$
The multinomial coefficient
$(n _{1} , \dots , n _{k} n) := \frac{n !}{n _{1} ! \dots n _{k} !}$
counts the ways to assign $n$ distinct positions to $k$ labelled groups so that group $i$ receives exactly $n_{i}$ positions. Equivalently, it counts permutations with repetition of a multiset whose distinct values have multiplicities $n_{1}, \dots, n_{k}$ .

Sequential Factorisation

Choose the $n_{1}$ positions of the first group, then the $n_{2}$ positions of the second group from those remaining, and continue until the last group is forced. The product rule gives the canonical factorisation

(n _{1} , \dots , n _{k} n) = (n _{1} n) (n _{2} n - n _{1}) (n _{3} n - n _{1} - n _{2}) \dots (n _{k} n _{k}) .

Expanding the binomial coefficients makes the intermediate factorials telescope, leaving

\frac{n !}{n _{1} ! \dots n _{k} !} .

Example

Two copies of $A$ and one copy of $B$

Choose two of the three positions for $A$ ; the remaining position is forced to contain $B$ .

Therefore
$(2 , 1 3) = \frac{3 !}{2 ! 1 !} = 3.$

Binomial Special Case

For $k = 2$ and $n_{2} = n - n_{1}$ , the multinomial coefficient reduces to a binomial coefficient:

(n _{1} , n - n _{1} n) = (n _{1} n) .

Multinomial Expansion

The coefficients in the expansion of $(x_{1} + \dots + x_{k})^{n}$ are multinomial coefficients:

(x_{1} + \dots + x_{k})^{n} = n_{1}, \dots, n_{k} \geq 0 n_{1} + \dots + n_{k} = n \sum (n _{1} , \dots , n _{k} n) x_{1}^{n_{1}} \dots x_{k}^{n_{k}} .

Lukas' Notes

Multinomial Coefficient

Table of Contents

Definition

Sequential Factorisation

Example

Binomial Special Case

Multinomial Expansion

Backlinks