A multinomial coefficient is a nonnegative integer that counts how many ways distinct objects can be divided among labeled groups of specified sizes, or how many distinct sequences have specified numbers of occurrences of each symbol. It generalizes the binomial coefficient from two groups to any finite number of groups. Multinomial coefficients appear in combinatorics, in expansions of powers of sums, and in probability calculations involving several possible outcomes.
Definition and notation
For nonnegative integers satisfying
the multinomial coefficient is
where denotes the factorial of , with .
The upper argument is the total number of objects or positions; the lower arguments specify their category counts. Some notation omits the upper argument because it is determined by the lower arguments.
For two categories,
For one category, the coefficient is . If , all category counts are zero and the coefficient is also , corresponding to the unique empty arrangement.
The factorial definition assumes that all lower arguments are nonnegative and sum to the upper argument. In recurrences and coefficient formulas, it is often convenient to extend the definition by assigning the value zero to integer tuples that violate these conditions.
Counting interpretations
Dividing distinct objects into labeled groups
Suppose distinct objects are assigned to labeled groups, with group required to contain exactly objects. The number of assignments is
To see this, arrange all objects in a row, then cut the row into consecutive blocks of lengths . There are initial arrangements. Rearranging the objects within any block does not change the group assignment, so every assignment is counted times.
The group labels matter. If groups are instead unlabeled, the counting problem becomes one about set partitions, and additional adjustments may be required. For example, dividing distinct objects into unlabeled groups, all of positive size , gives
Arrangements of repeated symbols
The same coefficient counts distinct sequences of length containing copies of symbol . This is often described as counting permutations of a multiset.
For example, the word BANANA contains three copies of A, two of N, and one of B. Its distinct letter arrangements number
Although repeated symbols are indistinguishable, their positions in the sequence are distinct. Choosing which positions receive each symbol is equivalent to assigning the positions to labeled groups.
Lattice paths
Consider paths from the origin to in an integer lattice, where each step increases exactly one coordinate by . Every path contains steps in coordinate direction , so the number of paths is
This interpretation applies when no additional restrictions, such as forbidden vertices or boundary constraints, are imposed.
The multinomial theorem
The multinomial theorem states that
Thus, the multinomial coefficient is the coefficient of the indicated monomial in the expanded polynomial. For , this is the binomial theorem.
The formula follows by viewing the power as a product of identical sums. To obtain , one must choose from exactly of the factors. The number of such choices is the multinomial coefficient.
For example,
The coefficient of is
The theorem holds for commuting variables, including elements of a commutative ring. It does not apply in this form to arbitrary noncommuting quantities: terms such as and need not coincide.
Identities and recurrences
Symmetry and successive selection
Permuting the lower arguments leaves the coefficient unchanged:
for every permutation of the category indices.
A multinomial coefficient can also be written as a product of binomial coefficients:
This corresponds to choosing the first group, then the second from the remaining objects, and continuing. It also establishes that the factorial ratio is an integer.
Pascal-type recurrence
For ,
This recurrence relation follows by classifying sequences according to their final symbol. It generalizes Pascal’s recurrence for binomial coefficients.
Sum of all coefficients
Setting every variable equal to in the multinomial theorem gives
Combinatorially, both sides count all length- sequences over an alphabet of symbols.
The number of count vectors in this sum is
This counts possible category-count patterns, rather than sequences, and should not be confused with the individual multinomial coefficients.
Probability and statistics
Suppose independent trials each have possible outcomes, with fixed probabilities satisfying
Let the random variable count how many trials produce outcome . The count vector has a multinomial distribution, whose probability mass function is
When a category has both probability and count zero, its factor is interpreted as .
Every particular outcome sequence with these counts has probability . The multinomial coefficient counts how many such sequences contribute to the event.
For example, in six independent rolls of a fair die, the probability that every face occurs exactly once is
For two outcomes, the multinomial distribution reduces to the binomial distribution. In maximum likelihood estimation from a fixed count vector, the multinomial coefficient is constant with respect to the unknown probabilities. It can therefore be omitted when locating the maximizing parameters, though it remains part of the probability mass function.
Computation and asymptotic size
Directly evaluating factorials can produce very large intermediate values. Exact calculations can instead use the successive-binomial product, with arbitrary-precision integer arithmetic when necessary.
For approximate calculations, especially when only a logarithm is needed,
where is the gamma function. Logarithmic evaluation avoids the overflow associated with explicitly forming large factorials, although cancellation and rounding can still affect accuracy.
Stirling’s approximation describes the coefficient’s growth. Write . For fixed , with all proportions bounded away from zero as increases,
where
is information entropy using natural logarithms.
This formula connects category-count arrangements with information theory: the leading exponential growth rate is determined by entropy. If some counts remain small or are zero, the stated approximation does not apply directly to those categories.
For fixed and , the largest coefficients occur when the counts differ by at most one. Indeed, if , moving one unit from to multiplies the coefficient by
Repeatedly balancing unequal counts therefore increases the coefficient until the counts are as equal as possible.