15 251 Great Theoretical Ideas in Computer Science Counting III Generating Functions Lecture 8 February 5 2009 X 1 X 2 X 3 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 Formal Power Series P X aiXi i 0 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 F 0 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 X 5 1 1 X 1 1 X 2 X2 n Xn 1 X 1 1 1 X 1 n Xn 1 1 X the coefficient of Xn in A X is 1 1 n 1 n 5 5 Closed form for Fibonaccis Fn 1 n 1 1 n 5 5 where 1 5 2 golden ratio Abraham de Moivre 1730 Leonhard Euler 1765 J P M Binet 1843 Closed form for Fibonaccis Fn 1 n 1 1 n 5 5 1 n Fn closest integer to 5 To recap 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 We just used this for the Fibonaccis Multiplication A 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 X2 seems a bit less natural in the vector representation it s called a convolution there Mult special case A X a0 a1 X a2 X2 1 2 Special case B X 1 X X 1 X multiply them together A B X a0 a0 a1 X a0 a1 a2 X2 a0 a1 a2 a3 X2 it gives us partial sums For example 1 Suppose A X 1 X X2 1 X and B X 1 X X2 1 1 X then A B X 1 2X 3X2 4X3 1 1 1 X 1 X 1 1 X 2 Generating function for the sequence 0 1 2 3 4 What happens if we again take prefix sums 1 Take 1 2X 3X 4X 1 X 2 2 3 multiplying through by 1 1 X 1 1 2X 3X 4X 1 X 3 1 2 3 Generating function for the triangular numbers What s the pattern 1 1 1 1 1 2 3 4 1 1 X 1 1 X 2 1 2 3 4 1 1 X 3 1 1 X n What s the pattern 0 0 1 2 0 0 3 0 1 2 3 4 1 1 X 1 1 X 2 1 2 3 4 1 1 X 3 1 1 X n What s the pattern 0 0 1 2 0 0 3 0 1 1 2 3 1 1 4 1 1 1 X 1 1 X 2 1 2 3 4 1 1 X 3 1 1 X n What s the pattern 0 0 1 2 0 0 3 0 1 1 2 3 1 1 4 1 2 2 3 4 2 2 5 2 1 1 X 1 1 X 2 1 1 X 3 1 1 X n What s the pattern 0 0 1 2 0 0 …
View Full Document
Unlocking...