Neel Mishra
← All Posts
Math · Probability & Statistics · Combinatorial Analysis· Part 6 of 7

Multinomial Coefficients

May 2026 · 16 min read

The binomial coefficient $\binom{n}{r}$ splits $n$ items into two groups: chosen and unchosen. But sometimes we want to split into more groups — three teams, four bins, $k$ types. The natural generalisation is the multinomial coefficient, and it shows up everywhere from card-dealing to symbol-counting to multinomial probability distributions in Ross Chapter 4.

Definition

Multinomial coefficient. Suppose $n_1, n_2, \dots, n_k$ are non-negative integers with $n_1 + n_2 + \dots + n_k = n$. Define

$\displaystyle \binom{n}{n_1, n_2, \dots, n_k} = \dfrac{n!}{n_1!\, n_2! \cdots n_k!}.$

It counts the number of ways to partition $n$ distinct items into $k$ labelled groups of sizes $n_1, n_2, \dots, n_k$.

When $k = 2$, this collapses to $\binom{n}{n_1, n_2} = \dfrac{n!}{n_1!\, n_2!} = \binom{n}{n_1}$, recovering the binomial coefficient. So multinomials are a strict generalisation.

Why It Works — Two Derivations

Derivation 1: stage-by-stage choice

Form the groups one at a time:

By the multiplication rule:

$\binom{n}{n_1}\binom{n - n_1}{n_2} \cdots \binom{n_k}{n_k} = \dfrac{n!}{n_1!\,(n - n_1)!} \cdot \dfrac{(n - n_1)!}{n_2!\,(n - n_1 - n_2)!} \cdots = \dfrac{n!}{n_1! n_2! \cdots n_k!}.$

The intermediate factorials telescope, leaving the multinomial. $\Box$

Derivation 2: line up and label

Imagine arranging the $n$ items in a row ($n!$ orderings), then assigning the first $n_1$ to group 1, the next $n_2$ to group 2, and so on. We have overcounted: any reordering within a group produces the same partition. Divide out by $n_1!\, n_2! \cdots n_k!$ and we get the same formula. This is exactly the “permutations of indistinguishable objects” argument from Part 3, viewed from a different angle.

Two views, same number. Multinomial coefficients count both partitions of distinct objects into labelled groups and distinct rearrangements of a sequence whose elements come in $k$ types with multiplicities $n_1, n_2, \dots, n_k$. These two interpretations are dual: each labelled grouping corresponds to a unique “type pattern” in a row, and vice versa.

▶ Visual: Partitioning 6 Students into Groups of 3 / 2 / 1

Step through one assignment to see why $\binom{6}{3, 2, 1} = \dfrac{6!}{3!\,2!\,1!} = 60.$

The Multinomial Theorem

Multinomial theorem. For any non-negative integer $n$ and any quantities $x_1, x_2, \dots, x_k$,

$\displaystyle (x_1 + x_2 + \dots + x_k)^n = \sum_{n_1 + n_2 + \dots + n_k = n} \binom{n}{n_1, n_2, \dots, n_k} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}.$

The sum runs over all compositions of $n$ into $k$ non-negative parts.

Proof. Same idea as the binomial theorem. Expand the product of $n$ identical factors $(x_1 + x_2 + \dots + x_k)$. To produce the monomial $x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}$ we must pick $x_i$ from exactly $n_i$ of the $n$ factors, and the count of those choices is the multinomial coefficient. $\Box$

Worked Examples

Ross 1.5a — Bridge deals

How many ways are there to deal 52 cards into four 13-card hands (north, south, east, west)?

The hands are labelled (we know which player is north and which is south), so this is a multinomial:

$\binom{52}{13, 13, 13, 13} = \dfrac{52!}{(13!)^4} \approx 5.36 \times 10^{28}.$

Ross 1.5b — MISSISSIPPI revisited

How many distinct anagrams of MISSISSIPPI are there?

Either view it as “permutations of a multiset” (Part 3) or as “partition the 11 positions into label-groups of sizes 1, 4, 4, 2” (this post). Both give:

$\binom{11}{1, 4, 4, 2} = \dfrac{11!}{1!\,4!\,4!\,2!} = 34{,}650.$

Ross 1.5c — Splitting students into groups

If 10 students are split into 3 distinct teams of sizes 4, 4, and 2, how many ways are there?

$\binom{10}{4, 4, 2} = \dfrac{10!}{4!\,4!\,2!} = \dfrac{3{,}628{,}800}{24 \cdot 24 \cdot 2} = 3{,}150.$

What if the two teams of size 4 are unlabelled — say "two practice teams that play each other"?

If the two same-sized teams are interchangeable, divide further by the $2!$ ways to swap them:

$\dfrac{3{,}150}{2!} = 1{,}575.$

Labels matter. “Three labelled teams” and “three unlabelled teams of identical size” are different. In the labelled case use the multinomial directly. In the unlabelled case divide by the number of label-swaps that preserve the sizes.

Worked: $(x + y + z)^3$

Apply the multinomial theorem with $n = 3$ and $k = 3$:

(x + y + z)^3 =
   x^3              [coefficient C(3; 3,0,0) = 1]
 + y^3              [C(3; 0,3,0) = 1]
 + z^3              [C(3; 0,0,3) = 1]
 + 3 x^2 y          [C(3; 2,1,0) = 3]
 + 3 x^2 z          [C(3; 2,0,1) = 3]
 + 3 x y^2          [C(3; 1,2,0) = 3]
 + 3 y^2 z          [C(3; 0,2,1) = 3]
 + 3 x z^2          [C(3; 1,0,2) = 3]
 + 3 y z^2          [C(3; 0,1,2) = 3]
 + 6 x y z          [C(3; 1,1,1) = 6]

Sum of coefficients: $1 + 1 + 1 + 6 \cdot 3 + 6 = 27 = 3^3$. Setting $x = y = z = 1$ in the theorem confirms the row sum identity.

Useful Properties

Computing Multinomial Coefficients

// Modular multinomial using precomputed fact[] / invFact[].
long long multinomial(int n, const std::vector<int>& parts) {
    long long sum = 0;
    for (int p : parts) sum += p;
    if (sum != n) return 0;          // invalid input
    long long r = fact[n];
    for (int p : parts) r = r * invFact[p] % MOD;
    return r;
}

For exact integer answers (no modulus), the safest method is to multiply binomials in stages and divide in integer arithmetic — exactly Derivation 1 from earlier in this post.

Probability Application: The Multinomial Distribution

Roll an $k$-sided die $n$ times. The probability of seeing exactly $n_i$ outcomes of side $i$ for $i = 1, \dots, k$ (with $n_1 + \dots + n_k = n$) is

$\Pr[(N_1, \dots, N_k) = (n_1, \dots, n_k)] = \binom{n}{n_1, \dots, n_k} p_1^{n_1} p_2^{n_2} \cdots p_k^{n_k}$

where $p_i$ is the probability of side $i$ on one roll. The multinomial coefficient counts the orderings; the product of $p_i^{n_i}$ accounts for the probability of any one such ordering. Ross devotes Section 4.6 to this — and you'll be ready for it because you understand where the multinomial coefficient comes from.

Common Mistakes

Summary

Practice Problems