Definitions

Binomial_coefficient

Binomial coefficient

In mathematics, the binomial coefficient tbinom nk is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n.

In combinatorics, tbinom nk is often called the choose function of n and k; tbinom nk is the number of k-element subsets (the k-combinations) of an n-element set; that is, the number of ways that k things can be 'chosen' from a set of n things.

Definition

Given a non-negative integer n and an integer k, the binomial coefficient is defined to be the natural number

{n choose k} = frac{n cdot (n-1) cdots (n-k+1)} {k cdot (k-1) cdots 1} = frac{n!}{k!(n-k)!} quad mbox{if} 0leq kleq n qquad (1)

and

{n choose k} = 0 quad mbox{if } k < 0 mbox{ or } k>n

where n! denotes the factorial of n.

Alternatively, a recursive definition can be written as

{n choose k} = {n-1 choose k-1} + {n-1 choose k} where
{n choose 0} = {n choose n} = 1

The notation tbinom nk was introduced by Albert von Ettinghausen in 1826, although these numbers were already known centuries before that (see Pascal's triangle). Alternative notations include C(n, k), nCk or C^{k}_{n}, in all of which the C stands for combinations or choices. Indeed, the function (n,k)mapstotbinom nk is often called the choose function, and tbinom nk is often read as "n choose k".

The binomial coefficients are the coefficients of the series expansion of a power of a binomial, hence the name:

(1+x)^n = sum_{k=0}^infty {n choose k} x^k. qquad (2)

If the exponent n is a nonnegative integer then this infinite series is actually a finite sum as all terms with k>n are zero, but if the exponent n is negative or a non-integer, then it is an infinite series. (See the articles on combination and on binomial theorem).

Combinatorial interpretation

The importance of the binomial coefficients (and the motivation for the alternate name 'choose') lies in the fact that {tbinom n k} is the number of ways that k objects can be chosen from among n objects, regardless of order. More formally,

{tbinom n k} is the number of k-element subsets of an n-element set. qquad (1a)

In fact, this property is often chosen as an alternative definition of the binomial coefficient, since from (1a) one may derive (1) as a corollary by a straightforward combinatorial proof. For a colloquial demonstration, note that in the formula

{n choose k} = frac{n cdot (n-1) cdots (n-k+1)}{k cdot (k-1) cdots 1},
the numerator gives the number of ways to fill the k slots using the n options, where the slots are distinguishable from one another. Thus a pizza with mushrooms added before sausage is considered to be different from a pizza with sausage added before mushrooms. The denominator eliminates these repetitions because if the k slots are indistinguishable, then all of the k! ways of arranging them are considered identical.

In the context of computer science, it also helps to see {tbinom n k} as the number of strings consisting of ones and zeros with k ones and nk zeros. For each k-element subset, K, of an n-element set, N, the indicator function, 1K : N→{0,1}, where 1K(x) = 1 whenever x in K and 0 otherwise, produces a unique bit string of length n with exactly k ones by feeding 1K with the n elements in a specific order.

Example

{7 choose 3} = frac{7!}{3!(7-3)!}
= frac{7 cdot 6 cdot 5 cdot 4 cdot 3 cdot 2 cdot 1}{(3 cdot 2 cdot 1)(4 cdot 3 cdot 2 cdot 1)} = frac{7cdot 6 cdot 5}{3cdot 2cdot 1} =frac{210}6 = 35.

The calculation of the binomial coefficient is conveniently arranged like this: ((((5/1)·6)/2)·7)/3 = (((5·6)/2)·7)/3 = ((30/2)·7)/3 = (15·7)/3 = 105/3 = 35, alternately dividing and multiplying with increasing integers. Each division produces an integer result which is itself a binomial coefficient.

Derivation from binomial expansion

For exponent 1, (1+x)1 is 1+x. For exponent 2, (1+x)2 is (1+x)·(1+x), which forms terms as follows. The first factor supplies either a 1 or a x; likewise for the second factor. Thus to form 1, the only possibility is to choose 1 from both factors; To form x2, the only possibility is to choose x from both factors. However, the x term can be formed by 1 from the first and x from the second factor, or x from the first and 1 from the second factor; thus it acquires a coefficient of 2. Proceeding to exponent 3, (1+x)3 reduces to (1+x)2·(1+x), where we already know that (1+x)2= 1+2x+x2, giving an initial expansion of (1+x)·(1+2x+x2). Again the extremes, 1 and x3 arise in a unique way. However, the x term is either 1·2x or x·1, for a coefficient of 3; likewise x2 arises in two ways, summing the coefficients 2 and 1 to give 3.

This suggests an induction. Thus for exponent n, each term of (1+x)n has nk factors of 1 and k factors of x. If k is 0 or n, the term xk arises in only one way, and we get the terms 1 and xn. So {tbinom n 0}=1 and {tbinom n n}=1. If k is neither 0 nor n, then the term xk arises in (1+x)n=(1+x)·(1+x)n−1 in two ways, from 1·xk and from x·xk−1, summing the coefficients {tbinom {n-1} k}+{tbinom {n-1}{k-1}} to give {tbinom n k}. This is the origin of Pascal's triangle, discussed below.

Another perspective is that to form xk from n factors of (1+x), we must choose x from k of the factors and 1 from the rest. To count the possibilities, consider all n! permutations of the factors. Represent each permutation as a shuffled list of the numbers from 1 to n. Select a 1 from the first nk factors listed, and an x from the remaining k factors; in this way each permutation contributes to the term xk. For example, the list 〈4,1,2,3〉 selects 1 from factors 4 and 1, and selects x from factors 2 and 3, as one way to form the term x2 like this: "(1 + x)·(1 + x )·(1 + x )·(1 + x)". But the distinct list 〈1,4,3,2〉 makes exactly the same selection; the binomial coefficient formula must remove this redundancy. The nk factors for 1 have (nk)! permutations, and the k factors for x have k! permutations. Therefore n!/(nk)!k! is the number of distinct ways to form the term xk.

A simpler explanation follows: One can pick a random element out of n in exactly n ways, a second random element in n−1 ways, and so forth. Thus, k elements can be picked out of n in n·(n−1)···(nk+1) ways. In this calculation, however, each order-independent selection occurs k! times, as a list of k elements can be permuted in so many ways. Thus eq. (1) is obtained.

Pascal's triangle

Pascal's rule is the important recurrence relation

{n choose k} + {n choose k+1} = {n+1 choose k+1}, qquad (3)
which follows directly from the definition:
begin{align} {n choose k} + {n choose k+1}
&{}= frac{n!}{k!(n-k)!} + frac{n!}{(k+1)!(n-(k+1))!} &{} = frac{n!(k+1)}{k!(n-k)!(k+1)} + frac{n!(n-k)}{(k+1)!(n-(k+1))!(n-k)} &{} = frac{n!(k+1 + n-k)}{(k+1)!(n-k)!} &{} = frac{(n+1)!}{(k+1)!((n+1)-(k+1))!} &{} = {n+1 choose k+1} end{align}

The recurrence relation just proved can be used to prove by mathematical induction that tbinom n k is a natural number for all n and k, (equivalent to the statement that k! divides the product of k consecutive integers), a fact that is not immediately obvious from the definition.

Combinatorial proof of Pascal's Rule

Let us count the ways of choosing k+1 objects from a set of size n+1. Paint one of the n+1 objects red. The subset of size k+1 either contains the red object or does not. There are n choose k+1 subsets that do not contain the red object (we must choose k+1 non-red objects from the n that are not red), and n choose k subsets that do contain the red object (after we have chosen the red object, it remains to choose k more from the remaining n). Hence {n choose k} + {n choose k+1} = {n+1 choose k+1}, qquad (3)

Pascal's rule also gives rise to Pascal's triangle:

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

Row number n contains the numbers tbinom 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 = 1 x5 + 5 x4y + 10 x3y2 + 10 x2y3 + 5 x y4 + 1 y5.
The differences between elements on other diagonals are the elements in the previous diagonal, as a consequence of 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 evaluating 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:

  • 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 if repetitions are allowed. See Multiset.
  • 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 Catalan numbers are frac {tbinom{2n}n}{n+1}.
  • The binomial distribution in statistics is tbinom n k p^k (1-p)^{n-k} !.
  • The formula for a Bézier curve.

Formulas involving binomial coefficients

When n is an integer

tbinom n k= tbinom n {n-k},qquadqquad(4)

This follows from (2) by using (1 + x)n = xn·(1 + x−1)n. It is reflected in the symmetry of Pascal's triangle.

Another formula is

sum_{k=0}^n tbinom n k = 2^n, qquadqquad(5)

it is obtained from (2) using x = 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. A combinatorial interpretation of this fact is given by counting subsets of size 0, size 1, size 2, and so on up to size n of a set S of n elements. Since we count the number of subsets of size i for 0 ≤ in, this sum must be equal to the number of subsets of S, which is known to be 2n.

The formula

sum_{k=1}^n k tbinom n k = n 2^{n-1} qquad(6)
follows from (2), after differentiating with respect to x and then substituting x = 1.

Vandermonde's identity

sum_j tbinom m j tbinom{n-m}{k-j} = tbinom n k qquad (7a)
is found by expanding (1 + x)m (1 + x)nm = (1 + x)n with (2). As tbinom n k is zero if k > n, the sum is finite for integer n and m. Equation (7a) generalizes equation (3). It holds for arbitrary, complex-valued m and n, the Chu-Vandermonde identity.

A related formula is

sum_m tbinom m j tbinom {n-m}{k-j}= tbinom {n+1}{k+1}. qquad (7b)

While equation (7a) is true for all values of m, equation (7b) is true for all values of j.

From expansion (7a) using n=2m, k = m, and (4), one finds

sum_{j=0}^m tbinom m j ^2 = tbinom {2m} m. qquad (8)

Denote by F(n + 1) the Fibonacci numbers. We obtain a formula about the diagonals of Pascal's triangle

sum_{k=0}^n tbinom {n-k} k = F(n+1). qquad (9)

This can be proved by induction using (3).

Also using (3) and induction, one can show that

sum_{j=k}^n tbinom j k = tbinom {n+1}{k+1}. qquad (10)

Again by (3) and induction, one can show that for k = 0, ... , n−1

sum_{j=0}^k (-1)^jtbinom n j = (-1)^ktbinom {n-1}k qquad(11)

as well as

sum_{j=0}^n (-1)^jtbinom n j = 0 qquad(12)

which is itself a special case of the result that for any integer k = 1, ..., n − 1,

sum_{j=0}^n (-1)^jtbinom n j j^k = 0 qquad(13)
which can be shown by differentiating (2) k times and setting x = −1.

The infinite series

sum_{j=0}^infty frac 1 {tbinom {n+j}n}=frac n{n-1}qquad(14)
is convergent for n ≥ 2. It is the limiting case of the finite sum
sum_{j=0}^k{tbinom {n+j}n}^{-1}=(1-n^{-1})^{-1}(1-{tbinom {n+k}{n-1}}^{-1}).
This formula is proved by mathematical induction on k.

Combinatorial identities involving binomial coefficients

Some identities have combinatorial proofs:

sum_{k=q}^n tbinom n k tbinom k q = 2^{n-q}tbinom n qqquad(15)

for {n} geq {q}. The combinatorial proof goes as follows: the left side counts the number of ways of selecting a subset of [n] of at least q elements, and marking q elements among those selected. The right side counts the same parameter, because there are tbinom n q ways of choosing a set of q marks and they occur in all subsets that additionally contain some subset of the remaining elements, of which there are 2^{n-q}.

This reduces to (6) when q=1.

The identity (8) also has a combinatorial proof. The identity reads

sum_{k=0}^n tbinom n k ^2 = tbinom {2n} n.

Suppose you have 2n empty squares arranged in a row and you want to mark (select) n of them. There are tbinom {2n}n ways to do this. On the other hand, you may select your n squares by selecting k squares from among the first n and n-k squares from the remaining n squares. This gives

sum_{k=0}^ntbinom n ktbinom n{n-k} = tbinom {2n} n.
Now apply (4) to get the result.

Generating functions

The binomial coefficients can also be derived from the labelled case of the Fundamental Theorem of Combinatorial Enumeration. This is done by defining C(n, k) to be the number of ways of partitioning [n] into two subsets, the first of which has size k. These partitions form a combinatorial class with the specification

mathfrak{S}_2(mathfrak{P}(mathcal{Z})) =
mathfrak{P}(mathcal{Z}) mathfrak{P}(mathcal{Z}).

Hence the exponential generating function B of the sum function of the binomial coefficients is given by

B(z) = exp{z} exp{z} = exp(2z),.

This immediately yields

sum_{k=0}^{n} {n choose k} = n! [z^n] exp (2z) = 2^n,

as expected. We mark the first subset with mathcal{U} in order to obtain the binomial coefficients themselves, giving

mathfrak{P}(mathcal{U} ; mathcal{Z}) mathfrak{P}(mathcal{Z}).

This yields the bivariate generating function

B(z, u) = exp uz exp z,.

Extracting coefficients, we find that

{n choose k} = n! [u^k] [z^n] exp uz exp z =
n! [z^n] frac{z^k}{k!} exp z

or

frac{n!}{k!} [z^{n-k}] exp z = frac{n!}{k! , (n-k)!},

again as expected. This derivation closely parallels that of the Stirling numbers of the first and second kind, motivating the binomial-style notation that is used for these numbers.

Divisors of binomial coefficients

The prime divisors of tbinom n k can be interpreted as follows: if p is a prime number and pr is the highest power of p which divides tbinom 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, tbinom n k is always divisible by n/gcd(n,k).

A somewhat surprising result by David Singmaster (1974) is that any integer divides almost all binomial coefficients. More precisely, fix an integer d and let f(N) denote the number of binomial coefficients tbinom n k with n < N such that d divides tbinom n k. Then

lim_{Ntoinfty} frac{f(N)}{N(N+1)/2} = 1.
Since the number of binomial coefficients tbinom n k with n < N is N(N+1) / 2, this implies that the density of binomial coefficients divisible by d goes to 1.

Bounds for binomial coefficients

The following bounds for tbinom n k hold:

left(frac{n}{k}right)^k le {n choose k} le frac{n^k}{k!} le left(frac{ncdot e}{k}right)^k

Generalizations

Generalization to multinomials

Binomial coefficients can be generalized to multinomial coefficients. They are defined to be the number:

{nchoose k_1,k_2,ldots,k_r} =frac{n!}{k_1!k_2!cdots k_r!}
where
sum_{i=1}^rk_i=n

While the binomial coefficients represent the coefficients of (x+y)n, the multinomial coefficients represent the coefficients of the polynomial

(x1 + x2 + ... + xr)n.
See multinomial theorem. The case r = 2 gives binomial coefficients:
{nchoose k_1,k_2}={nchoose k_1, n-k_1}={nchoose k_1}= {nchoose k_2}

The combinatorial interpretation of multinomial coefficients is distribution of n distinguishable elements over r (distinguishable) containers, each containing exactly ki elements, where i is the index of the container.

Multinomial coefficients have many properties similar to these of binomial coefficients, for example the recurrence relation:

{nchoose k_1,k_2,ldots,k_r} ={n-1choose k_1-1,k_2,ldots,k_r}+{n-1choose k_1,k_2-1,ldots,k_r}+ldots+{n-1choose k_1,k_2,ldots,k_r-1}
and symmetry:
{nchoose k_1,k_2,ldots,k_r} ={nchoose k_{sigma_1},k_{sigma_2},ldots,k_{sigma_r}}
where (sigma_i) is a permutation of (1,2,...,r).

Generalization to negative integers

If k geq 0, then {n choose k} = frac{n(n-1) dots (n-k+1)}{1 . 2 dots k}= (-1)^k {-n+k-1 choose k} extends to all n .

The binomial coefficient extends to k leq 0 via

{n choose k}= begin{cases} (-1)^{n-k} {-k-1 choose n-k} quad mbox{if } n geq k, (-1)^{n-k} {-k-1 choose -n-1} quad mbox{if } n leq -1. end{cases}

Notice in particular, that

{n choose k}=0 quad mbox{iff }
begin{cases} n geq 0 mbox{ and } n < k, n geq 0 mbox{ and } k < 0, n < 0 mbox{ and } n < k < 0. end{cases}

This gives rise to the Pascal Hexagon or Pascal Windmill.

Generalization to real and complex argument

The binomial coefficient {zchoose k} can be defined for any complex number z and any natural number k as follows:
{zchoose k} = prod_{n=1}^{k}{z-k+nover n}= frac{z(z-1)(z-2)cdots (z-k+1)}{k!}. qquad (14)

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).

