calcul coefficient binomial

December 13 2010 The binomial coe cient choose k\" written n (n)k n! = = ; k k! k! (n k)! counts the number of k-element subsets of an n-element set The name arises from the binomial theorem which says that 1 X (x + y)n = k=0 n xkyn k: k For integer n we can limit ourselves to letting k range from 0 to n

Basic Facts about Binomial Coefficients n ! There are many equivalent ways of defining (Read this as “n choose r ”) Here we r assume 0 ≤ r ≤ n 1 Here are four of doing this The Factorial Formula: n ! n! = r r!(n − r)! This is enough to give the basic identities n ! n ! n ! = = 1; = 0 n r 2 Recursion on r (Pascal’s triangle): ! − r 0 !

bounds on the binomial coe cients that are more convenient to work with11 We begin with the simplest upper bound which can often be useful when the bino-mial is a lower-order term 80 k n : n k 2n (1) To see why this is true recall that n k counts the number of subsets of [n] of size k while 2n counts all subsets of [n]

Binomial Theorem At this point we all know beforehand what we obtain when we unfold (x + y)2 and (x + y)3 We can actually use binomial coe the formulas for the square and cube of a binomial expression cients to generalize Theorem 1 For any n 2 N0 the following identity holds: (0 1) n X (x + y)n = k=0 k n xkyn k: Proof

x(1+x)3=x+3x2+3x3+x4 Adding (1+x)4=1+4x+4x2+4x3+x4 Thus for (1 +x)4 the coe cient of any power ofxis seen to the sum of the coe cients of that power and the preceding power in the expansion of (1 +x)3 In other words the coe cients are obtained by recursion generating Pascal’s triangle

In mathematics the binomial theorem is an important formula giving the expansion of powers of sums Its simplest version reads (x+y)n = Xn k=0 n k xkyn−k whenever n is any non-negative integer the numbers n k = n! k!(n−k)! are the binomial coefficients and n! denotes the factorial of n