Binomial CoefficientsSlide 2Review: corollary 1 from section 4.3Review: combinatorial proofPolynomial expansionSlide 6Slide 7Polynomial expansion: The binomial theoremExamplesRosen, section 4.4, question 4Pascal’s trianglePascal’s IdentityCombinatorial proof of Pascal’s identityRosen, section 4.4, question 19: algebraic proof of Pascal’s identityApril Fools Day JokesSlide 16Proof practice: corollary 1Slide 18Slide 20Proof practice: corollary 2Proof practice: corollary 3Vandermonde’s identityCombinatorial proof of Vandermonde’s identityReview of Rosen, section 4.3, question 11 (a)Yet another combinatorial proofSlide 27Rosen, section 4.4, question 24Rosen, section 4.4, question 38Slide 30Slide 31Quick surveySlide 33Slide 34Becoming an IEEE authorSlide 3611Binomial CoefficientsBinomial CoefficientsCS/APMA 202CS/APMA 202Rosen section 4.4Rosen section 4.4Aaron BloomfieldAaron Bloomfield22 Binomial CoefficientsBinomial CoefficientsIt allows us to do a quick expansion of It allows us to do a quick expansion of ((xx++yy))nnWhy it’s really important:Why it’s really important:It provides a good context to present It provides a good context to present proofsproofsEspecially combinatorial proofsEspecially combinatorial proofs33 Let Let nn and and rr be non-negative integers with be non-negative integers with rr ≤ ≤ nn. Then . Then CC((nn,,rr) = ) = CC((nn,,n-rn-r))Or, Or, Proof (from last slide set):Proof (from last slide set): ! )()!(!),(rnnrnnrnnC)!(!!rnrn)!(!!),(rnrnrnCReview: corollary 1 Review: corollary 1 from section 4.3from section 4.3rnnrn44 Review: combinatorial proofReview: combinatorial proofA A combinatorial proofcombinatorial proof is a proof that uses is a proof that uses counting arguments to prove a theorem, counting arguments to prove a theorem, rather than some other method such as rather than some other method such as algebraic techniquesalgebraic techniquesEssentially, show that both sides of the Essentially, show that both sides of the proof manage to count the same objectsproof manage to count the same objectsUsually in the form of an English explanation Usually in the form of an English explanation with supporting formulaewith supporting formulae55 Polynomial expansionPolynomial expansionConsider (Consider (xx++yy))33::Rephrase it as:Rephrase it as:When choosing When choosing xx twice and twice and yy once, there are once, there are C(3,2) = C(3,1) = 3 ways to choose where the C(3,2) = C(3,1) = 3 ways to choose where the xx comes fromcomes fromWhen choosing When choosing xx once and once and yy twice, there are twice, there are C(3,2) = C(3,1) = 3 ways to choose where the C(3,2) = C(3,1) = 3 ways to choose where the yy comes fromcomes from3223333)( yxyyxxyx    32222223))()(( yxyxyxyyxyxyxxyxyxyx 66 Polynomial expansionPolynomial expansionConsiderConsiderTo obtain the To obtain the xx55 term termEach time you multiple by (Each time you multiple by (xx++yy), you select the ), you select the xxThus, of the 5 choices, you choose Thus, of the 5 choices, you choose xx 5 times 5 timesC(5,5) = 1C(5,5) = 1Alternatively, you choose Alternatively, you choose yy 0 times 0 timesC(5,0) = 1C(5,0) = 1To obtain the To obtain the xx44yy term termFour of the times you multiply by (Four of the times you multiply by (xx++yy), you select the ), you select the xxThe other time you select the The other time you select the yyThus, of the 5 choices, you choose Thus, of the 5 choices, you choose xx 4 times 4 timesC(5,4) = 5C(5,4) = 5Alternatively, you choose Alternatively, you choose yy 1 time 1 timeC(5,1) = 5C(5,1) = 5To obtain the To obtain the xx33yy22 term termC(5,3) = C(5,2) = 10C(5,3) = C(5,2) = 10Etc…Etc…543223455510105)( yxyyxyxyxxyx 77 Polynomial expansionPolynomial expansionFor (For (xx++yy))55543223455051525354555)( yxyyxyxyxxyx543223455510105)( yxyyxyxyxxyx 88 Polynomial expansion: Polynomial expansion: The binomial theoremThe binomial theoremFor (For (xx++yy))nnThe book calls this Theorem 1The book calls this Theorem 1nnnnnyxnyxnyxnnyxnnyx011110011)(njjjnyxjn0nnnnyxnnyxnnyxnyxn01111011099 ExamplesExamplesWhat is the coefficient of What is the coefficient of xx1212yy1313 in ( in (xx++yy))2525??What is the coefficient of What is the coefficient of xx1212yy1313 in (2 in (2xx-3-3yy))2525??Rephrase it as (2x+(-3y))Rephrase it as (2x+(-3y))2525The coefficient occurs when The coefficient occurs when jj=13:=13:300,200,5!12!13!2512251325 2502525)3()2(25)3(2jjjyxjyx00,545,702,433,959,763)3(2!12!13!25)3(21325131213121010 Rosen, section 4.4, question 4Rosen, section 4.4, question 4Find the coefficient of Find the coefficient of xx55yy88 in ( in (xx++yy))1313Answer: Answer: 12878135131111 Pascal’s trianglePascal’s triangle012345678n =1212 Pascal’s IdentityPascal’s IdentityBy Pascal’s identity: or 21=15+6By Pascal’s identity: or 21=15+6Let Let nn and and kk be positive integers with be positive integers with nn ≥≥ kk. . ThenThenor C(or C(nn+1,+1,kk) = C() = C(nn,,kk-1) + C(-1) + C(nn,,kk))The book calls this Theorem 2The book calls this Theorem 2We will prove this via two ways:We will prove this via two ways:Combinatorial proofCombinatorial proofUsing the formula forUsing the formula forknknkn11564657kn1313 Combinatorial proof of