Alternatively, the infinite product

(-1)^k {z choose k}= {-z+k-1 choose k} = frac{1}{Gamma(-z)} frac{1}{(k+1)^{z+1}} prod_{j=k+1} frac{(1+frac{1}{j})^{-z-1}}{1-frac{z+1}{j}}
may be used to generalize the binomial coefficient. This formula discloses that asymptotically {z choose k} approx frac{(-1)^k}{Gamma(-z) k^{z+1}} as k to infty.

For fixed k, the expression f(z)={zchoose k} is a polynomial in z of degree k with rational coefficients. f(z) is the unique polynomial of degree k satisfying

f(0) = f(1) = ... = f(k − 1) = 0 and f(k) = 1.

Any polynomial p(z) of degree d can be written in the form

p(z) = sum_{k=0}^{d} a_k {zchoose k}.

This is important in the theory of difference equations and finite differences, and can be seen as a discrete analog of Taylor's theorem. It is closely related to Newton's polynomial. Alternating sums of this form may be expressed as the Nörlund-Rice integral.

In particular, one can express the product of binomial coefficients as such a linear combination:

{xchoose m} {xchoose n} = sum_{k=0}^m {m+n-kchoose k,m-k,n-k} {xchoose m+n-k}

where the connection coefficients are multinomial coefficients. In terms of labelled combinatorial objects, the connection coefficients represent the number of ways to assign m+n-k labels to a pair of labelled combinatorial objects of weight m and n respectively, that have had their first k labels identified, or glued together, in order to get a new labelled combinatorial object of weight m+n-k. (That is, to separate the labels into 3 portions to be applied to the glued part, the unglued part of the first object, and the unglued part of the second object.) In this regard, binomial coefficients are to exponential generating series what falling factorials are to ordinary generating series.

