Slide 1Slide 2RecapSlide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Coefficient of Xk in (X2+X)/(1-X)4 is the sum of the first k squares:Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 7415-251Great Theoretical Ideas in Computer ScienceX1 X2 + + X3Lecture 8 (September 17, 2009)Counting III:Generating FunctionsRecapThe Binomial Formula(1+X)0 =(1+X)1 =(1+X)2 =(1+X)3 =(1+X)4 =11 + 1X1 + 2X + 1X21 + 3X + 3X2 + 1X31 + 4X + 6X2 + 4X3 + 1X4Pascal’s Triangle: kth row are coefficients of (1+X)kInductive definition of kth entry of nth row:Pascal(n,0) = Pascal (n,n) = 1; Pascal(n,k) = Pascal(n-1,k-1) + Pascal(n-1,k)Pascal’s Triangle“It is extraordinaryhow fertile inproperties thetriangle is.Everyone cantry hishand”11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 111 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Summing on kth Avenuei = knikn+1k+1=11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Fibonacci Numbers= 2= 3= 5= 8= 1311 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Sums of Squares2 2 22 2 2 22nnnkk = 0n2=All these properties can be proved inductively and algebraically. We gave combinatorial proofs using the Manhattan block walking representation of binomial coefficientsHow many shortest routes from A to B?BA105Manhattanjth street kth avenue1024301234There are shortest routes from (0,0) to (j,k)j+kkManhattanLevel n kth avenue1024301234There are shortest routes from (0,0) to (n-k,k)nkManhattanLevel n kth avenue1024301234There areshortest routes from (0,0) tonklevel n and kth avenueLevel n kth avenue1024301234nkn-1k-1n-1k=+Level n kth avenue1024301234nk2How many ways to get to via ?Level n kth avenue10243012342nnnkk = 0n2=Level n kth avenue1024301234How many ways to get to via ?n+1k+1 i kLevel n kth avenue1024301234n+1k+1iki = kn=n+1k+11 + X1 + X2 + X3 + … + Xn-2 + Xn-1 = X - 1 Xn – 1Recall the Geometric Series1 - X 1 - Xn=1 + X1 + X2 + X3 + … + Xn + … = 1 - X 1the Infinite Geometric SeriesAlso makes sense if we viewthe infinite sum on the left as a formal power seriesHolds when |X| < 11 + X1 + X2 + X3 + … + Xn + …1 - X 1- X1 - X2 - X3 - … - Xn - Xn+1 - …(1- X) P(X) = P(X) = -X * P(X) = P(X) =1Formal Power Seriesi = 0aiXiP(X) =There are no worries about convergence issues.This is a purely syntactic object.Formal Power Seriesi = 0aiXiP(X) =If you want, think of as the infinite vectorV = < a0, a1, a2, ..., an, … >But, as you will see, thinking of as a “polynomial” is very natural.OperationsA(X) = a0 + a1 X + a2 X2 + … B(X) = b0 + b1 X + b2 X2 + … adding them together(A+B)(X) = (a0+b0) + (a1+b1) X + (a2+b2) X2 + … like adding the vectors position-wise<4,2,3,…> + <5,1,1,….> = <9,3,4,…>OperationsA(X) = a0 X0 + a1 X1 + a2 X2 + … multiplying by XX * A(X) = 0 X0 + a0 X1 + a1 X2 + a2 X3 + … like shifting the vector entriesSHIFT<4,2,3,…> = <0,4,2,3,…>ExampleExample:V = nth row of Pascal’s triangleStore:V = <1,0,0,0,…>V = <1,1,0,0,…>V = <1,2,1,0,…>V = <1,3,3,1,…>V := <1,0,0,…>;Loop n times V := V + SHIFT(V);Example:V := <1,0,0,…>;Loop n times V := V + SHIFT(V);V = nth row of Pascal’s trianglePV := 1;PV := PV(1+X);ExampleExample:V := <1,0,0,…>;Loop n times V := V + SHIFT(V);V = nth row of Pascal’s triangleExamplePV = (1+ X)nAs expected, the coefficients of PV give the nth row of Pascal’s triangleTo summarize…i = 0aiXiP(X) =Given a sequence V = < a0, a1, a2, ..., an, … >associate a formal power series with itThis is the “generating function” for VFibonaccisi.e., the sequence <0,1,1,2,3,5,8,13…>is represented by the power series0 + 1X1 + 1X2 + 2 X3 + 3 X4 + 5 X5 + 8 X6 +…F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2Two RepresentationsA(X) = 0 + 1X1 + 1X2 + 2 X3 + 3 X4 + 5 X5 + 8 X6 +…F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2Can we write A(X) more succinctly?A(X) = F0 + F1 X1 + F2 X2 + F3 X3 + … + Fn Xn +…0 + F0 X1 + F1 X2 + F2 X3 + … + Fn-1 Xn +…X A(X) =0 + 0 X1 + F0 X2 + F1 X3 + … + Fn-2 Xn +…X2 A(X) =(1 – X – X2) A(X)(F0 – 0 – 0)+ (F1 – F0 – 0)X1+ 0=X=(1 – X – X2)XA(X) =FibonaccisF0 = 0, F1 = 1, Fn = Fn-1 + Fn-2(1 – X – X2)XA(X) = has the generating function i.e., the coefficient of Xn in A(X) is Fn1 – X – X2XX2 + X3-(X – X2 – X3)X2X3 + X4-(X2 – X3 – X4)+ X2-(2X3 – 2X4 – 2X5)+ 2X33X4 + 2X5+ 3X4-(3X4 – 3X5 – 3X6)5X5 + 3X6+ 5X5-(5X5 – 5X6 – 5X7)8X6 + 5X7+ 8X6-(8X6 – 8X7 – 8X8)Two representationsof the same thing…F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2(1 – X – X2)XA(X) =Closed form?F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2(1 – X – X2)XA(X) = let’s factor (1 – X – X2)(1 – X – X2) = (1 - φX)(1 – (-1/φ)X)where φ = 1 + √52Simplify, simplify…F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2XA(X) = (1 - φX)(1 – (-1/φ)X)A(X) = 1(1 - φX)1(1 – (-1/φ)X)√51√5-1+some elementary algebra omitted…**you are not allowed to say this in your answers…A(X) = 1(1 - φX)1(1 – (-1/φ)X)√51√5-1+1(1 - φX)=1 + φ X + φ2 X2 + … + φn Xn + … = 1 + Y1 + Y2 + Y3 + … + Yn + … 1 - Y 1the Infinite Geometric SeriesA(X) = 1(1 - φX)1(1 – (-1/φ)X)√51√5-1+1(1 - φX)=1 + φ X + φ2 X2 + … + φn Xn + … the coefficient of Xn in A(X) is…√51(-1/φ)n√5-1+φn1(1 – (-1/φ)X)=1 + (-1/φ) X + … + (-1/φ)n Xn + …√51(-1/φ)n√5-1+φnFn = where φ = 1 + √52J.P.M. Binet (1843)Closed form for FibonaccisLeonhard Euler (1765)Abraham de Moivre (1730)“golden ratio”√51(-1/φ)n√5-1+φnFn = Closed form for Fibonaccis√51φnFn = closest integer toTo recap…i = 0aiXiP(X) =Given a sequence V = < a0, a1, a2, ..., an, … >associate a formal power series with itThis is the “generating function” for VWe just used this for the Fibonaccis…MultiplicationA(X) = a0 + a1 X + a2 X2 + … B(X) = b0 + b1 X + b2 X2 + … multiply them together(A*B)(X) = (a0*b0) + (a0b1 + a1b0) X + (a0b2 + a1b1 + a2b0) X2 + (a0b3 + a1b2 + a2b1 + a3b0 ) X3 + … seems a bit less natural in the vector …
View Full Document