Binomial coefficient

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 n \ge k \ge 0 and is written \tbinom{n}{k}. Alternative notations include C(n,k), _nC_k, and C_{n,k} in all of which the C stands for combinations or choices. Many calculators use variants of the 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 P(n,k), etc.
The binomial coefficient is the coefficient of the x^k term in the polynomial expansion of the binomial power (1+x)^n, and it is given by the formula
:\binom{n}{k} = \frac{n!}{k! (n-k)!}.
For example, the fourth power of 1+x is
:\begin{align}
 (1 + x)^4 &= \tbinom{4}{0} x^0 + \tbinom{4}{1} x^1 + \tbinom{4}{2} x^2 + \tbinom{4}{3} x^3 + \tbinom{4}{4} x^4 \\
 &= 1 + 4x + 6 x^2 + 4x^3 + x^4,
 \end{align}
and the binomial coefficient \tbinom{4}{2} =\tfrac{4!}{2!\cdot2!} = 6 is the coefficient of the x^2 term.
The binomial coefficients occur in many areas of mathematics, and especially in combinatorics. The symbol \tbinom{n}{k} is usually read as "n choose k" because there are \tbinom{n}{k} ways to choose an (unordered) subset of k elements from a fixed set of n elements. For example, there are \tbinom{4}{2}=6 ways to choose 2 elements from \{1,2,3,4\}, namely \{1,2\} \text{, } \{1,3\} \text{, } \{1,4\} \text{, } \{2,3\} \text{, } \{2,4\} \text{,} and \{3,4\}.
== Computing the value of binomial coefficients ==
Several methods exist to compute the value of \tbinom nk without actually expanding a binomial power or counting k-combinations.
=== Recursive formula ===
One method uses the recursive, purely additive, formula
: \binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \text{for all integers }n,k : 1\le k\le n-1,
with initial/boundary values
:\binom n0 = \binom nn = 1 \quad \text{for all integers } n\ge0,
The formula follows from considering the set \{1,2,3,\ldots,n\} and counting separately
* (a) the k-element groupings that include a particular set element, say "i", in every group (since "i" is already chosen to fill one spot in every group, we need only choose k-1 from the remaining k-1) and
* (b) all the k-groupings that don't include "i"; this enumerates all the possible k-combinations of n elements.
=== Multiplicative formula ===
A more efficient method to compute individual binomial coefficients is given by the formula
:\binom nk = \frac{n^{\underline{k}}}{k!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{n+1-i}{i},
where the numerator of the first fraction n^{\underline{k}} 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 k distinct objects, retaining the order of selection, from a set of n objects. The denominator counts the number of distinct sequences that define the same k-combination when order is disregarded.
Due to the symmetry of the binomial coefficient with regard to k and n-k, calculation may be optimised by setting the upper limit of the product above to the smaller of k and n-k.
=== 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:
: \binom nk = \frac{n!}{k!\,(n-k)!} \quad \text{for }\ 0\leq k\leq n,
where n! denotes the factorial of n. This formula follows from the multiplicative formula above by multiplying numerator and denominator by (n-k)!; as a consequence it involves many factors common to numerator and denominator. It is less practical for explicit computation (in the case that k is small and n 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)
: \binom nk = \binom n{n-k} \quad \text{for }\ 0\leq k\leq n,
which leads to a more efficient multiplicative computational routine. Using the falling factorial notation,
: \binom nk = 
\begin{cases}
 n^{\underline{k}}/k! & \operatorname{if }\ k \le \tfrac{n}{2} \\
 n^{\underline{n-k}}/(n-k)! & \operatorname{if }\ k > \tfrac{n}{2}
\end{cases}.
== Combinatorics and statistics ==
Binomial coefficients are of importance in combinatorics, because they provide ready formulas for certain frequent counting problems:
* There are \tbinom n k ways to choose k elements from a set of n elements. See Combination.
* There are \tbinom {n+k-1}k ways to choose k elements from a set of n elements if repetitions are allowed.
* There are \tbinom {n+k} k strings containing k ones and n zeros.
* There are \tbinom {n+1} k strings consisting of k ones and n zeros such that no two ones are adjacent.
* The binomial distribution in statistics is \tbinom n k p^k (1-p)^{n-k} \!.
== See also ==
* Combination
* Permutation
* Binomial distribution
Category:Combinatorics