Newton's binomial series

Newton's binomial series, named after Sir Isaac Newton, is one of the simplest Newton series:

(1+z)^{alpha} = sum_{n=0}^{infty}{alphachoose n}z^n = 1+{alphachoose1}z+{alphachoose 2}z^2+cdots.

The identity can be obtained by showing that both sides satisfy the differential equation (1+z) f'(z) = α f(z).

The radius of convergence of this series is 1. An alternative expression is

frac{1}{(1-z)^{alpha+1}} = sum_{n=0}^{infty}{n+alpha choose n}z^n

where the identity

{n choose k} = (-1)^k {k-n-1 choose k}

is applied.

The formula for the binomial series was etched onto Newton's gravestone in Westminster Abbey in 1727.

Two real or complex valued arguments

The binomial coefficient is generalized to two real or complex valued arguments using gamma function or Beta function via
{x choose y}:= frac{Gamma(x+1)}{Gamma(y+1) Gamma(x-y+1)}= frac{1}{(x+1) Beta(x-y+1,y+1)}.
This definition inherits these following additional properties from Gamma:
{x choose y}= frac{sin (y pi)}{sin(x pi)} {-y-1 choose -x-1}= frac{sin((x-y) pi)}{sin (x pi)} {y-x-1 choose y};
moreover,
{x choose y} cdot {y choose x}= frac{sin((x-y) pi)}{(x-y) pi}.

