- Also called:
- combinatorial mathematics
- Key People:
- Paul Erdős
- Andrei Okounkov
News •
Permutations and combinations
Binomial coefficients
An ordered set a1, a2,…, ar of r distinct objects selected from a set of n objects is called a permutation of n things taken r at a time. The number of permutations is given by nPn = n(n − 1)(n − 2)⋯ (n − r + 1). When r = n, the number nPr = n(n − 1)(n − 2)⋯ is simply the number of ways of arranging n distinct things in a row. This expression is called factorial n and is denoted by n!. It follows that nPr = n!/(n − r)!. By convention 0! = 1.
A set of r objects selected from a set of n objects without regard to order is called a combination of n things taken r at a time. Because each combination gives rise to r! permutations, the number of combinations, which is written (n/r), can be expressed in terms of factorials
.
The number (n/r) is called a binomial coefficient because it occurs as the coefficient of prqn − r in the binomial expansion—that is, the re-expression of (q + p)n in a linear combination of products of p and q
.
in the binomial expansion is the probability that an event the chance of occurrence of which is p occurs exactly r times in n independent trials (see probability theory).
The answer to many different kinds of enumeration problems can be expressed in terms of binomial coefficients. The number of distinct solutions of the equation x1 + x2 +⋯+ xn = m, for example, in which m is a non-negative integer m ≥ n and in which only non-negative integral values of xi are allowed is expressible this way, as was found by the 17th–18th-century French-born British mathematician Abraham De Moivre
.
Multinomial coefficients
If S is a set of n objects and if n1, n2,…, nk are non-negative integers satisfying n1 + n2 +⋯+ nk = n, then the number of ways in which the objects can be distributed into k boxes, X1, X2,…, Xk, such that the box Xi contains exactly ni objects is given in terms of a ratio constructed of factorials
.
This number, called a multinomial coefficient, is the coefficient in the multinomial expansion of the nth power of the sum of the {pi}
If all of the {pi} are non-negative and sum to 1 and if there are k possible outcomes in a trial in which the chance of the ith outcome is pi, then the ith summand in the multinomial expansion is the probability that in n independent trials the ith outcome will occur exactly ni times, for each i, 1 i k.
Recurrence relations and generating functions
If fn is a function defined on the positive integers, then a relation that expresses fn + k as a linear combination of function values of integer index less than n + k, in which a fixed constant in the linear combination is written ai, is called a recurrence relation
.
The relation together with the initial values f0, f1,…, fk − 1 determines fn for all n. The function F(x) constructed of a sum of products of the type fnxn, the convergence of which is assumed in the neighbourhood of the origin, is called the generating function of fn
.
The set of the first n positive integers will be written Xn. It is possible to find the number of subsets of Xn containing no two consecutive integers, with the convention that the null set counts as one set. The required number will be written fn. A subset of the required type is either a subset of Xn − 1 or is obtained by adjoining n to a subset of Xn − 2. Therefore fn is determined by the recurrence relation fn = fn − 1 + fn − 2 with the initial values f0 = 1, f1 = 2. Thus f2 = 3, f3 = 5, f4 = 8, and so on. The generating function F(x) of fn can be calculated
,
and from this a formula for the desired function fn can be obtained
That fn = fn-1 + fn-2 can now be directly checked.
Partitions
A partition of a positive integer n is a representation of n as a sum of positive integers n = x1 + x2 +⋯+ xk, xi ≥ 1, i = 1, 2,…, k. The numbers xi are called the parts of the partition. The 
for this is the number of ways of putting k − 1 separating marks in the n − 1 spaces between n dots in a row. The theory of unordered partitions is much more difficult and has many interesting features. An unordered partition can be standardized by listing the parts in a decreasing order. Thus n = x1 + x2 +⋯+ xk, x1 ≥ x2 ≥⋯≥ xk ≥ 1. In what follows, partition will mean an unordered partition.
The number of partitions of n into k parts will be denoted by Pk(n), and a recurrence formula for it can be obtained from the definition
.
This recurrence formula, together with the initial conditions Pk(n) = 0 if n < k, and Pk(k) = 1 determines Pk(n). It can be shown that Pk(n) depends on the value of n (mod k!), in which the notation x ≡ a (mod b) means that x is any number that, if divided by b, leaves the same remainder as a does. For example, P3(n) = n2 + cn, in which cn = 0, −1/12, −1/3, +1/4, −1/3, or −1/12, according as n is congruent to 0, 1, 2, 3, 4, or 5 (mod 6). P(n), which is a sum over all values of k from 1 to n of Pk(n), denotes the number of partitions of n into n or fewer parts.