Great Theoretical Ideas In Computer Science V Adamchik D Sleator Lecture 6 CS 15 251 Jan 28 2010 Spring 2010 Carnegie Mellon University Generating Functions I X 1 X 2 X 3 Warm Up Question a Could Your iPod Be Holding the Greatest Mystery in Modern Science B Chazelle http www cs princeton edu chazelle pubs algorithm h tml Computing The Algorithm will be the most disruptive scientific paradigm since quantum mechanics If Google is a religion what is its God It would have to be The Algorithm Jan 12 2006 The Economist Plan Counting with generating functions Solving the Diophantine equations Proving combinatorial identities Applied Combinatorics by Alan Tucker Generatingfunctionology by Herbert Wilf Counting with Generating Functions We start with George Polya s approach 1887 1985 Hungarian mathematician Problem Ula is allowed to choose two items from a tray containing an apple an orange a pear a banana and a plum In how many ways can she choose 5 2 There is a correspondence between paths in a choice tree and the cross terms of the product of polynomials Counting with Generating Functions 0 apple 1 apple 0 orange 1 orange 0 pear 1 pear 0 banana 1 banana 2 In this 0 notation apple stand for plum 1 plum choosing 2 apples and stands for an exclusive or 5 1 x 1 x 1 x 1 x 1 x 1 x Take the coefficient of x2 Problem Ula is allowed to choose two items from a tray containing TWO apples an orange a pear a banana and a plum In how many ways can she choose The two apples are identical Counting with Generating Functions 0 apple 1 apple 2 apple 0 orange 1 orange 0 pear 1 pear 0 banana 1 banana 0 plum 1 plum 2 1 x x 1 x 1 x 1 x 1 x Take the coefficient of x2 11 The function f x that has a polynomial expansion f x a0 a1 x an xn is the generating function for the sequence a0 a1 an If the polynomial 1 x x2 4 is the generating polynomial for ak what is the combinatorial meaning of ak The number of ways to select k object from 4 types with at most 2 of each type The 251 staff Danish party The 251 staff wants to order a Danish pastry from La Prima Unfortunately the shop only has 2 apple 3 cheese and 4 raspberry pastries left What the number of possible orders Counting with Generating Functions 1 x x2 1 x x2 x3 1 x x2 x3 x4 apple cheese raspberry 4 5 6 7 8 1 3x 6x2 9x3 11x 11x 9x 6x 3x 8 The coefficient by x shows that there are only 3 9 x orders for 8 pastries Note we solve the whole parameterized family of problems The 251 staff wants to order a Danish pastry from La Prima The shop only has 2 apple 3 cheese and 4 raspberry pastries left What the number of possible orders Raspberry pastries come in multiples of two Counting with Generating Functions 1 x x2 1 x x2 x3 1 x2 x4 apple cheese raspberry 1 2x 4x2 5x3 6x4 6x5 5x6 4x7 2x8 x 9 The coefficient by x8 shows that there are only 2 possible orders Problem Find the number of ways to select R balls from a pile of 2 red 2 green and 2 blue balls Coefficient by xR in 1 x x2 3 Coefficient by xR in 1 x x2 3 1 x x2 3 x0 x1 x2 x0 x1 x2 x0 x1 x2 e e e e e e 3 1 2 3 1 2 X X X X Find the number of ways to select R balls from a pile of 2 red 2 green and 2 blue balls e e e 3 1 2 X X X e1 e2 e3 R 0 ek 2 Exercise Find the number of integer solutions to x1 x2 x3 x4 21 0 xk 7 Take the coefficient by x21 in 1 x x2 x3 x4 x5 x6 x7 4 Exercise Find the number of integer solutions to x1 x2 x3 x4 21 0 xk 7 x1 x2 x3 x4 21 0 xk 7 Observe 0 xk 7 1 xk 1 6 0 xk 1 5 Than x1 1 x2 1 x3 1 x4 1 21 4 x1 x2 x3 x4 21 0 xk 7 The problem is reduced to solving y1 y2 y3 y4 17 0 yk 5 Solution take the coefficient by x17 in 1 x x2 x3 x4 x5 4 which is 20 Problem x1 x2 x3 9 1 x1 2 2 x2 4 1 x3 4 Solution x1 x2 x3 9 1 x1 2 2 x2 4 1 x3 4 x x2 x2 x3 x4 x x2 x3 x4 Take the coefficient by x9 in the product of generating functions Two observations 1 A generating function approach is designed to model a selection of all possible numbers of objects 2 It can be used not only for counting but for solving the linear Diophantine equations The 251 staff Danish party Adam pulls a few strings and a large apple Danish factory is built next to the CMU The 251 staff Danish party Unfortunately still only 3 cheese and 4 raspberry pastries are available Raspberry pastries come in multiples of two What the number of possible orders Counting with Generating Functions 1 x x2 x3 1 x2 x4 1 x x2 x3 cheese raspberry There is a problem with the above expression apple Counting with Generating Functions 1 x x2 x3 1 x2 x4 1 x x2 x3 cheese raspberry apple 1 x 2x2 2x3 2x4 2x5 x6 x7 1 x x2 x3 1 2x 4x2 6x3 8x4 The power series a0 a1 x a2 x2 is the generating function for the infinite sequence a0 a1 a2 a k 0 k x k A famous generating function from calculus k x e k 0 k x We can use the generating function technique to solve almost all the mathematical problems you have met in your life so far Exercise Count the number of N letter combinations of MATH in which M and A appear with repetitions and T and H only once Coefficient by xN in 1 x x2 2 1 x 2 What is the coefficient of Xk in the expansion of 1 X X 2 X3 X4 n A solution to e1 e2 en k ek 0 What is the coefficient of Xk in the expansion of 1 X X2 X3 X4 n n k k 1 GF for the pirates and gold problem n k 1 k x 1 x x k k 0 2 n But what is the LHS 1 1 x x 1 x 2 2 y 1 x x x y 2 x x y x y 1 y 1 x 1 1 2 y 1 x x 1 x GF for the pirates and gold problem n k 1 k 1 x 1 x n k 0 k n x 1 1 x x x x 1 2 n …
View Full Document
Unlocking...