15 251 Great Theoretical Ideas in Computer Science Counting III Generating Functions Lecture 8 September 17 2009 X 1 X 2 X 3 Recap The Binomial Formula 1 X 0 1 1 X 1 1 1X 1 X 2 1 2X 1X2 1 X 3 1 3X 3X2 1X3 1 X 4 1 4X 6X2 4X3 1X4 Pascal s Triangle kth row are coefficients of 1 X k Inductive 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 extraordinary 1 how fertile in properties the 1 1 triangle is 1 2 1 Everyone can try his 1 3 3 1 hand 1 4 6 4 1 1 1 5 6 10 15 10 20 5 15 1 6 1 Summing on kth Avenue 1 1 1 1 1 1 1 6 2 4 6 1 4 10 20 i k 1 3 10 15 1 3 5 n 1 5 15 1 6 1 i n 1 k 1 k Fibonacci Numbers 1 2 1 1 3 1 2 1 5 8 1 3 3 1 13 1 1 1 4 5 6 6 10 15 4 10 20 1 5 15 1 6 1 Sums of Squares n 1 1 12 12 1 1 1 22 32 4 5 6 1 6 12 4 10 20 2n n n k 12 32 10 15 k 0 2 1 5 15 1 6 1 All these properties can be proved inductively and algebraically We gave combinatorial proofs using the Manhattan block walking representation of binomial coefficients How many shortest routes from A to B A B 10 5 Manhattan jth street 4 3 2 1 0 0 1 2 kth avenue 3 4 j k There are k shortest routes from 0 0 to j k Manhattan Level n 4 3 There are 2 1 0 0 1 2 kth avenue 3 4 n shortest routes from 0 0 to n k k k Manhattan Level n 4 3 There are 2 1 n k 0 0 1 2 kth avenue 3 4 shortest routes from 0 0 to n and kth avenue level Level n 4 3 2 1 0 0 1 2 kth avenue 3 4 n n 1 n 1 k k 1 k Level n 4 3 2 1 0 How many ways to get to via 0 1 2 kth avenue 3 4 n k 2 Level n 4 3 2 1 0 n k 0 0 2 1 2 kth avenue 3 n 2n k n 4 Level n 4 3 2 1 0 0 1 2 kth avenue 3 4 i k n 1 k 1 How many ways to get to via Level n 4 3 2 1 0 n i k 0 1 2 kth avenue 3 4 n 1 k 1 i n 1 k k 1 1 X1 X2 X3 Xn 2 Xn 1 Xn 1 X 1 1 Xn 1 X Recall the Geometric Series 1 X X X X 1 2 3 1 n 1 X the Infinite Geometric Series Holds when X 1 Also makes sense if we view the infinite sum on the left as a formal power series P X 1 X1 X2 X3 Xn 1 2 X X X3 Xn Xn 1 X P X 1 X P X 1 P X 1 1 X Formal Power Series P X aiXi i 0 There are no worries about convergence issues This is a purely syntactic object Formal Power Series P X aiXi i 0 If you want think of as the infinite vector V a0 a1 a2 an But as you will see thinking of as a polynomial is very natural Operations A 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 Operations A X a0 X0 a1 X1 a2 X2 multiplying by X X A X 0 X0 a0 X1 a1 X2 a2 X3 like shifting the vector entries SHIFT 4 2 3 0 4 2 3 Example Example V 1 0 0 Loop n times V V SHIFT V Store V V V V 1 0 0 0 1 1 0 0 1 2 1 0 1 3 3 1 V nth row of Pascal s triangle Example Example V 1 0 0 PV 1 Loop n times V V SHIFT V PV PV 1 X V nth row of Pascal s triangle Example Example V 1 0 0 Loop n times V V SHIFT V PV 1 X n V nth row of Pascal s triangle As expected the coefficients of PV give the nth row of Pascal s triangle To summarize Given a sequence V a0 a1 a2 an associate a formal power series with it P X aiXi i 0 This is the generating function for V Fibonaccis F0 0 F1 1 Fn Fn 1 Fn 2 i e the sequence 0 1 1 2 3 5 8 13 is represented by the power series 0 1X1 1X2 2 X3 3 X4 5 X5 8 X6 Two Representations F0 0 F1 1 Fn Fn 1 Fn 2 A X 0 1X1 1X2 2 X3 3 X4 5 X5 8 X6 Can we write A X more succinctly A X F0 F1 X1 F2 X2 F3 X3 Fn Xn X A X 0 F X1 F X2 F2 X3 F Xn 0 1 n 1 X2 A X 0 0 X1 F0 X2 F1 X3 Fn 2 Xn 1 X X2 A X F0 0 0 F1 F0 0 X1 0 X A X X 1 X X2 Fibonaccis F0 0 F1 1 Fn Fn 1 Fn 2 has the generating function A X X 1 X X2 i e the coefficient of Xn in A X is Fn X X2 2X3 3X4 5X5 8X6 1 X X2 X X X2 X3 X2 X3 X2 X3 X4 2X3 X4 2X3 2X4 2X5 3X4 2X5 3X4 3X5 3X6 5X5 3X6 5X5 5X6 5X7 8X6 5X7 8X6 8X7 8X8 Two representations of the same thing F0 0 F1 1 Fn Fn 1 Fn 2 A X X 1 X X2 Closed form F0 0 F1 1 A X Fn Fn 1 Fn 2 X 1 X X2 let s factor 1 X X2 1 X X2 1 X 1 1 X where 1 5 2 Simplify simplify F0 0 F1 1 Fn Fn 1 Fn 2 X A X 1 X 1 1 X some elementary algebra omitted 1 1 1 1 A X 5 1 X 5 1 1 X you are not allowed to say this in your answers 1 1 1 1 A X 5 1 X 5 1 1 X 1 1 X 2 X2 n Xn 1 X 1 1 Y 1 Y 1 Y2 Y 3 Y n the Infinite Geometric Series 1 1 1 1 A X 5 1 …
View Full Document
Unlocking...