Asphalt Wiki


Ambox content
This page uses LaTeX markup to display mathematical formulas. Editing the page with the VisualEditor or Classic rich-text editor disrupts the layout.
Do not even switch to one of these editors while editing the page!
For help with mathematical symbols, see Mathematical symbols and expressions.

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem which describes the algebraic expansion of powers of a binomial. Commonly, a binomial coefficient is indexed by a pair of integers and is written . Alternative notations include , , and in all of which the stands for combinations or choices. Many calculators use variants of the notation because they can represent it on a single-line display. In this form the binomial coefficients are easily compared to k-permutations of n, written as , etc.

The binomial coefficient is the coefficient of the term in the polynomial expansion of the binomial power , and it is given by the formula

For example, the fourth power of is

and the binomial coefficient is the coefficient of the term.

The binomial coefficients occur in many areas of mathematics, and especially in combinatorics. The symbol is usually read as " choose " because there are ways to choose an (unordered) subset of elements from a fixed set of elements. For example, there are ways to choose 2 elements from namely and

Computing the value of binomial coefficients[]

Several methods exist to compute the value of without actually expanding a binomial power or counting k-combinations.

Recursive formula[]

One method uses the recursive, purely additive, formula

with initial/boundary values

The formula follows from considering the set and counting separately

  • (a) the -element groupings that include a particular set element, say "", in every group (since "" is already chosen to fill one spot in every group, we need only choose from the remaining ) and
  • (b) all the -groupings that don't include ""; this enumerates all the possible -combinations of elements.

Multiplicative formula[]

A more efficient method to compute individual binomial coefficients is given by the formula

where the numerator of the first fraction is expressed as a falling factorial power. This formula is easiest to understand for the combinatorial interpretation of binomial coefficients. The numerator gives the number of ways to select a sequence of distinct objects, retaining the order of selection, from a set of objects. The denominator counts the number of distinct sequences that define the same -combination when order is disregarded.

Due to the symmetry of the binomial coefficient with regard to and , calculation may be optimised by setting the upper limit of the product above to the smaller of and .

Factorial formula[]

Finally, though computationally unsuitable, there is the compact form, often used in proofs and derivations, which makes repeated use of the factorial function:

where denotes the factorial of . This formula follows from the multiplicative formula above by multiplying numerator and denominator by ; as a consequence it involves many factors common to numerator and denominator. It is less practical for explicit computation (in the case that is small and is large) unless common factors are first cancelled (in particular since factorial values grow very rapidly). The formula does exhibit a symmetry that is less evident from the multiplicative formula (though it is from the definitions)

which leads to a more efficient multiplicative computational routine. Using the falling factorial notation,

Combinatorics and statistics[]

Binomial coefficients are of importance in combinatorics, because they provide ready formulas for certain frequent counting problems:

  • There are ways to choose elements from a set of elements. See Combination.
  • There are ways to choose elements from a set of elements if repetitions are allowed.
  • There are strings containing ones and zeros.
  • There are strings consisting of ones and zeros such that no two ones are adjacent.
  • The binomial distribution in statistics is .

See also[]

  • Combination
  • Permutation
  • Binomial distribution