Search

The Online Encyclopedia and Dictionary

 
     
 

Encyclopedia

Dictionary

Quotes

 

Binomial coefficient

See binomial (disambiguation) for a list of other topics called by that name.
Contents

Formal definition

In mathematics, in particular in combinatorics, the binomial coefficient of the integer numbers n and k is defined as a coefficient of the xk in the expansion of (1 + x)n (cf. binomial theorem):

(1+x)^n = {n\choose 0} + {n\choose 1}x + {n\choose 2}x^2 + \dots = \sum_k {n\choose k} x^k. \qquad (1)

In particular, the following formulae hold

{n \choose k} = \frac{n!}{k!(n-k)!} \quad \mbox{if } n\geq k\geq 0 \qquad \mbox{(1)}
{n \choose k} = 0 \quad \mbox{if } k<0 \mbox{ or } k>n\geq 0
{n \choose k} = (-1)^k {-n+k-1 \choose k} \quad \mbox{if } n<0\leq k.

(Here, for a natural number m, m! denotes the factorial of m.) For example,

{7 \choose 3} = \frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35.

The binomial coefficient {n \choose k} read as "n choose k". For non-negative integers n and k, it can be also written as C(n, k) or C_n^k which stands for the number combinations of k things taken out of n things.

According to Nicholas J. Higham , the {n \choose k} notation was introduced by Albert von Ettinghausen in 1826, although these numbers have been known centuries before that; see Pascal's triangle.

The name binomial comes from the expansion of the binomial (x + y)n (for integer n\geq 0):

(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k} \qquad (2)

This is generalized by the binomial theorem, which allows the exponent n to be negative or a non-integer. Binomial coefficient is a partial case of multinomial coefficient.

Pascal's triangle

The important recurrence relation

C(n,k) + C(n,k+1) = C(n+1,k+1) \qquad (3)

follows directly from the definition. This recurrence relation can be used to prove by mathematical induction that C(n, k) is a natural number for all n and k, a fact that is not immediately obvious from the definition.

It also gives rise to Pascal's triangle:

row 0                     1
row 1                   1   1
row 2                 1   2   1
row 3               1   3   3   1
row 4             1   4   6   4   1
row 5           1   5   10  10   5   1
row 6         1   6   15  20  15   6   1
row 7       1   7   21  35  35   21  7   1
row 8     1   8   28  56  70  56   28  8   1

Row number n contains the numbers C(n, k) for k = 0,...,n. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath. This method allows the quick calculation of binomial coefficients without the need for fractions or multiplications. For instance, by looking at row number 5 of the triangle, one can quickly read off that

(x + y)5 = 1x5 + 5 x4y + 10 x3y2 + 10 x2y3 + 5 x y4 + 1y5.

The differences between elements on other diagonals are the elements in the previous diagonal - consequential to the recurrence relation (3) above.

In the 1303 AD treatise Precious Mirror of the Four Elements, Zhu Shijie mentioned the triangle as an ancient method for solving binomial coefficients indicating that the method was known to Chinese mathematicians five centuries before Pascal.

Combinatorics and statistics

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

  • Every set with n elements has {n\choose k} different subsets having k elements each (these are called k-combinations), set of all k-combinations of the set S often is denoted by {S\choose k}.
  • The number of strings of length n containing k ones and n − k zeros is {n\choose k}.
  • There are C(n + 1, k) strings consisting of k ones and n zeros such that no two ones are adjacent.
  • The number of sequences consisting of n natural numbers whose sum equals k is {n+k-1\choose k}; this is also the number of ways to choose k elements from a set of n if repetitions are allowed, denoted by \left({n\choose k}\right).
  • The Catalan numbers have an easy formula involving binomial coefficients; they can be used to count various structures, such as trees and parenthesized expressions.

The binomial coefficients also occur in the formula for the binomial distribution in statistics and in the formula for a Bézier curve.

Formulas involving binomial coefficients

The following formulas are occasionally useful:

C(n,k)=C(n, n-k)\qquad\qquad(4)\,

This follows from expansion (2) by using (x + y)n = (y + x)n, and is reflected in the numerical "symmetry" of Pascal's triangle.

\sum_{k=0}^{n} \mathrm{C}(n,k) = 2^n \qquad (5)

From expansion (2) using x = y = 1. This is equivalent to saying that the elements in one row of Pascal's Triangle always add up to two raised to an integer power.

\sum_{k=1}^{n} k \mathrm{C}(n,k) = n 2^{n-1} \qquad (6)

From expansion (2), after differentiating and substituting x = y = 1.

\sum_{j=0}^{k} \mathrm{C}(m,j) \mathrm{C}(n,k-j) = \mathrm{C}(m+n,k) \qquad (7)

By expanding (x + y)n (x + y)m = (x + y)m+n with (2) (note that C(n, k) is defined to be zero if k > n). This equation generalizes (3).

\sum_{k=0}^{n} \mathrm{C}(n,k)^2 = \mathrm{C}(2n,n) \qquad (8)

From expansion (7) using m = k = n and (4).

\sum_{k=0}^{n} \mathrm{C}(n-k,k) = \mathrm{F}(n+1) \qquad (9)

Here, F(n + 1) denotes the Fibonacci numbers. This formula about the diagonals of Pascal's triangle can be proven with induction using (3).

\sum_{j=k}^{n} \mathrm{C}(j,k) = \mathrm{C}(n+1,k+1) \qquad (10)

This can be proven by induction on n using (3).

Divisors of binomial coefficients

The prime divisors of C(n, k) can be interpreted as follows: if p is a prime number and pr is the highest power of p which divides C(n, k), then r is equal to the number of natural numbers j such that the fractional part of k/pj is bigger than the fractional part of n/pj. In particular, C(n, k) is always divisible by n/gcd(n,k).

Generalization to complex arguments

The binomial coefficient {z\choose k} can be defined for any complex number z and any natural number k as follows:

{z\choose k} = {1 \over k!}\prod_{n=0}^{k-1}(z-n)= \frac{z(z-1)(z-2)\cdots (z-k+1)}{k!} \qquad (11)

This generalization is known as the generalized binomial coefficient and is used in the formulation of the binomial theorem and satisfies properties (3) and (7).

For fixed k, the expression {z\choose k} is a polynomial in z of degree k with rational coefficients. Every polynomial p(z) of degree d can be written in the form

p(z) = \sum_{k=0}^{d} a_k {z\choose k}

with suitable constants ak. This is important in the theory of difference equations and can be seen as a discrete analog of Taylor's theorem.

Generalization to q-series

The binomial coefficient has a q-analog generalization known as the Gaussian binomial.

See also

Last updated: 06-02-2005 04:08:42
The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy