Binomial coefficient

In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial power (1+x)ⁿ. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and 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 It is the simplest kind of polynomial except for a monomial Colloquially given, say there are n pizza toppings to select from, if one wishes to bake a pizza with exactly k different toppings, then the binomial coefficient expresses how many different types of such k-topping pizzas are possible.

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}\ 0\leq k\leq n \qquad (1)$

and

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

where n! denotes the factorial of n. Definition The factorial function is formally defined by n!=\prod_{k=1}^n k

According to Nicholas J. Higham, the ${\tbinom n k}$ notation was introduced by Albert von Ettinghausen in 1826, although these numbers were already known centuries before that (see Pascal's triangle). Nicholas John Higham FRS (born Salford 25 December 1961) is a numerical analyst and Richardson Professor of Applied Mathematics at For the game see 1826 (board game. Year 1826 ( MDCCCXXVI) was a Common year starting on Sunday (link will display \begin{matrix}&&&&&1\\&&&&1&&1\\&&&1&&2&&1\\&&1&&3&&3&&1\\&1&&4&&6&&4&&1\end{matrix Alternative notations include C(n, k), _nC_k or $C^{k}_{n}$ , in all of which the C stands for combination or choose. In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set 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".

The binomial coefficients are the coefficients in the expansion of the binomial (1 + x)ⁿ (hence the name):

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

This is generalized by the binomial theorem, which allows the exponent n to be negative or a non-integer. In Mathematics, a coefficient is a Constant multiplicative factor of a certain object In Mathematics, the binomial theorem is an important Formula giving the expansion of powers of Sums Its simplest version says See the article on combination. In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set

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. The term combinatorial proof is often used in either of two senses A proof by double counting. 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 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.

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 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 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. In Mathematics, an indicator function or a characteristic function is a function defined on a set X that indicates membership of ^[1]

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{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35.$

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, (1+x)¹ is 1+x. For exponent 2, (1+x)² 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 x², 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)³ reduces to (1+x)²·(1+x), where we already know that (1+x)²= 1+2x+x², giving an initial expansion of (1+x)·(1+2x+x²). Again the extremes, 1 and x³ arise in a unique way. However, the x term is either 1·2x or x·1, for a coefficient of 3; likewise x² arises in two ways, summing the coefficients 2 and 1 to give 3.

This suggests an induction. Mathematical induction is a method of Mathematical proof typically used to establish that a given statement is true of all Natural numbers It is done by proving that Thus for exponent n, each term of (1+x)ⁿ 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ⁿ. So ${\tbinom n 0}=1$ and ${\tbinom n n}=1.$ If k is neither 0 nor n, then the term x^k arises in (1+x)ⁿ=(1+x)·(1+x)ⁿ⁻¹ in two ways, from 1·x^k and from x·x^k−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 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. In several fields of Mathematics the term permutation is used with different but closely related meanings 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² 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

${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))!} \\ &{} = \left(\frac{n!(k+1)}{k!(n-k)!(k+1)} + \frac{n!(n-k)}{(k+1)!(n-(k+1))!(n-k)}\right)\\ &{} = \left(\frac{n!(k+1 + n-k)}{(k+1)!(n-k)!}\right) \\ &{} = \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 C(n, k) is a natural number for all n and k, a fact that is not immediately obvious from the definition. In Mathematics, Pascal's rule is a combinatorial identity about Binomial coefficients It states that for any Natural number n "Difference equation" redirects here It should not be confused with a Differential equation. Mathematical induction is a method of Mathematical proof typically used to establish that a given statement is true of all Natural numbers It is done by proving that

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 C(n, k) for k = 0,…,n. \begin{matrix}&&&&&1\\&&&&1&&1\\&&&1&&2&&1\\&&1&&3&&3&&1\\&1&&4&&6&&4&&1\end{matrix 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)⁵ = 1 x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1 y⁵.

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 ( fl 13th century) Courtesy name Hanqing (汉卿 Pseudonym Songting (松庭 was one of the greatest Chinese Mathematics in China emerged independently by the 11th century BC Blaise Pascal (blɛz paskal (June 19 1623 &ndash 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:

Every set with n elements has $C(n, k)$ different subsets having k elements each (these are called k-combinations). Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set
The number of strings of length n containing k ones and n − k zeros is $C(n, k). In Computer programming and some branches of Mathematics, a string is an ordered Sequence of Symbols.$
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. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an
The Catalan numbers have an easy formula involving binomial coefficients; they can be used to count various structures, such as trees and parenthesized expressions. In combinatorial mathematics, the Catalan numbers form a Sequence of Natural numbers that occur in various Counting problems often involving In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path.

The binomial coefficients also occur in the formula for the binomial distribution in statistics and in the formula for a Bézier curve. WikipediaWikiProject Probability#Standards for a discussion of standards used for probability distribution articles such as this one Statistics is a mathematical science pertaining to the collection analysis interpretation or explanation and presentation of Data. In the mathematical field of Numerical analysis, a Bézier curve is a Parametric curve important in Computer graphics and related fields

Formulas involving binomial coefficients

One has that

${n \choose k}= {n \choose n-k},\qquad\qquad(4)$

This follows immediately from the definition or can be seen from expansion (2) by using (x + y)ⁿ = (y + x)ⁿ, and is reflected in the numerical "symmetry" of Pascal's triangle. \begin{matrix}&&&&&1\\&&&&1&&1\\&&&1&&2&&1\\&&1&&3&&3&&1\\&1&&4&&6&&4&&1\end{matrix

Another formula is

$\sum_{k=0}^{n} {n \choose k} = 2^n, \qquad\qquad(5)$

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

The formula

$\sum_{k=1}^{n} {k} {n \choose k} = {n} 2^{n-1} \qquad(6)$

follows from expansion (2), after differentiating with respect to either x or y and then substituting x = y = 1. In Calculus, a branch of mathematics the derivative is a measurement of how a function changes when the values of its inputs change

Vandermonde's identity

$\sum_{j} {m\choose j} {{n-m} \choose {k-j}} = {n \choose k} \qquad (7a)$

is found by expanding (1+x)^m (1+x)^n-m = (1+x)ⁿ with (2). In combinatorial Mathematics, Vandermonde's identity, named after Alexandre-Théophile Vandermonde, states that the equality {m+n 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, complex-valued $m$ and $n$ , the Chu-Vandermonde identity. In combinatorial Mathematics, Vandermonde's identity, named after Alexandre-Théophile Vandermonde, states that the equality {m+n

A related formula is

$\sum_{m} {m\choose j} {n-m\choose k-j}= {n+1\choose 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} {m \choose j}^2 = {{2m} \choose m}. \qquad (8)$

Denote by F(n + 1) the Fibonacci numbers. In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci We obtain a formula about the diagonals of Pascal's triangle

$\sum_{k=0}^{n} {{n-k} \choose k} = \mathrm{F}(n+1). \qquad (9)$

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 It is done by proving that

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

$\sum_{j=k}^{n} {j \choose k} = {{n+1} \choose {k+1}}. \qquad (10)$

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

$\sum_{j=0}^{k} (-1)^j{n \choose j} = (-1)^k{{n-1} \choose k} \qquad(11)$

as well as

$\sum_{j=0}^{n} (-1)^j{n \choose j} = 0 \qquad(12)$

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

$\sum_{j=0}^{n} (-1)^j{n \choose j}j^a = 0.$

which can be shown by differentiating (2) a times and setting x=-1 and y=1.

Combinatorial identities involving binomial coefficients

We present some identities that have combinatorial proofs. We have, for example,

$\sum_{k=q}^{n} {n \choose k}{k \choose q} = 2^{n-q} {n \choose q}.\qquad(13)$

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 $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

$\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}.$

Suppose you have $2 n$ empty squares arranged in a row and you want to mark (select) n of them. There are $C (2 n, 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}^{n} {n \choose k} {n \choose n-k} = {{2n} \choose n}.$

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. The fundamental theorem of combinatorial enumeration is a theorem in combinatorics that solves the enumeration problem of labelled and unlabelled combinatorial classes 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. In Mathematics a generating function is a Formal power series whose coefficients encode information about a Sequence a n 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$

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

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 binomial-style 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 $\tbinom n k$ can be interpreted as follows: if p is a prime number and p^r 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/p^j is bigger than the fractional part of n/p^j. In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 In Mathematics and Computer science, the floor and ceiling functions map Real numbers to nearby Integers The In particular, $\tbinom n k$ is always divisible by n/gcd(n,k). In Mathematics, the greatest common divisor (gcd, sometimes known as the greatest common factor (gcf or highest common factor (hcf, of two non-zero

A somewhat surprising result by David Singmaster (1974) is that any integer divides almost all binomial coefficients. David Breyer Singmaster (born 1939 USA) is a retired Professor of Mathematics at London South Bank University, England, UK. See also Generic property In Mathematics, the phrase almost all has a number of specialised uses 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_{N\to\infty} \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{n\cdot e}{k}\right)^k$

Generalizations

Generalization to multinomials

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

${n\choose 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)ⁿ, the multinomial coefficients represent the coefficients of the polynomial

(x₁ + x₂ + . . . + x_r)ⁿ.

See multinomial theorem. In Mathematics, the multinomial theorem says how to write a power of a sum in terms of powers of the terms in that sum The case k = 2 gives binomial coefficients:

${n\choose k_1,k_2}={n\choose k_1, n-k_1}={n\choose k_1}= {n\choose k_2}$

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:

${n\choose k_1,k_2,\ldots,k_r} ={n-1\choose k_1-1,k_2,\ldots,k_r}+{n-1\choose k_1,k_2-1,\ldots,k_r}+\ldots+{n-1\choose k_1,k_2,\ldots,k_r-1}$

and symmetry:

${n\choose k_1,k_2,\ldots,k_r} ={n\choose k_{\sigma_1},k_{\sigma_2},\ldots,k_{\sigma_r}}$

where $(σ 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.

Hilton, Holton and Pedersen (1997). Mathematical Reflections. Springer. ISBN 0-387-94770-1.

Generalization to real and complex argument

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

${z\choose k} = \prod_{n=1}^{k}{z-k+n\over 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). Complex plane In Mathematics, the complex numbers are an extension of the Real numbers obtained by adjoining an Imaginary unit, denoted In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an In Mathematics, the binomial theorem is an important Formula giving the expansion of powers of Sums Its simplest version says

For fixed k, the expression $f(z)={z\choose k}$ is a polynomial in z of degree k with rational coefficients. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations In Mathematics, a rational number is a number which can be expressed as a Ratio of two Integers Non-integer rational numbers (commonly called fractions

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 {z\choose 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. "Difference equation" redirects here It should not be confused with a Differential equation. A finite difference is a mathematical expression of the form f ( x + b) &minus f ( x + a) In Calculus, Taylor's theorem gives a sequence of approximations of a Differentiable function around a given point by Polynomials (the Taylor It is closely related to Newton's polynomial. In the Mathematical field of Numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation Polynomial Alternating sums of this form may be expressed as the Nörlund-Rice integral. In Mathematics, the Nörlund-Rice integral, sometimes called Rice's method, relates the n th Forward difference of a function to a Line integral

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

${x\choose m} {x\choose n} = \sum_{k=0}^m {m+n-k\choose k,m-k,n-k} {x\choose m+n-k}$

where the connection coefficients are multinomial coefficients. In Mathematics, the multinomial theorem says how to write a power of a sum in terms of powers of the terms in that sum 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. In Mathematics, the Pochhammer symbol (x_{n}\ introduced by Leo August Pochhammer, represents either the rising or the falling

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}{\alpha\choose n}z^n = 1+{\alpha\choose1}z+{\alpha\choose 2}z^2+\cdots.$

The identity can be obtained by showing that both sides satisfy the differential equation (1+z) f'(z) = α f(z). In Mathematics, the binomial series generalizes the purely algebraic formula of the Binomial theorem to complex values of α Sir Isaac Newton, FRS (ˈnjuːtən 4 January 1643 31 March 1727) Biography Early years See also Isaac Newton's early life and achievements In Mathematics, a difference operator maps a function, f ( x) to another function f ( x + a) &minus f ( x

The radius of convergence of this series is 1. In Mathematics, the radius of convergence of a Power series is a non-negative quantity either a real number or \scriptstyle \infty that represents a 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. The Collegiate Church of St Peter at Westminster, which is almost always referred to by its original name of Westminster Abbey, is a large mainly Gothic church Year 1727 ( MDCCXXVII) was a Common year starting on Wednesday (link will display the full calendar of the Gregorian calendar (or a Common

Generalization to q-series

The binomial coefficient has a q-analog generalization known as the Gaussian binomial. In Mathematics, in the area of Combinatorics and Special functions a q -analog is roughly speaking a theorem or identity for a ''q''-series In Mathematics, the Gaussian binomials (sometimes called the Gaussian coefficients, or the q -binomial coefficients) are the Q-analogs

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 $α$ . This article describes cardinal numbers in mathematics For cardinals in linguistics see Names of numbers in English. In Mathematics, the cardinality of a set is a measure of the "number of elements of the set" 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 \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 $α$ . In Mathematics, the axiom of choice, or AC, is an Axiom of Set theory.

Binomial coefficient in programming languages

The notation ${n \choose k}$ is convenient in handwriting but inconvenient for typewriters and computer terminals. A typewriter is a mechanical or Electromechanical device with a set of "keys" that when pressed cause characters to be printed on a medium A computer terminal is an electronic or electromechanical hardware device that is used for entering data into and displaying data from a Computer or a Computing 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 . A programming language is an Artificial language that can be used to write programs which control the behavior of a machine particularly a Computer. In Computer science, a subroutine ( function, method, procedure, or subprogram) is a portion of code within a larger Not to be confused with the J++ or J# programming languages The J programming language, developed in the early 1990s by

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. tags please moot on the talk page first! --> In Computing, C is a general-purpose cross-platform block structured 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
}

Using Pascal's rule ${n\choose k} = {n-1\choose k-1} + {n-1\choose k}$ , the algorithm for the binomial coefficient may be written in recursive form:^[2]

    function choose(n: integer, k:integer): integer
        if k = 0 or k = n then
            choose = 1
        else
            choose = choose(n-1, k-1) + choose(n-1, k)
        end if
    end function

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. In Mathematics, Pascal's rule is a combinatorial identity about Binomial coefficients It states that for any Natural number n Recursion in computer science is a way of thinking about and solving problems In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set In Mathematics the n th central binomial coefficient is defined in terms of the Binomial coefficient by {2n \choose n} = \frac{(2n!}{(n!^2} In Combinatorial Mathematics the binomial transform is a Sequence transformation (ie a transform of a Sequence) that computes its Forward In Mathematics, a Newtonian series, named after Isaac Newton, is a sum over a Sequence a_n written in the form f(s = This is a list of factorial and binomial topics in Mathematics, by Wikipedia page In Mathematics, the binomial theorem is an important Formula giving the expansion of powers of Sums Its simplest version says PlanetMath is a free, collaborative online Mathematics Encyclopedia.
Knuth, Donald E. (1997). Donald Ervin Knuth (kəˈnuːθ (born 10 January 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition, Addison-Wesley, 52–74. ISBN 0-201-89683-4.
Graham, Ronald L.; Knuth, Donald E . & Patashnik, Oren (1989), Concrete Mathematics, Addison Wesley, pp. Ronald Lewis Graham (born October 31, 1935) is a Mathematician credited by the American Mathematical Society with being "one of the principal Donald Ervin Knuth (kəˈnuːθ (born 10 January 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer Oren Patashnik (born 1954 is a computer scientist He is notable for co-creating BibTeX, and co-writing Concrete Mathematics A Foundation for Computer Science 153–242, ISBN 0-201-14236-8
Singmaster, David (1974). David Breyer Singmaster (born 1939 USA) is a retired Professor of Mathematics at London South Bank University, England, UK. "Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients". J. London Math. Soc. (2) 8: 555–560.
Bryant, Victor (1993). Aspects of combinatorics. Cambridge University Press.

Dictionary

binomial coefficient

-noun

(combinatorics) A coefficient of any of the terms in the expansion of the binomial (x+y)ⁿ.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

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

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

Contents