the multinomial coefficient and multinomial theorem
/ mul-tih-NOH-mee-ul /
The binomial coefficient counts ways to split n items into TWO groups (chosen and not chosen). But what if you want to split into more than two groups — say, deal 9 cards into three labelled hands of 3, 3, 3, or count anagrams of a word with several repeated letters? The multinomial coefficient is the natural generalisation: it counts the ways to partition n distinct items into r labelled groups of specified sizes.
If the group sizes are n1, n2, ..., nr and they add up to n, the multinomial coefficient is n! / (n1! n2! ... nr!). When there are just two groups (r = 2) this is exactly C(n, n1), the ordinary binomial coefficient, so the multinomial truly generalises it. The same number does triple duty: it counts ordered partitions into labelled groups, it counts distinct arrangements of a multiset with those repeat counts (the anagram count), and it is the coefficient in the multinomial theorem, which says (x1 + x2 + ... + xr)^n = sum over all (n1, ..., nr) with sum n of [n!/(n1!...nr!)] x1^n1 x2^n2 ... xr^nr. The coefficient counts how many ways the n factors hand out their xi's.
Watch the labelling carefully. The multinomial counts groups that are DISTINGUISHED (Hand 1, Hand 2, Hand 3 are different roles). If the groups are interchangeable — for instance splitting 9 people into three UNLABELLED teams of 3 with no roles attached — you must additionally divide by the number of ways to permute the equal-sized groups, here an extra 3!, or you will over-count. The binomial and multinomial coefficients always come out as whole numbers.
Deal 12 distinct cards into three labelled hands of sizes 5, 4, 3: that is 12!/(5!4!3!) = 27720 ways. The anagrams of MISSISSIPPI (4 I, 4 S, 2 P, 1 M) are 11!/(4!4!2!1!) = 34650 — the same kind of number.
n!/(n1! n2! ... nr!) partitions n into labelled groups; generalises C(n,k).
It counts LABELLED groups. If the groups of equal size are interchangeable with no distinct roles, divide by the factorial of the number of such equal groups to avoid over-counting.