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 X1 X2 X3 Warm Up Question a Could Your iPod Be Holding the Greatest Mystery in Modern Science Plan If Google is a religion what is its God Counting with generating functions Solving the Diophantine equations Proving combinatorial identities B Chazelle http www cs princeton edu chazelle pubs algorithm html Computing The Algorithm will be the most disruptive scientific paradigm since quantum mechanics Counting with Generating Functions We start with George Polya s approach Applied Combinatorics by Alan Tucker It would have to be The Algorithm Generatingfunctionology by Herbert Wilf Jan 12 2006 The Economist 1 There is a correspondence between paths in a choice tree and the cross terms of the product of polynomials 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 1 x 5 1 x 1 x 1 x 1 x 1 x Take the coefficient of x2 2 Counting with Generating Functions The two apples are identical 0 apple 1 apple 0 orange 1 orange 0 pear 1 pear 0 banana 1 banana 0 plum 1 plum In this notation apple2 stand for choosing 2 apples and stands for an exclusive or 5 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 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 1 x x 1 x 1 x 1 x 1 x 2 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 Take the coefficient of x2 11 2 If the polynomial 1 x x2 4 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 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 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 x x2 x3 x4 apple cheese raspberry 1 3x 6x2 9x3 11x4 11x5 9x6 6x7 3x8 x9 The coefficient by x8 shows that there are only 3 orders for 8 pastries Note we solve the whole parameterized family of problems 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 x9 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 3 Coefficient by xR in 1 x x2 3 1 x x2 3 Find the number of ways to select R balls from a pile of 2 red 2 green and 2 blue balls e e e X 1X 2X 3 x0 x1 x2 x0 x1 x2 x0 x1 x2 e1 e2 e 3 R e e e X 1X 2X 3 0 b ek b 2 x1 x2 x3 x4 21 0 xk 7 Exercise Find the number of integer solutions to Observe x1 x2 x3 x4 21 0 xk 7 Than Exercise Find the number of integer solutions to x1 x2 x3 x4 21 0bxkb7 Take the coefficient by x21 in 1 x x2 x3 x4 x5 x6 x7 4 x1 x2 x3 x4 21 0 xk 7 The problem is reduced to solving 0 xk 7 1 xk 1 6 0 b xk 1 b 5 x1 1 x2 1 x3 1 x4 1 21 4 y1 y2 y3 y4 17 0bykb5 Solution take the coefficient by x17 in 1 x x2 x3 x4 x5 4 which is 20 4 Solution Problem x1 x2 x3 9 1bx1b2 2bx2b4 1bx3b4 x1 x2 x3 9 1bx1b2 2bx2b4 1bx3b4 x x2 x2 x3 x4 x x2 x3 x4 Take the coefficient by x9 in the product of generating functions 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 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 Counting with Generating Functions 1 x x2 x3 1 x2 x4 1 x x2 x3 cheese raspberry apple There is a problem with the above expression 5 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 The power series a0 a1 x a2 x2 is the generating function for the infinite sequence ex a0 a1 a2 1 2x 4x2 6x3 8x4 A famous generating function from calculus k 0 xk k ak x k k 0 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 What is the coefficient of Xk in the expansion of 1 X X 2 X3 X4 n A solution to e1 e2 en k Coefficient by xN in ek 0 1 x x2 2 1 x 2 6 y 1 x x2 What is the coefficient of Xk in the expansion of 1 X X2 X3 X4 n 1 x x 2 n k 1 n k k 0 n k 1 1 x x2 1 1 x n k 0 k xk 1 1 x xn 1 x 1 1 x x2 xn 1 when x 1 1 x x 2 x n 1 xy x x2 y x y 1 But what is the LHS k n k 1 x k 1 x 1 x n y 1 x 1 1 1 x y 1 x x2 We will be dealing with formal power series also called generating functions k 0 ak xk when x 1 7 The coefficients can be any complex numbers though we will be mainly working over the integers Power series have no analytic interpretation We …
View Full Document
Unlocking...