In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+1)^{n}. Colloquially, given, say n pizza toppings to select from, if one wishes to bake a pizza with exactly k toppings, then the binomial coefficient expresses how many different types of such ktopping pizzas are possible. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ...
Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ...
In mathematics, a coefficient is a constant multiplicative factor of a certain object. ...
In elementary algebra, a binomial is a polynomial with two terms: the sum of two monomials. ...
Definition
Given a nonnegative integer n and an integer k, the binomial coefficient is defined to be the natural number and where n! denotes the factorial of n. For factorial rings in mathematics, see unique factorisation domain. ...
According to Nicholas J. Higham, the notation 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), _{n}C_{k} or , in all of which the C stands for combination or choose. Indeed, another name for the binomial coefficient is choose function, and the binomial coefficient of n and k is often read as "n choose k". Nicholas J. Higham FRS (born Salford 25 December 1961[1]) is a numerical analyst and Richardson Professor of Applied Mathematics at the School of Mathematics, University of Manchester. ...
The oldest surviving photograph, NicÃ©phore NiÃ©pce, circa 1826 1826 (MDCCCXXVI) was a common year starting on Sunday (see link for calendar) of the Gregorian calendar (or a common year starting on Tuesday of the 12dayslower Julian calendar). ...
The first five rows of Pascals triangle In mathematics, Pascals triangle is a geometric arrangement of the binomial coefficients in a triangle. ...
In combinatorial mathematics, a combination is an unordered collection of unique elements. ...
The binomial coefficients are the coefficients in the expansion of the binomial (x + y)^{n} (hence the name): In mathematics, a coefficient is a constant multiplicative factor of a certain object. ...
This is generalized by the binomial theorem, which allows the exponent n to be negative or a noninteger. See the article on combination. In mathematics, the binomial theorem is an important formula giving the expansion of powers of sums. ...
In combinatorial mathematics, a combination is an unordered collection of unique elements. ...
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, regardless of order. More formally,  is the number of kelement subsets of an nelement 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 A combinatorial proof is a method of proving a statement, usually a combinatorics identity, by counting some carefully chosen object in different ways to obtain different expressions in the statement (see also double counting). ...
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 chicken is considered to be different from a pizza with chicken 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.
Example The calculation of the binomial coefficient is conveniently arranged like this: ((((5/1)·6)/2)·7)/3, 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, (x+y)^{1} is x+y. For exponent 2, (x+y)^{2} is (x+y)(x+y), which forms terms as follows. The first factor supplies either an x or a y; likewise for the second factor. Thus to form x^{2}, the only possibility is to choose x from both factors; likewise for y^{2}. However, the xy term can be formed by x from the first and y from the second factor, or y from the first and x from the second factor; thus it acquires a coefficient of 2. Proceeding to exponent 3, (x+y)^{3} reduces to (x+y)^{2}(x+y), where we already know that (x+y)^{2}= x^{2}+2xy+y^{2}, giving an initial expansion of (x+y)(x^{2}+2xy+y^{2}). Again the extremes, x^{3} and y^{3} arise in a unique way. However, the x^{2}y term is either 2xy times x or x^{2} times y, for a coefficient of 3; likewise xy^{2} arises in two ways, summing the coefficients 1 and 2 to give 3. This suggests an induction. Thus for exponent n, each term has total degree (sum of exponents) n, with n−k factors of x and k factors of y. If k is 0 or n, the term arises in only one way, and we get the terms x^{n} and y^{n}. If k is neither 0 nor n, then the term arises in two ways, from x^{nk1}y^{k} × x and from x^{nk}y^{k1} × y. For example, x^{2}y^{2} is both xy^{2} times x and x^{2}y times y, thus its coefficient is 3 (the coefficient of xy^{2}) + 3 (the coefficient of x^{2}y). This is the origin of Pascal's triangle, discussed below. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...
This article is about the term degree as used in mathematics. ...
Another perspective is that to form x^{n−k}y^{k} from n factors of (x+y), we must choose y from k of the factors and x 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 an x from the first n−k factors listed, and a y from the remaining k factors; in this way each permutation contributes to the term x^{n−k}y^{k}. For example, the list 〈4,1,2,3〉 selects x from factors 4 and 1, and selects y from factors 2 and 3, as one way to form the term x^{2}y^{2}. Permutation is the rearrangement of objects or symbols into distinguishable sequences. ...
 (x +^{1} y)(x +^{2} y)(x +^{3} y)(x +^{4} y)
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 x have (n−k)! permutations, and the k factors for y have k! permutations. Therefore n!/(n−k)!k! is the number of truly distinct ways to form the term x^{n−k}y^{k}. A much more intuitive and simple explananation 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 ways. In this calculation, however, each orderindependent 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 In mathematics, Pascals rule is a combinatorial identity about binomial coefficients. ...
In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...
which follows directly from the definition: The recurrence relation just proved 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. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...
Pascal's rule also gives rise to Pascal's triangle: The first five rows of Pascals triangle In mathematics, Pascals triangle is a geometric arrangement of the binomial coefficients in a 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 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} = 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. 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. Zhu Shijie (Chinese: æœ±ä¸–æ°, Styled Hanqing å—æ¼¢å¿ï¼Œè™Ÿæ¾åº) ( mid1270s?1330?) also known as Chu ShihChieh was one of the greatest Chinese mathematicians. ...
This article or section is in need of attention from an expert on the subject. ...
Blaise Pascal (pronounced ), (June 19, 1623â€“August 19, 1662) was a French mathematician, physicist, and religious philosopher. ...
Combinatorics and statistics Binomial coefficients are of importance in combinatorics, because they provide ready formulas for certain frequent counting problems: Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ...
 Every set with n elements has C(n,k) different subsets having k elements each (these are called kcombinations).
 The number of strings of length n containing k ones and n − k zeros is C(n,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 C(n + k − 1,k); this is also the number of ways to choose k elements from a set of n if repetitions are allowed.
 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. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...
In combinatorial mathematics, a combination is an unordered collection of unique elements. ...
In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. ...
A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
In probability theory and statistics, the binomial distribution is the discrete probability distribution of the number of successes in a sequence of n independent yes/no experiments, each of which yields success with probability p. ...
A graph of a normal bell curve showing statistics used in educational assessment and comparing various grading methods. ...
Cubic BÃ©zier curve In the mathematical field of numerical analysis, a BÃ©zier curve is a parametric curve important in computer graphics. ...
Formulas involving binomial coefficients One has that This follows immediately from the definition or can be seen from expansion (2) by using (x + y)^{n} = (y + x)^{n}, and is reflected in the numerical "symmetry" of Pascal's triangle. The first five rows of Pascals triangle In mathematics, Pascals triangle is a geometric arrangement of the binomial coefficients in a triangle. ...
Another formula is it is obtained 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. A combinatorial proof 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 ≤ i ≤ n, this sum must be equal to the number of subsets of S, which is known to be 2^{n}. The formula follows from expansion (2), after differentiating with respect to either x or y and then substituting x = y = 1. For a nontechnical overview of the subject, see Calculus. ...
Vandermonde's identity In combinatorial mathematics, Vandermondes identity, named after AlexandreThéophile Vandermonde, states that This may be proved by simple algebra relying on the fact that (see factorial) but it also admits a more combinatoricsflavored bijective proof, as follows. ...
is found by expanding (1+x)^{m} (1+x)^{nm} = (1+x)^{n} with (2). As C(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, complexvalued m and n, the ChuVandermonde identity. In combinatorial mathematics, Vandermondes identity, named after AlexandreThÃ©ophile Vandermonde, states that Proof This may be proved by simple algebra relying on the fact that (see factorial) but it also admits a more combinatoricsflavored bijective proof, as follows. ...
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 Denote by F(n + 1) the Fibonacci numbers. We obtain a formula about the diagonals of Pascal's triangle A tiling with squares whose sides are successive Fibonacci numbers in length A Fibonacci spiral, created by drawing arcs connecting the opposite corners of squares in the Fibonacci tiling shown above â€“ see golden spiral. ...
This can be proved by induction using (3). Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...
Also using (3) and induction, one can show that Again by (3) and induction, one can show that for k=0,...,n1 Also, a useful notation to know when proving futher identities is
Combinatorial identities involving binomial coefficients We present some identities that have combinatorial proofs. We have, for example, for 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 C(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 Suppose you have 2n empty squares arranged in a row and you want to mark (select) n of them. There are C(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 Now apply (4) to get the result.
Generating functions If we didn't know about binomial coefficients we could derive them using 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 The fundamental theorem of combinatorial enumeration is a theorem in combinatorics that solves the enumeration problem of labelled and unlabelled combinatorial classes. ...
Hence the exponential generating function B of the sum function of the binomial coefficients is given by In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...
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 is included here because it closely parallels that of the Stirling numbers of the first and second kind, and hence lends support to the binomialstyle notation that is used for these numbers. In mathematics, Stirling numbers arise in a variety of combinatorics problems. ...
Divisors of binomial coefficients The prime divisors of C(n, k) can be interpreted as follows: if p is a prime number and p^{r} 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/p^{j} is bigger than the fractional part of n/p^{j}. In particular, C(n, k) is always divisible by n/gcd(n,k). In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ...
In mathematics, the floor function is the function defined as follows: for a real number x, floor(x) is the largest integer less than or equal to x. ...
In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two nonzero integers, is the largest positive integer that divides both numbers without remainder. ...
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 C(n, k) with n < N such that d divides C(n, k). Then David Singmaster is a professor of Mathematics at Londons South Bank University. ...
In mathematics, the phrase almost all has a number of specialised uses. ...
Since the number of binomial coefficients C(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 C(n, k) hold: Generalization to multinomials While the binomial coefficients represent the coefficients of (x+y)^{n}, the multinomial coefficients represent the coefficients of  (x_{1} + x_{2} + ... + x_{k})^{n}.
See multinomial theorem. The case k = 2 gives binomial coefficients. In mathematics, the multinomial formula is an expression of a power of a sum in terms of powers of the addends. ...
Generalization to negative integers The definition can be extended to negative integers as follows: and and This gives rise to the Pascal Hexagon or Pascal Windmill.  Hilton, Holton and Pedersen (1997). Mathematical Reflections. Springer. ISBN 0387947701.
Generalization to real and complex argument The binomial coefficient can be defined for any complex number z and any natural number k as follows: In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = âˆ’1. ...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
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). In mathematics, the binomial theorem is an important formula giving the expansion of powers of sums. ...
For fixed k, the expression is a polynomial in z of degree k with rational coefficients. In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ...
In mathematics, a rational number is a number which can be expressed as a ratio of two integers. ...
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 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örlundRice integral. In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...
A finite difference is a mathematical expression of the form f(x + b) âˆ’ f(x +a). ...
In calculus, Taylors theorem, named after the mathematician Brook Taylor, who stated it in 1712, gives the approximation of a differentiable function near a point by a polynomial whose coefficients depend only on the derivatives of the function at that point. ...
In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points in the Newton form. ...
In mathematics, the NÃ¶rlundRice integral relates the nth forward difference of a function to a path integral on the complex plane. ...
In particular, one can express the product of binomial coefficients as such a linear combination: where the connection coefficients are multinomial coefficients. In terms of labelled combinatorial objects, the connection coefficients represent the number of ways to assign m+nk 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+nk. (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. In mathematics, the multinomial formula is an expression of a power of a sum in terms of powers of the addends. ...
In mathematics, the Pochhammer symbol is used in the theory of special functions to represent the rising factorial or upper factorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial The empty product (x)0 is defined to be 1 in both cases. ...
Newton's binomial series Newton's binomial series, named after Sir Isaac Newton, is one of the simplest Newton series: In mathematics, the binomial series generalizes the purely algebraic binomial theorem. ...
Sir Isaac Newton in Knellers portrait of 1689. ...
In mathematics, a difference operator maps a function, f(x), to another function, f(x + a) âˆ’ f(x + b). ...
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 In mathematics, the radius of convergence of a power series where the center a and the coefficients cn are complex numbers (which may, in particular, be real numbers) is the nonnegative quantity r (which may be a real number or âˆž) such that the series converges if and diverges if In...
where the identity is applied. The formula for the binomial series was etched onto Newton's gravestone in Westminster Abbey in 1727. The Collegiate Church of St Peter, Westminster, which is almost always referred to by its original name of Westminster Abbey, is a mainly Gothic church, on the scale of a cathedral (and indeed often mistaken for one), in Westminster, London, just to the west of the Palace of Westminster. ...
Events 1727 to 1800  Lt. ...
Generalization to qseries The binomial coefficient has a qanalog generalization known as the Gaussian binomial. In mathematics, a qseries is defined as usually considered first as a formal power series; it is also an analytic function of q, in the unit disc. ...
In mathematics, the Gaussian binomial (sometimes called the Gaussian coefficient, the qbinomial coefficient, or the Gaussian polynomial) is a qanalog of the binomial coefficients. ...
See also In combinatorial mathematics, a combination is an unordered collection of unique elements. ...
A combinatorial proof is a method of proving a statement, usually a combinatorics identity, by counting some carefully chosen object in different ways to obtain different expressions in the statement (see also double counting). ...
In mathematics the nth central binomial coefficient is defined to be where is the binomial coefficient. ...
In mathematics, in the area of combinatorics, the binomial transform is a transformation of sequence by computing its forward differences. ...
In mathematics, a Newtonian series is a sum over a sequence written in the form where is the binomial coefficient and is the rising factorial. ...
This is a list of factorial and binomial topics, by Wikipedia page. ...
In combinatorial mathematics, it is clear that the only number that appears infinitely many times in Pascals triangle is 1. ...
References  This article incorporates material from the following PlanetMath articles, which are licensed under the GFDL: Binomial Coefficient, Bounds for binomial coefficients, Proof that C(n,k) is an integer, Generalized binomial coefficients.
 Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. AddisonWesley, 1997. ISBN 0201896834. Section 1.2.6: Binomial Coefficients, pp.52–74.
 David Singmaster, Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients. J. London Math. Soc. (2), volume 8 (1974), 555–560.
