Mathematics
The Multinomial Theorem and Enumerating Outcomes with Repetition
Quick fact
The multinomial coefficient (n; k₁, k₂, …, kₘ) = n! / (k₁! k₂! … kₘ!) counts the number of distinct permutations of n objects where there are k₁ identical items of type 1, k₂ of type 2, and so on, and this same number appears as the coefficient in the expansion of (x₁ + x₂ + … + xₘ)ⁿ.
Why this is interesting
You know how to expand (a+b)², but what happens when you have (a+b+c)³? How many different terms appear, and how do you know their coefficients without multiplying everything out?
Read the full explanation
Understanding The Multinomial Theorem and Enumerating Outcomes with Repetition
Let's start with something familiar: (a+b)² expands to a² + 2ab + b². The coefficient 2 on the ab term arises because you can choose which factor gives the 'a' and which gives the 'b'. When you have three variables, like (a+b+c)², you get terms like a², ab, ac, b², bc, c². For the mixed term ab, you pick which factor supplies 'a' and which supplies 'b' — there are 2 choices, but for a term like abc, you need three factors, so you go to (a+b+c)³. The coefficient counts the number of ways to choose which factors contribute which variable. In general, when expanding (x₁ + x₂ + … + xₘ)ⁿ, each term corresponds to choosing nonnegative integers k₁, k₂, …, kₘ that sum to n. The coefficient for the term x₁ᵏ¹ x₂ᵏ² … xₘᵏᵐ is exactly the number of ways to assign each of the n factors to one of the m variables, with exactly kᵢ factors assigned to xᵢ. This number is the multinomial coefficient, denoted (n; k₁, k₂, …, kₘ). It equals n! divided by the product of the factorials of the kᵢ. This formula is the heart of the multinomial theorem.
A deeper explanation
The multinomial theorem states that (x₁ + x₂ + … + xₘ)ⁿ = Σ over all k₁+k₂+…+kₘ = n of (n; k₁, k₂, …, kₘ) x₁ᵏ¹ x₂ᵏ² … xₘᵏᵐ. The coefficient (n; k₁, k₂, …, kₘ) = n! / (k₁! k₂! … kₘ!) is the number of distinct permutations of n items where there are k₁ identical items of type 1, k₂ of type 2, etc. Why does this coefficient appear? Because when you expand the product, you choose one term from each of the n binomial-like factors. The number of ways to select which factors contribute to each variable is exactly the number of permutations of a multiset with those counts. This coefficient also generalizes the binomial coefficient: when m=2, we get (n; k₁, k₂) = n!/(k₁! k₂!) which equals the binomial coefficient C(n, k₁) = C(n, k₂). The theorem is not just an algebraic curiosity; it is the combinatorial foundation for counting outcomes when there are more than two categories. For example, it answers questions like 'How many distinct strings can you form from the letters of MISSISSIPPI?' (where there are 4 S's, 4 I's, 2 P's, 1 M) — the answer is 11!/(4!4!2!1!) = 34650. This connects directly to probability: if you roll a die multiple times, the probability of a specific combination of faces is given by the multinomial coefficient times the product of the individual probabilities raised to the observed counts. In computer science, the multinomial theorem helps analyze algorithms that distribute tasks into multiple categories, and it underlies generating functions for combinatorial enumeration. Understanding the mechanism — that each coefficient is a count of assignments — makes the theorem intuitive rather than a memorized formula.