Binomial coefficient

:''See binomial (disambiguation) for a list of other topics called by that name.'' In mathematics, particularly in combinatorics, the binomial coefficient of the natural number ''n'' and the integer ''k'' is defined to be the natural number :

{n \choose k} = \frac{n!}{k!(n-k)!} \quad \mbox{if } n\geq k\geq 0 \qquad \mbox{(1)}

and :

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

(Here, for a natural number ''m'', ''m''! denotes the factorial of ''m''.) The binomial coefficient of ''n'' and ''k'' is also written as C(''n'', ''k'') or C_''n''^''k'' (C for combination) and read as "''n'' choose ''k''". According to Nicholas J. Higham, the

{n \choose k}

notation was introduced by Albert von Ettinghausen in 1826, although these numbers have been known centuries before that; see Pascal's triangle. For example, :

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

The binomial coefficients are the coefficients in the expansion of the binomial (''x'' + ''y'')^''n'' (hence the name): :

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

This is generalized by the binomial theorem, which allows the exponent ''n'' to be negative or a non-integer. == Pascal's triangle == The important recurrence relation :

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

follows directly from the definition. This recurrence relation can be used to prove by mathematical induction that C(''n'', ''k'') is a natural number for all ''n'' and ''k'', a fact that is not immediately obvious from the definition. It also gives rise to Pascal's triangle: row 0 1 row 1 1 1 row 2 1 2 1 row 3 1 3 3 1 row 4 1 4 6 4 1 row 5 1 5 10 10 5 1 row 6 1 6 15 20 15 6 1 row 7 1 7 21 35 35 21 7 1 row 8 1 8 28 56 70 56 28 8 1 Row number ''n'' contains the numbers C(''n'', ''k'') for ''k'' = 0,...,''n''. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath. This method allows the quick calculation of binomial coefficients without the need for fractions or multiplications. For instance, by looking at row number 5 of the triangle, one can quickly read off that :(''x'' + ''y'')⁵ = 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 - consequential to the recurrence relation (3) above. In the 1303 AD treatise ''Precious Mirror of the Four Elements'', Zhu Shijie mentioned the triangle as an ancient method for solving binomial coefficients indicating that the method was known to Chinese mathematicians five centuries before Blaise Pascal. == Combinatorics and statistics == Binomial coefficients are of importance in combinatorics, because they provide ready formulas for certain frequent counting problems: * Every set with ''n'' elements has

{n\choose k}

different subsets having ''k'' elements each (these are called combination), set of all ''k''-combinations of the set S often is denoted by

{S\choose k}

. * The number of strings of length ''n'' containing ''k'' ones and ''n'' − ''k'' zeros is

{n\choose k}

. * There are

{n+1\choose k}

strings consisting of ''k'' ones and ''n'' zeros such that no two ones are adjacent. * The number of sequences consisting of ''n'' natural numbers whose sum equals ''k'' is

{n+k-1\choose k}

; this is also the number of ways to choose ''k'' elements from a set of ''n'' if repetitions are allowed, denoted by

\left({n\choose k}\right)

. * The Catalan numbers have an easy formula involving binomial coefficients; they can be used to count various structures, such as tree (graph theory)s and parenthesized expressions. The binomial coefficients also occur in the formula for the binomial distribution in statistics and in the formula for a B�zier curve. == Formulas involving binomial coefficients == The following formulas are occasionally useful: :

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

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

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

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

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

From expansion (2), after derivative and substituting ''x'' = ''y'' = 1. :

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

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

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

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

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

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

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

This can be proven by induction on ''n'' using (3). == Divisors of binomial coefficients == The prime number 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''/greatest common divisor(''n'',''k''). == Generalization to complex arguments == The binomial coefficient

{z\choose k}

can be defined for any complex number ''z'' and any natural number ''k'' as follows: :

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

This generalization is known as the generalized binomial coefficient and is used in the formulation of the binomial theorem and satisfies properties (3) and (7). For fixed ''k'', the expression

{z\choose k}

is a polynomial in ''z'' of degree ''k'' with rational number coefficients. Every polynomial ''p''(''z'') of degree ''d'' can be written in the form :

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

with suitable constants ''a''_''k''. This is important in the theory of difference equations and can be seen as a discrete analog of Taylor's theorem. == Generalization to ''q''-series == The binomial coefficient has a q-analog generalization known as the Gaussian binomial. == Bounds for binomial coefficients == The following bounds for C(''n'', ''k'') hold: *

{n \choose k} \le \frac{n^k}{k!}

{n \choose k} \le \left(\frac{n\cdot e}{k}\right)^k

{n\choose k}\ge \left(\frac{n}{k}\right)^k

==See also== * List of factorial and binomial topics == References == Combinatorics Number sequences

Binomial coefficient

Does anyone want to add the general binomial theorem (for all n). Also I have some weird alternative formulas for C(n,r) with n a non-negative integer, but I'd have to set up the pictures on a stable server or something. ==Definition of binomial coefficients for n < 0 == To User:Maxal and whoever else is willing to comment: I would say that the recently inserted equation :

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

