In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the multinomial theorem describes how to expand a
power of a
sum in terms of powers of the terms in that sum. It is the
generalization
A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set of elements, as well as one or more common character ...
of the
binomial theorem from
binomial
Binomial may refer to:
In mathematics
*Binomial (polynomial), a polynomial with two terms
*Binomial coefficient, numbers appearing in the expansions of powers of binomials
*Binomial QMF, a perfect-reconstruction orthogonal wavelet decomposition
* ...
s to
multinomials.
Theorem
For any positive integer and any non-negative integer , the multinomial formula describes how a sum with terms expands when raised to an arbitrary power :
:
where
:
is a multinomial coefficient. The sum is taken over all combinations of
nonnegative integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
indices through such that the sum of all is . That is, for each term in the expansion, the exponents of the must add up to . Also, as with the
binomial theorem, quantities of the form that appear are taken to equal 1 (
even when equals zero).
In the case , this statement reduces to that of the binomial theorem.
Example
The third power of the trinomial is given by
:
This can be computed by hand using the distributive property of multiplication over addition, but it can also be done (perhaps more easily) with the multinomial theorem. It is possible to "read off" the multinomial coefficients from the terms by using the multinomial coefficient formula. For example:
:
has the coefficient
:
has the coefficient
Alternate expression
The statement of the theorem can be written concisely using
multiindices:
:
where
:
and
:
Proof
This proof of the multinomial theorem uses the
binomial theorem and
induction on .
First, for , both sides equal since there is only one term in the sum. For the induction step, suppose the multinomial theorem holds for . Then
:
by the induction hypothesis. Applying the binomial theorem to the last factor,
:
:
which completes the induction. The last step follows because
:
as can easily be seen by writing the three coefficients using factorials as follows:
:
Multinomial coefficients
The numbers
:
appearing in the theorem are the
multinomial coefficients. They can be expressed in numerous ways, including as a product of
binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s or of
factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \ ...
s:
:
Sum of all multinomial coefficients
The substitution of for all into the multinomial theorem
:
gives immediately that
:
Number of multinomial coefficients
The number of terms in a multinomial sum, , is equal to the number of monomials of degree on the variables :
:
The count can be performed easily using the method of
stars and bars.
Valuation of multinomial coefficients
The largest power of a prime that divides a multinomial coefficient may be computed using a generalization of
Kummer's theorem
In mathematics, Kummer's theorem is a formula for the exponent of the highest power of a prime number ''p'' that divides a given binomial coefficient. In other words, it gives the ''p''-adic valuation of a binomial coefficient. The theorem is nam ...
.
Interpretations
Ways to put objects into bins
The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing distinct objects into distinct bins, with objects in the first bin, objects in the second bin, and so on.
Number of ways to select according to a distribution
In
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic b ...
and
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, if one has a number distribution of labels, then the multinomial coefficients naturally arise from the binomial coefficients. Given a number distribution on a set of total items, represents the number of items to be given the label . (In statistical mechanics is the label of the energy state.)
The number of arrangements is found by
*Choosing of the total to be labeled 1. This can be done
ways.
*From the remaining items choose to label 2. This can be done
ways.
*From the remaining items choose to label 3. Again, this can be done
ways.
Multiplying the number of choices at each step results in:
:
Cancellation results in the formula given above.
Number of unique permutations of words
The multinomial coefficient
:
is also the number of distinct ways to
permute a
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
of elements, where is the
multiplicity of each of the th element. For example, the number of distinct permutations of the letters of the word MISSISSIPPI, which has 1 M, 4 Is, 4 Ss, and 2 Ps, is
:
Generalized Pascal's triangle
One can use the multinomial theorem to generalize
Pascal's triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although o ...
or
Pascal's pyramid to
Pascal's simplex. This provides a quick way to generate a lookup table for multinomial coefficients.
See also
*
Multinomial distribution
*
Stars and bars (combinatorics)
In the context of combinatorial mathematics, stars and bars (also called "sticks and stones", "balls and bars", and "dots and dividers") is a graphical aid for deriving certain combinatorial theorems. It was popularized by William Feller in his ...
References
{{Reflist
Factorial and binomial topics
Articles containing proofs
Theorems about polynomials