This preview shows page 1-2-3-4-5-6-7-49-50-51-52-53-54-55-99-100-101-102-103-104-105 out of 105 pages.
Counting III: Pascal’s Triangle, Polynomials, and Vector ProgramsThe Geometric SeriesThe Infinite Geometric SeriesSlide 4Slide 5Geometric Series (Linear Form)Geometric Series (Quadratic Form)Suppose we multiply this out to get a single, infinite polynomial. What is an expression for Cn?cn = a0bn + a1bn-1 +… aibn-i… + an-1b1 + anb0If a = b then cn = (n+1)(an) a0bn + a1bn-1 +… aibn-i… + an-1b1 + anb0Slide 11if a b then cn = a0bn + a1bn-1 +… aibn-i… + an-1b1 + anb0Geometric Series (Quadratic Form)Slide 14Slide 15Choice tree for terms of (1+X)3The Binomial FormulaSlide 18One polynomial, two representationsPower Series RepresentationSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26A Combinatorial ProofAn attempt at a correspondenceA correspondence that works for all nSlide 30Slide 31Pascal’s Triangle: kth row are the coefficients of (1+X)kkth Row Of Pascal’s Triangle:Inductive definition of kth entry of nth row: Pascal(n,0) = Pacal (n,n) = 1; Pascal(n,k) = Pascal(n-1,k-1) + Pascal(n,k)Slide 35Pascal’s TriangleSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44How many shortest routes from A to B?ManhattanSlide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Vector ProgramsSlide 57Slide 58Slide 59Slide 60Slide 61Programs -----> PolynomialsFormal Power SeriesV! = < a0, a1, a2, . . . >Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73What does this program output?Slide 75Slide 76Al-Karaji ProgramSlide 78(1+X)/(1-X)3Slide 80Slide 81Slide 82Slide 83Slide 84Coefficient of Xk in PV = (X2+X)(1-X)-4 is the sum of the first k squares:Vector programs -> Polynomials -> Closed form expressionSlide 87Slide 88Slide 89Vector Program I/OVector Recurrence RelationsFibonacci NumbersSlide 93Slide 94Slide 95Slide 96Slide 97Slide 98Linear factors on the bottomSlide 100Slide 101Power Series Expansion of FSlide 103Slide 104ReferencesCounting III: Pascal’s Triangle, Polynomials, and Vector ProgramsGreat Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2003Lecture 11 Feb 14, 2004 Carnegie Mellon University X1 X2 + + X31 + X1 + X11 + X + X22 + X + X 33 + … + X + … + Xn-1n-1 + X + Xnn = = XXn+1 n+1 - 1- 1 XX - 1- 1 The Geometric Series1 + X1 + X11 + X + X22 + X + X 33 + … + X + … + Xnn + ….. + ….. == 11 1 - X1 - X The Infinite Geometric Series(X-1) ( 1 + X1 + X2 + X 3 + … + Xn + … )= X1 + X2 + X 3 + … + Xn + Xn+1 + …. - 1 - X1 - X2 - X 3 - … - Xn-1 – Xn - Xn+1 - …= 1 1 + X1 + X11 + X + X22 + X + X 33 + … + X + … + Xnn + ….. + ….. == 11 1 - X1 - X1 + x + ….. ____________________1-x | 1 -[1 – x] _____ x -[x – x2 ] ______ x2 -.... 1 + X1 + X11 + X + X22 + X + X 33 + … + X + … + Xnn + ….. + ….. == 11 1 - X1 - X1 + aX1 + aX11 + a + a22XX22 + a + a33X X 33 + … + a + … + annXXnn + ….. =+ ….. = 11 1 - aX1 - aX Geometric Series (Linear Form)(1 + aX1 + a2X2 + … + anXn + …..) (1 + bX1 + b2X2 + … + bnXn + …..) = 11 (1 – aX)(1-bX)(1 – aX)(1-bX) Geometric Series (Quadratic Form)(1 + aX1 + a2X2 + … + anXn + …..) (1 + bX1 + b2X2 + … + bnXn + …..) = 1 + c1X1 + .. + ck Xk + …Suppose we multiply this out to get a single, infinite polynomial.What is an expression for Cn?(1 + aX1 + a2X2 + … + anXn + …..) (1 + bX1 + b2X2 + … + bnXn + …..) = 1 + c1X1 + .. + ck Xk + …cn = aa00bbnn + a + a11bbn-1n-1 +… a +… aiibbn-in-i… + a… + an-1n-1bb11 + + aannbb00(1 + aX1 + a2X2 + … + anXn + …..) (1 + bX1 + b2X2 + … + bnXn + …..) = 1 + c1X1 + .. + ck Xk + …If a = b then cn = (n+1)(an) aa00bbnn + a + a11bbn-1n-1 +… a +… aiibbn-in-i… + a… + an-1n-1bb11 + + aannbb00(a-b) (aa00bbnn + a + a11bbn-1n-1 +… a +… aiibbn-in-i… + a… + an-1n-1bb11 + a + annbb00)= aa11bbnn +… a +… ai+1i+1bbn-in-i… + a… + annbb11 + + aan+1n+1bb00 - aa00bbn+1 n+1 – a – a11bbnn… a… ai+1i+1bbn-in-i… - a… - an-1n-1bb22 - a - annbb11= - bn+1 + an+1= an+1 – bn+1 aa00bbnn + a + a11bbn-1n-1 +… a +… aiibbn-in-i… + a… + an-1n-1bb11 + a + annbb00 = = aan+1 n+1 – – bbn+1n+1 aa - b- b(1 + aX1 + a2X2 + … + anXn + …..) (1 + bX1 + b2X2 + … + bnXn + …..) = 1 + c1X1 + .. + ck Xk + …if a b then cn = aa00bbnn + a + a11bbn-1n-1 +… a +… aiibbn-in-i… + a… + an-1n-1bb11 + + aannbb00 aan+1 n+1 – – bbn+1n+1 aa - b- b(1 + aX1 + a2X2 + … + anXn + …..) (1 + bX1 + b2X2 + … + bnXn + …..) = 11 (1 – aX)(1-bX)(1 – aX)(1-bX) Geometric Series (Quadratic Form)aan+1 n+1 – – bbn+1n+1 aa - b- b n=0..1Xn==n=0..1Xnor(n+1)a(n+1)annwhen a=bPreviously, we saw thatPolynomials Count!What is the coefcient of BA3N2 in the expansion of(B + A + N)6?The number of ways to rearrange the letters in the word BANANA.1 X 1 X1 X 1 X1 X1 X1 XChoice tree for terms of (1+X)31XXX2XX2X2X3Combine like terms to get 1 + 3X + 3X2 + X3The Binomial Formula(1 X) FHGIKJFHGIKJFHGIKJ FHGIKJ FHGIKJn k nn nXnXnkXnnX0 1 22... ...binomial expressionBinomial Coefcients0(1 )nn kknx xk The Binomial Formula0(1 )nn kknx xk One polynomial, two representations“Product form” or“Generating form”“Additive form” or“Expanded form”00(1 )nn kkkknx xknxk=�=��+ = �������= �������“Closed form” or“Generating form”“Power series” (“Taylor series”) expansionSince 0 if nk nk Power Series RepresentationBy playing these two representations againsteach other we obtain a new representation ofa previous insight:00(1 )2nn kknnknx xknk 1 2 3Let x=1. The number ofThe number ofsubsets of an subsets of an nn-element set-element set001 even odd(1 )0 ( 1)2nn kknkkn nnk knx xknkn nk k Let x= -1. Equivalently, By varying x, we can discover new identities001 even odd(1 )0 ( 1)2nn kknkkn nnk knx xknkn nk k Let x= -1. Equivalently, The number of
View Full Document