Binomial coefficient

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written ( n k ) . {displaystyle { binom {n}{k}}.} It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n, and it is given by the formula ( x + y ) n = ∑ k = 0 n ( n k ) x n − k y k {displaystyle (x+y)^{n}=sum _{k=0}^{n}{inom {n}{k}}x^{n-k}y^{k}}     (∗) ( n k ) = ( n n − k ) for    0 ≤ k ≤ n , {displaystyle {inom {n}{k}}={inom {n}{n-k}}quad { ext{for }} 0leq kleq n,}     (1) ( 1 + X ) α = ∑ k = 0 ∞ ( α k ) X k . {displaystyle (1+X)^{alpha }=sum _{k=0}^{infty }{alpha choose k}X^{k}.}     (2) ( n k ) + ( n k + 1 ) = ( n + 1 k + 1 ) , {displaystyle {n choose k}+{n choose k+1}={n+1 choose k+1},}     (3) a k = ∑ i = 0 k ( − 1 ) k − i ( k i ) p ( i ) . {displaystyle a_{k}=sum _{i=0}^{k}(-1)^{k-i}{inom {k}{i}}p(i).}     (4) ( n k ) = n k ( n − 1 k − 1 ) {displaystyle {inom {n}{k}}={frac {n}{k}}{inom {n-1}{k-1}}}     (5) ∑ k = 0 n ( n k ) = 2 n {displaystyle sum _{k=0}^{n}{inom {n}{k}}=2^{n}}     (∗∗) ∑ k = 0 n k ( n k ) = n 2 n − 1 {displaystyle sum _{k=0}^{n}k{inom {n}{k}}=n2^{n-1}}     (6) ∑ j = 0 k ( m j ) ( n − m k − j ) = ( n k ) {displaystyle sum _{j=0}^{k}{inom {m}{j}}{inom {n-m}{k-j}}={inom {n}{k}}}     (7) ∑ j = 0 m ( m j ) 2 = ( 2 m m ) , {displaystyle sum _{j=0}^{m}{inom {m}{j}}^{2}={inom {2m}{m}},}     (8) ∑ m = 0 n ( m j ) ( n − m k − j ) = ( n + 1 k + 1 ) . {displaystyle sum _{m=0}^{n}{inom {m}{j}}{inom {n-m}{k-j}}={inom {n+1}{k+1}}.}     (9) ∑ j = 0 n ( − 1 ) j ( n j ) P ( n − j ) = n ! a n {displaystyle sum _{j=0}^{n}(-1)^{j}{inom {n}{j}}P(n-j)=n!a_{n}}     (10) In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written ( n k ) . {displaystyle { binom {n}{k}}.} It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n, and it is given by the formula For example, the fourth power of 1 + x is and the binomial coefficient ( 4 2 ) = 4 ! 2 ! 2 ! = 6 {displaystyle { binom {4}{2}}={ frac {4!}{2!2!}}=6} is the coefficient of the x2 term. Arranging the numbers ( n 0 ) , ( n 1 ) , … , ( n n ) {displaystyle { binom {n}{0}},{ binom {n}{1}},ldots ,{ binom {n}{n}}} in successive rows for n = 0 , 1 , 2 , … {displaystyle n=0,1,2,ldots } gives a triangular array called Pascal's triangle, satisfying the recurrence relation The binomial coefficients occur in many areas of mathematics, and especially in combinatorics. The symbol ( n k ) {displaystyle { binom {n}{k}}} is usually read as 'n choose k' because there are ( n k ) {displaystyle { binom {n}{k}}} ways to choose an (unordered) subset of k elements from a fixed set of n elements. For example, there are ( 4 2 ) = 6 {displaystyle { binom {4}{2}}=6} ways to choose 2 elements from { 1 , 2 , 3 , 4 } , {displaystyle {1,2,3,4},} namely { 1 , 2 } ,  { 1 , 3 } ,  { 1 , 4 } ,  { 2 , 3 } ,  { 2 , 4 } , {displaystyle {1,2}{ ext{, }}{1,3}{ ext{, }}{1,4}{ ext{, }}{2,3}{ ext{, }}{2,4}{ ext{,}}} and { 3 , 4 } . {displaystyle {3,4}.} The binomial coefficients can be generalized to ( z k ) {displaystyle { binom {z}{k}}} for any complex number z and integer k ≥ 0, and many of their properties continue to hold in this more general form. Andreas von Ettingshausen introduced the notation ( n k ) {displaystyle { binom {n}{k}}} in 1826, although the numbers were known centuries earlier (see Pascal's triangle). The earliest known detailed discussion of binomial coefficients is in a tenth-century commentary, by Halayudha, on an ancient Sanskrit text, Pingala's Chandaḥśāstra. In about 1150, the Indian mathematician Bhaskaracharya gave an exposition of binomial coefficients in his book Līlāvatī. Alternative notations include C(n, k), nCk, nCk, Ckn, Cnk, and Cn,k in all of which the C stands for combinations or choices. Many calculators use variants of the C notation because they can represent it on a single-line display. In this form the binomial coefficients are easily compared to k-permutations of n, written as P(n, k), etc. For natural numbers (taken to include 0) n and k, the binomial coefficient ( n k ) {displaystyle { binom {n}{k}}} can be defined as the coefficient of the monomial Xk in the expansion of (1 + X)n. The same coefficient also occurs (if k ≤ n) in the binomial formula