is reduntant, because of :

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

which shows up below. : The latter formula makes sense only for integer

n \geq 0

. While the former one is true for any n. --User:Maxal 22:47, 13 Apr 2005 (UTC) :: The point is, ''everywhere'' in this article it is assumed that n ≥ 0. Just read through it. The Pascal triangle for example, does not hold for n < 0. I find your addition not in the right place. I think it rather belongs in a generalization section at the end of the article. What do you think? User:Oleg Alexandrov 23:03, 13 Apr 2005 (UTC) :Disagree. It's the only complete definition for now. And it should come first. I think Pascal triangle and other middle-school-level stuff should form a separate section. --User:Maxal 23:07, 13 Apr 2005 (UTC) :: Please notice that the generalization to n < 0, actually, for any n complex, is at already in the article, see several sections below in there. User:Oleg Alexandrov 23:10, 13 Apr 2005 (UTC) : First of all, there is a bad mixture of notations.

C_n^k

or C(n,k) is the number of combinations and it's defined only for non-negative integer n,k (Pascal's triangle is actually defined for C(n,k)). The binomial coefficient

{n\choose k}

is a generalization of

C_n^k

which is defined for integer k and arbitrary n. As of generalization of

{n\choose k}

to complex n, it's ok except for notation. C(n,k) is inappropriate. :Second, the article makes accent on combinatorics where complex n have no (or very limited) application. Hence, it's ok to keep the generalization to complex n at the end. --User:Maxal 23:26, 13 Apr 2005 (UTC) :: So, what are the applications of negative n to combinatorics? User:Oleg Alexandrov 23:28, 13 Apr 2005 (UTC) : Say, they often appear in expansions of generating functions. And there many self-reverse relations including them. --User:Maxal 23:37, 13 Apr 2005 (UTC) So, if you want to really make some changes to this article, you should read it all, then see how to make things look nice overall. What do you think? : I've read it all, and there was no correct definition for binomial coefficients for n<0. Moreover, in the discussion you can see a request for the definition "general" binomial coefficient. I've provided a general definition of binomial coefficients (most popular in combinatorics). From this very same expansion binomial coefficients can be also defined for non-integer n but that's mainly related to analysis. --User:Maxal 22:47, 13 Apr 2005 (UTC) Also, please see the sentence: :This is generalized by the binomial theorem, which allows the exponent n to be negative or a non-integer. in the article. Did you notice it? User:Oleg Alexandrov 22:42, 13 Apr 2005 (UTC) : Yes but that article should not prevent for providing correct and complete definition of the binomial coefficients. --User:Maxal 22:47, 13 Apr 2005 (UTC) == Rewriting the first section in this article? == I am a bit unahappy about the first section in this article. There, one starts with the expansion of :

(1+x)^n

only to switch later in the same section to :

(x+y)^n.

One starts with an arbitrary integer ''n'', only to continue with natural ''n'' in the next sections, and come back with arbitrary complex ''n'' a while below. I would suggest to make the first paragraph talk only about the case of the natural number ''n''. That is, start with the most elementary case. This will be followed naturally by the Pascal triangle, in the next section. One can expand and generalize on this later. This is consistent with Wikipedia:How to write a Wikipedia article on Mathematics. Any comments? User:Oleg Alexandrov 23:50, 22 Apr 2005 (UTC) :There was way too many changes to revert them at once. Reverting back. If you don't like the way it is currently presented, add/change just the first section instead of reverting the whole thing. --User:Maxal 23:56, 30 Apr 2005 (UTC) :: As you noticed, I reverted not right away, but waited a while, then wrote the above, then waited more. I reverted all of it, because I did not want to do lots of work then you come back and revert again. :: Now, I still believe the first section is better off the way it was before your changes. You made things more general at the expense of damaging the logical flow of the article. :: Once we agree on that, I will put back the first section the way it was before you changed, and keep your other modifications. User:Oleg Alexandrov 00:06, 1 May 2005 (UTC) : There should be a clear distinction between C(n,k) and

{n\choose k}

. What is currently defined at the top is actually C(n,k), not

{n\choose k}

. So in the first two sections C(n,k) should be used while

{n\choose k}

should appear later with complete definition as a generalization of C(n,k). --User:Maxal 11:46, 3 May 2005 (UTC) :: I have no problems with that. However, one should mention on top that

{n\choose k}

is an alternative notation. User:Oleg Alexandrov 15:46, 3 May 2005 (UTC)

See other meanings of words starting from letter:

B

BA | BC | BD | BE | BF | BG | BH | BI | BJ | BK | BL | BM | BN | BO | BP | BR | BS | BT | BU | BW | BX | BY | BZ |

Words begining with Binomial_coefficient:

Binomial_coefficient
Binomial_coefficient
Binomial_coefficients