Generalization to q-series

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

Generalization to infinite cardinals

The definition of the binomial coefficient can be generalized to infinite cardinals by defining:

{alpha choose beta} = | { B subseteq A : |B| = beta } |

where A is some set with cardinality alpha. One can show that the generalized binomial coefficient is well-defined, in the sense that no matter what set we choose to represent the cardinal number alpha, {alpha choose beta} will remain the same. For finite cardinals, this definition coincides with the standard definition of the binomial coefficient.

Assuming the Axiom of Choice, one can show that {alpha choose alpha} = 2^{alpha} for any infinite cardinal alpha.

Binomial coefficient in programming languages

The notation {n choose k} is convenient in handwriting but inconvenient for typewriters and computer terminals. Many programming languages do not offer a standard subroutine for computing the binomial coefficient, but for example the J programming language uses the exclamation mark: k ! n .

Naive implementations, such as the following snippet in C:

int choose(int n, int k)  {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

are prone to overflow errors, severely restricting the range of input values. A direct implementation of the first definition works well:

unsigned long long choose(unsigned n, unsigned k) {
    if (k > n)
        return 0;

    if (k > n/2)
        k = n-k; // faster

    long double accum = 1;
    for (unsigned i = 1; i <= k; i++)
         accum = accum * (n-k+i) / i;

    return accum + 0.5; // avoid rounding error
}

See also

References

Search another word or see Binomial_coefficienton Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature