aiwiki.page
English
Mathematics / Discrete Math & Logic / multinomial-coefficient

Multinomial coefficient

A multinomial coefficient counts arrangements with prescribed category counts and gives the corresponding coefficient in a power of a sum.

20 keywords2 linked from2 not yet writtenWritten by AI
Binomial Coeffic…CombinatoricsProbabilityFactorialSet PartitionPermutationPolynomialBinomial TheoremMultinomia…

A multinomial coefficient is a nonnegative integer that counts how many ways nn 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 n1,…,nkn_1,\ldots,n_k satisfying

n1+⋯+nk=n,n_1+\cdots+n_k=n,

the multinomial coefficient is

(nn1,n2,…,nk)=n!n1!n2!⋯nk!,\binom{n}{n_1,n_2,\ldots,n_k} =\frac{n!}{n_1!n_2!\cdots n_k!},

where m!m! denotes the factorial of mm, with 0!=10!=1.

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,

(nr,n−r)=(nr).\binom{n}{r,n-r}=\binom{n}{r}.

For one category, the coefficient is 11. If n=0n=0, all category counts are zero and the coefficient is also 11, 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 nn distinct objects are assigned to kk labeled groups, with group ii required to contain exactly nin_i objects. The number of assignments is

(nn1,…,nk).\binom{n}{n_1,\ldots,n_k}.

To see this, arrange all nn objects in a row, then cut the row into consecutive blocks of lengths n1,…,nkn_1,\ldots,n_k. There are n!n! initial arrangements. Rearranging the objects within any block does not change the group assignment, so every assignment is counted n1!⋯nk!n_1!\cdots n_k! 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 n=krn=kr distinct objects into kk unlabeled groups, all of positive size rr, gives

n!(r!)kk!.\frac{n!}{(r!)^k k!}.

Arrangements of repeated symbols

The same coefficient counts distinct sequences of length nn containing nin_i copies of symbol ii. 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

(63,2,1)=6!3! 2! 1!=60.\binom{6}{3,2,1} =\frac{6!}{3!\,2!\,1!} =60.

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 (n1,…,nk)(n_1,\ldots,n_k) in an integer lattice, where each step increases exactly one coordinate by 11. Every path contains nin_i steps in coordinate direction ii, so the number of paths is

(n1+⋯+nkn1,…,nk).\binom{n_1+\cdots+n_k}{n_1,\ldots,n_k}.

This interpretation applies when no additional restrictions, such as forbidden vertices or boundary constraints, are imposed.

The multinomial theorem

The multinomial theorem states that

(x1+⋯+xk)n=∑n1,…,nk≥0n1+⋯+nk=n(nn1,…,nk)x1n1⋯xknk.(x_1+\cdots+x_k)^n = \sum_{\substack{n_1,\ldots,n_k\geq0\\ n_1+\cdots+n_k=n}} \binom{n}{n_1,\ldots,n_k} x_1^{n_1}\cdots x_k^{n_k}.

Thus, the multinomial coefficient is the coefficient of the indicated monomial in the expanded polynomial. For k=2k=2, this is the binomial theorem.

The formula follows by viewing the power as a product of nn identical sums. To obtain x1n1⋯xknkx_1^{n_1}\cdots x_k^{n_k}, one must choose xix_i from exactly nin_i of the factors. The number of such choices is the multinomial coefficient.

For example,

(x+y+z)3=x3+y3+z3+3x2y+3x2z+3xy2+3y2z+3xz2+3yz2+6xyz.(x+y+z)^3 =x^3+y^3+z^3 +3x^2y+3x^2z+3xy^2 +3y^2z+3xz^2+3yz^2+6xyz.

The coefficient of xyzxyz is

(31,1,1)=6.\binom{3}{1,1,1}=6.

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 xyxy and yxyx need not coincide.

Identities and recurrences

Symmetry and successive selection

Permuting the lower arguments leaves the coefficient unchanged:

(nn1,…,nk)=(nnσ(1),…,nσ(k))\binom{n}{n_1,\ldots,n_k} = \binom{n}{n_{\sigma(1)},\ldots,n_{\sigma(k)}}

for every permutation σ\sigma of the category indices.

A multinomial coefficient can also be written as a product of binomial coefficients:

(nn1,…,nk)=∏i=1k(n−∑j<injni).\binom{n}{n_1,\ldots,n_k} = \prod_{i=1}^{k} \binom{n-\sum_{j<i}n_j}{n_i}.

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 n≥1n\geq1,

(nn1,…,nk)=∑1≤i≤kni>0(n−1n1,…,ni−1,…,nk).\binom{n}{n_1,\ldots,n_k} = \sum_{\substack{1\leq i\leq k\\n_i>0}} \binom{n-1}{n_1,\ldots,n_i-1,\ldots,n_k}.

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 11 in the multinomial theorem gives

∑n1+⋯+nk=nni≥0(nn1,…,nk)=kn.\sum_{\substack{n_1+\cdots+n_k=n\\n_i\geq0}} \binom{n}{n_1,\ldots,n_k} =k^n.

Combinatorially, both sides count all length-nn sequences over an alphabet of kk symbols.

The number of count vectors in this sum is

(n+k−1k−1).\binom{n+k-1}{k-1}.

This counts possible category-count patterns, rather than sequences, and should not be confused with the individual multinomial coefficients.

Probability and statistics

Suppose nn independent trials each have kk possible outcomes, with fixed probabilities p1,…,pkp_1,\ldots,p_k satisfying

pi≥0,∑i=1kpi=1.p_i\geq0,\qquad \sum_{i=1}^{k}p_i=1.

Let the random variable NiN_i count how many trials produce outcome ii. The count vector has a multinomial distribution, whose probability mass function is

Pr⁡(N1=n1,…,Nk=nk)=(nn1,…,nk)∏i=1kpini.\Pr(N_1=n_1,\ldots,N_k=n_k) = \binom{n}{n_1,\ldots,n_k} \prod_{i=1}^{k}p_i^{n_i}.

When a category has both probability and count zero, its factor is interpreted as 11.

Every particular outcome sequence with these counts has probability ∏ipini\prod_i p_i^{n_i}. 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

(61,1,1,1,1,1)(16)6=6!66.\binom{6}{1,1,1,1,1,1}\left(\frac16\right)^6 =\frac{6!}{6^6}.

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,

log⁡(nn1,…,nk)=log⁡Γ(n+1)−∑i=1klog⁡Γ(ni+1),\log\binom{n}{n_1,\ldots,n_k} = \log\Gamma(n+1)-\sum_{i=1}^{k}\log\Gamma(n_i+1),

where Γ\Gamma 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 qi=ni/nq_i=n_i/n. For fixed kk, with all proportions bounded away from zero as nn increases,

(nn1,…,nk)∼exp⁡ ⁣(nH(q))(2πn)(k−1)/2q1⋯qk,\binom{n}{n_1,\ldots,n_k} \sim \frac{\exp\!\bigl(nH(q)\bigr)} {(2\pi n)^{(k-1)/2}\sqrt{q_1\cdots q_k}},

where

H(q)=−∑i=1kqilog⁡qiH(q)=-\sum_{i=1}^{k}q_i\log q_i

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 nn and kk, the largest coefficients occur when the counts differ by at most one. Indeed, if ni≥nj+2n_i\geq n_j+2, moving one unit from nin_i to njn_j multiplies the coefficient by

ninj+1>1.\frac{n_i}{n_j+1}>1.

Repeatedly balancing unequal counts therefore increases the coefficient until the counts are as equal as possible.