Binomial coefficient
this wiki
In mathematics, the binomial coefficient is the coefficient of the x^{ k} term in the polynomial expansion of the binomial power (1 + x)^{ n}.
In combinatorics, is interpreted as 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. Hence, is often read as "n choose k" and is called the choose function of n and k.
The notation was introduced by Andreas von Ettingshausen in 1826,^{[1]} although the numbers were already known centuries before that (see Pascal's triangle). Alternative notations include C(n, k), _{n}C_{k}, ^{n}C_{k}, ,^{[2]} in all of which the C stands for combinations or choices.
Definition
Factorial definition
For non-negative integers n and k, the binomial coefficient is defined by the factorial representation
and
where n! denotes the factorial of n.
Recursive definition
Alternatively, a recursive definition can be written as
with
which shows that the binomial coefficient of non-negative integers n and k is always a natural number. This recursive definition produces Pascal's triangle.
Product definition
More generally, for a real or complex number α and an integer k, the (generalized) binomial coefficient^{[note 1]} is defined by the product representation
and
This extends the factorial definition, because for k = 0 the formula (1b) is the empty product, which is defined as 1, and if α is a non-negative integer smaller than k, then a zero appears as nominator of one of the factors in (1b).
Connection to the binomial series and the binomial theorem
The binomial coefficients are the coefficients of the binomial series of a power of a binomial, hence the name: For all complex numbers α and x with |x| < 1,
If the exponent α is a nonnegative integer n, then this infinite series is actually a finite sum as all terms with k > n are zero, thereby recovering the binomial theorem.
Combinatorial interpretation
The importance of the binomial coefficients (and the motivation for the alternate name choose) lies in the fact that is the number of ways that k objects can be chosen from among n objects, when order is irrelevant. More formally, for non-negative integers n and k,
- is the number of k-element subsets (combinations) of an n-element set.
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
the numerator gives the number of ways to fill the k slots using the n options, where the slots are distinguishable from one another. An example of this case is where the slots are numbered (and the options are distinguishable), such as choosing names from a list and putting them in a particular order. The denominator eliminates these repetitions because if the k slots are indistinguishable, then all of the k! ways of arranging them are considered identical.
Combinations with repetition can also be expressed in terms of binomial coefficients, namely as ; see number of combinations with repetition.
In the context of computer science, it also helps to see as the number of strings of n bits with Hamming weight k, i.e. consisting of ones and zeros with k ones and n − k zeros. For each k-element subset K of an n-element set N, the indicator function 1_{K} : N → {0,1}, where 1_{K }(x) = 1 whenever x is in K and 0 otherwise, produces a unique bit string of length n with exactly k ones by feeding 1_{K} with the n elements in a specific order.^{[3]}
Example
If you have a bag of 7 different colored rocks, how many three-rock combinations are there?
Another example would be the odds of winning a lottery jackpot in which you pick 6 numbers from 49 à la Lotto 6/49.
- or about 1 in 14 million.
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 an x; likewise for the second factor. Thus to form 1, the only possibility is to choose 1 from both factors; To form x^{2}, 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 + x^{2}, giving an initial expansion of (1 + x)·(1 + 2x + x^{2}). Again the extremes, 1 and x^{3} arise in a unique way. However, the x term is either 1·2x or x·1, for a coefficient of 3; likewise x^{2} 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 n − k factors of 1 and k factors of x. If k is 0 or n, the term x^{k} arises in only one way, and we get the terms 1 and x^{n}. So and If k is neither 0 nor n, then the term x^{k} arises in (1 + x)^{n} = (1 + x)·(1 + x)^{n−1} in two ways, from 1·x^{k} and from x·x^{k−1}, summing the coefficients to give . This is the origin of Pascal's triangle, discussed below.
Another perspective is that to form x^{k} 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 n − k factors listed, and an x from the remaining k factors; in this way each permutation contributes to the term x^{k}. 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 x^{2} 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 n − k factors for 1 have (n − k)! permutations, and the k factors for x have k! permutations. Therefore n!/(n − k)!k! is the number of distinct ways to form the term x^{k}.
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)···(n − k + 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
which can be used to prove by mathematical induction that 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 formula (1).
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: 1 7 21 35 35 21 7 1 8: 1 8 28 56 70 56 28 8 1
Row number n contains the numbers 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 x^{5} + 5 x^{4}y + 10 x^{3}y^{2} + 10 x^{2}y^{3} + 5 x y^{4} + 1 y^{5}.
The differences between elements on other diagonals are the elements in the previous diagonal, as a consequence of the recurrence relation (3) above.
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 k elements from a set of n elements. See Combination.
- There are ways to choose k elements from a set of n if repetitions are allowed. See Multiset.
- There are strings containing k ones and n zeros.
- There are strings consisting of k ones and n zeros such that no two ones are adjacent.
- The Catalan numbers are
- The binomial distribution in statistics is
- The formula for a Bézier curve.
Binomial coefficients as polynomials
For any nonnegative integer k, the expression can be simplified and defined as a permutation divided by k!, which, itself, is a permutation:
This presents a polynomial in t with rational coefficients.
As such, it can be evaluated at any real or complex number t to define binomial coefficients with such first arguments. These "generalized binomial coefficients" appear in Newton's generalized binomial theorem.
For each k, the polynomial can be characterized as the unique degree k polynomial p(t) satisfying p(0) = p(1) = ... = p(k − 1) = 0 and p(k) = 1.
Its coefficients are expressible in terms of Stirling numbers of the first kind, by definition of the latter:
The derivative of can be calculated by logarithmic differentiation:
Binomial coefficients as a basis for the space of polynomials
Over any field containing Q, each polynomial p(t) of degree at most d is uniquely expressible as a linear combination . The coefficient a_{k} is the k^{th} difference of the sequence p(0), p(1), …, p(k). Explicitly,^{[note 2]}
Integer-valued polynomials
Each polynomial is integer-valued: it takes integer values at integer inputs. (One way to prove this is by induction on k, using Pascal's identity.) Therefore any integer linear combination of binomial coefficient polynomials is integer-valued too. Conversely, (3.5) shows that any integer-valued polynomial is an integer linear combination of these binomial coefficient polynomials. More generally, for any subring R of a characteristic 0 field K, a polynomial in K[t] takes values in R at all integers if and only if it is an R-linear combination of binomial coefficient polynomials.
Example
The integer-valued polynomial 3t(3t + 1)/2 can be rewritten as
Identities involving binomial coefficients
For any nonnegative integers n and k,
This follows from (2) by using (1 + x)^{n} = x^{n}·(1 + x^{−1})^{n}. It is reflected in the symmetry of Pascal's triangle. A combinatorial interpretation of this formula is as follows: when forming a subset of elements (from a set of size ), it is equivalent to consider the number of ways you can pick elements and the number of ways you can exclude elements.
The factorial definition lets one relate nearby binomial coefficients. For instance, if k is a positive integer and n is arbitrary, then
and, with a little more work,
Powers of -1
A special binomial coefficient is , as that equals powers of -1:
Series involving binomial coefficients
Another formula is
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 involving double counting 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 ≤ i ≤ n, this sum must be equal to the number of subsets of S, which is known to be 2^{n}.
The formulas
and
follows from (2), after differentiating with respect to x (twice in the latter) and then substituting x = 1.
is found by expanding (1 + x)^{m} (1 + x)^{n−m} = (1 + x)^{n} with (2). As 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 and , the Chu-Vandermonde identity.
A related formula is
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
Let F(n) denote the n^{th} Fibonacci number. We obtain a formula about the diagonals of Pascal's triangle
This can be proved by induction using (3).
Also using (3) and induction, one can show that
Again by (3) and induction, one can show that for k = 0, ... , n−1
as well as
which is itself a special case of the result from the theory of finite differences that for any polynomial P(x) of degree less than n,
Differentiating (2) k times and setting x = −1 yields this for , when 0 ≤ k < n, and the general case follows by taking linear combinations of these.
When P(x) is of degree less than or equal to n,
where is the coefficient of degree n in P(x).
More generally for 13b,
where m and d are complex numbers. This follows immediately applying (13b) to the polynomial Q(x):=P(m + dx) instead of P(x), and observing that Q(x) has still degree less than or equal to n, and that its coefficient of degree n is d^{n}a_{n}.
The infinite series
is convergent for k ≥ 2. This formula is used in the analysis of the German tank problem. It is equivalent to the formula for the finite sum
which is proved for M>m by induction on M.
Using (8) one can derive
and
Identities with combinatorial proofs
Many identities involving binomial coefficients can be proved by combinatorial means. For example, the following identity for nonnegative integers (which reduces to (6) when ):
can be given a double counting proof as follows. The left side counts the number of ways of selecting a subset of of at least q elements, and marking q elements among those selected. The right side counts the same parameter, because there are 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
The recursion formula
where both sides count the number of k-element subsets of {1, 2, . . . , n} with the right hand side ﬁrst grouping them into those which contain element n and those which don’t.
The identity (8) also has a combinatorial proof. The identity reads
Suppose you have empty squares arranged in a row and you want to mark (select) n of them. There are ways to do this. On the other hand, you may select your n squares by selecting k squares from among the first n and squares from the remaining n squares. This gives
Now apply (4) to get the result.
Continuous identities
Certain trigonometric integrals have values expressible in terms of binomial coefficients:
For and
These can be proved by using Euler's formula to convert trigonometric functions to complex exponentials, expanding using the binomial theorem, and integrating term by term.
Generating functions
Ordinary generating functions
For a fixed n, the ordinary generating function of the sequence is:
For a fixed k, the ordinary generating function of the sequence is:
The bivariate generating function of the binomial coefficients is:
Exponential generating functions
The binomial coefficients can also be derived from the labelled case of the Fundamental Theorem of Combinatorial Enumeration. This is done by interpreting as the number of ways to partition the set into two subsets of size k and n-k. These partitions form a combinatorial class with the specification
Hence the exponential generating function B of the sum function of the binomial coefficients is given by
This immediately yields
as expected. We mark the first subset with in order to obtain the binomial coefficients themselves, giving
This yields the bivariate generating function
Extracting coefficients, we find that
or
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.
Divisibility properties
In 1852, Kummer proved that if m and n are nonnegative integers and p is a prime number, then the largest power of p dividing equals p^{c}, where c is the number of carries when m and n are added in base p. Equivalently, the exponent of a prime p in equals the number of positive integers j such that the fractional part of k/p^{j} is greater than the fractional part of n/p^{j}. It can be deduced from this that is 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 with n < N such that d divides . Then
Since the number of binomial coefficients with n < N is N(N+1) / 2, this implies that the density of binomial coefficients divisible by d goes to 1.
Another fact: An integer n ≥ 2 is prime if and only if all the intermediate binomial coefficients
are divisible by n.
Proof: When p is prime, p divides
- for all 0 < k < p
because it is a natural number and the numerator has a prime factor p but the denominator does not have a prime factor p.
When n is composite, let p be the smallest prime factor of n and let k = n/p. Then 0 < p < n and
otherwise the numerator k(n−1)(n−2)×...×(n−p+1) has to be divisible by n = k×p, this can only be the case when (n−1)(n−2)×...×(n−p+1) is divisible by p. But n is divisible by p, so p does not divide n−1, n−2, ..., n−p+1 and because p is prime, we know that p does not divide (n−1)(n−2)×...×(n−p+1) and so the numerator cannot be divisible by n.
Bounds and asymptotic formulas
The following bounds for hold:
Stirling's approximation yields:
- and in general for m ≥ 2 and n ≥ 1.
The infinite product formula (cf. Gamma function, alternative definition)
yields the asymptotic formulas
as .
This asymptotic behaviour is contained in the approximation
as well. (Here is the k^{th} harmonic number and is the Euler–Mascheroni constant).
The sum of binomial coefficients can be bounded by a term exponential in and the binary entropy of the largest that occurs. More precisely, for and , it holds
where is the binary entropy of .^{[4]}
A simple and rough upper bound for the sum of binomial coefficients is given by the formula below (not difficult to prove)
Generalizations
Generalization to multinomials
Binomial coefficients can be generalized to multinomial coefficients. They are defined to be the number:
where
While the binomial coefficients represent the coefficients of (x+y)^{n}, the multinomial coefficients represent the coefficients of the polynomial
See multinomial theorem. The case r = 2 gives binomial coefficients:
The combinatorial interpretation of multinomial coefficients is distribution of n distinguishable elements over r (distinguishable) containers, each containing exactly k_{i} 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:
and symmetry:
where is a permutation of (1,2,...,r).
Generalization to negative integers
If , then extends to all .
Taylor series
Using Stirling numbers of the first kind the series expansion around any arbitrarily chosen point is
Binomial coefficient with n=.5
The definition of the binomial coefficients can be extended to the case where is real and is integer.
In particular, the following identity holds for any non-negative integer :
This shows up when expanding into a power series using the Newton binomial series :
Identity for the product of binomial coefficients
One can express the product of binomial coefficients as a linear combination of binomial coefficients:
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.
Partial Fraction Decomposition
The partial fraction decomposition of the inverse is given by
- and
Newton's binomial series
Newton's binomial series, named after Sir Isaac Newton, is one of the simplest Newton series:
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
where the identity
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 the gamma function or beta function via
This definition inherits these following additional properties from :
moreover,
The resulting function has been little-studied, apparently first being graphed in (Fowler 1996). Notably, many binomial identities fail: but for n positive (so negative). The behavior is quite complex, and markedly different in various octants (that is, with respect to the x and y axes and the line ), with the behavior for negative x having singularities at negative integer values and a checkerboard of positive and negative regions:
- in the octant it is a smoothly interpolated form of the usual binomial, with a ridge ("Pascal's ridge").
- in the octant and in the quadrant the function is close to zero.
- in the quadrant the function is alternatingly very large positive and negative on the parallelograms with vertices
- in the octant the behavior is again alternatingly very large positive and negative, but on a square grid.
- in the octant it is close to zero, except for near the singularities.
Generalization to q-series
The binomial coefficient has a q-analog generalization known as the Gaussian binomial coefficient.
Generalization to infinite cardinals
The definition of the binomial coefficient can be generalized to infinite cardinals by defining:
where A is some set with cardinality . 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 , 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 for any infinite cardinal .
Binomial coefficient in programming languages
The notation 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; // Take advantage of symmetry long double accum = 1; unsigned i; for (i = 1; i <= k; i++) accum = accum * (n-k+i) / i; return accum + 0.5; // avoid rounding error }
Another way to compute the binomial coefficient when using large numbers is to recognize that
is a special function that is easily computed and is standard in some programming languages such as using LogGamma in Mathematica or gammaln in MATLAB. Roundoff error may cause the returned value to not be an integer.
References
This page uses content from Wikipedia. The original article was at Binomial coefficient. The list of authors can be seen in the page history. As with the Math Wiki, the text of Wikipedia is available under the Creative Commons Licence. |
- ↑ Nicholas J. Higham. Handbook of writing for the mathematical sciences. SIAM. p. 25. ISBN 0898714206.
- ↑ G. E. Shilov (1977). Linear algebra. Dover Publications. ISBN 9780486635187.
- ↑ PlanetMath: binomial coefficient
- ↑ see e.g. Template:Harvtxt
- Fowler, David (January 1996), "The Binomial Coefficient Function", The American Mathematical Monthly 103 (1): 1–17, http://www.jstor.org/stable/2975209
- Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Third ed.). Addison-Wesley. pp. 52–74. ISBN 0-201-89683-4.
- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (Second ed.). Addison-Wesley. pp. 153–256. ISBN 0-201-55802-5.
- Singmaster, David (1974). "Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients". J. London Math. Soc. (2) 8: 555–560. doi:10.1112/jlms/s2-8.3.555.
- Bryant, Victor (1993). Aspects of combinatorics. Cambridge University Press.
- Arthur T. Benjamin; Jennifer Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.
- Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0.
Cite error:
<ref>
tags exist for a group named "note", but no corresponding <references group="note"/>
tag was found.