Generating Functions ISlide 2Slide 3Slide 4Slide 5Counting with Generating FunctionsSlide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Find the number of ways to select R balls from a pile of 2 red, 2 green and 2 blue ballsSlide 21Slide 22x1+x2+x3+x4 = 21 0 < xk< 7x1+x2+x3+x4=21 0<xk<7Slide 25Slide 26Two observationsSlide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Power Series = Generating FunctionGenerating FunctionsSlide 51Slide 52Slide 53Slide 54Proving Identities with GFSlide 56Slide 57Slide 58Slide 59Computing Combinatorial SumsSlide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Generating Functions IGreat Theoretical Ideas In Computer ScienceGreat Theoretical Ideas In Computer ScienceV. AdamchikV. AdamchikD. SleatorD. SleatorCS 15-251 Spring CS 15-251 Spring 20102010Lecture 6Lecture 6Jan. 28, 2010Jan. 28, 2010Carnegie Mellon Carnegie Mellon UniversityUniversity++()+( ) = ? X1 X2 + + X3Could Your iPod Be Holding the Greatest Mystery in Modern Science?Warm-Up QuestionWarm-Up Questiona“ Computing (The Algorithm) will be the most disruptive scientific paradigm since quantum mechanics." B.Chazelle http://www.cs.princeton.edu/~chazelle/pubs/algorithm.htmlIt would have to be The Algorithm. Jan. 12, 2006, The Economist If Google is a religion, what is its God?Plan• Counting with generating functions• Solving the Diophantine equations• Proving combinatorial identitiesApplied Combinatorics, by Alan TuckerGeneratingfunctionology, by Herbert WilfCounting with Generating FunctionsWe start with George Polya’s approach(1887-1985), Hungarian mathematician.ProblemUla 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?52There is a correspondence between paths in a choice tree and the cross terms of the product of polynomials!Counting with Generating Functionsx)x)(1x)(1x)(1x)(1(1x)(15(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.Take the coefficient of x2.ProblemUla 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 Functionsx)x)(1x)(1x)(1)(1xx(1211(0 apple + 1 apple + + 2 apple)(0 orange + 1 orange)(0 pear + 1 pear)(0 banana + 1 banana)(0 plum + 1 plum)Take the coefficient of x2.The function f(x) that has The function f(x) that has a polynomial expansiona polynomial expansionf(x)=af(x)=a0 0 + a+ a11 x + …+ a x + …+ ann x xnn is the is the generating functiongenerating function for the sequencefor the sequenceaa00, a, a11, …, a, …, annIf the polynomial (1+x+x2)4 is the generating polynomialfor ak, what is the combinatorial meaning of ak?The number of ways to select k The number of ways to select k object from 4 types with at object from 4 types with at most 2 of each typemost 2 of each type..The 251-staff Danish partyThe 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= 1+3x+6x2+9x3+11x4+11x5+9x6+6x7+3x8+x9The coefficient by x8 shows that there are only 3 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+x9The coefficient by x8 shows that there are only 2 possible orders.ProblemFind the number of ways to select R balls from a pile of 2 red, 2 green and 2 blue ballsCoefficient by xR in (1+x+x2)33213e2e1eeeeXXXX Coefficient by xR in (1+x+x2)3(1+x+x2)3 = (x0+x1+x2)(x0+x1+x2)(x0+x1+x2)Find the number of ways to select R balls from a pile of 2 red, 2 green and 2 blue ballse1 + e2 + e3 = R0 ek 23e2e1eXXXExerciseFind the number of integer solutions tox1+x2+x3+x4=210xk7Take the coefficient by x21 in (1+x+x2+x3+x4+x5+x6+x7)4ExerciseFind the number of integer solutions tox1+x2+x3+x4 = 210 < xk< 7x1+x2+x3+x4 = 210 < xk< 7ObserveObserve 0 < 0 < xk < 7 -1 < -1 < xk-1 < 6 0 xk-1 5Than (x1-1)+(x2-1)+(x3-1)+(x4-1) = 21-4x1+x2+x3+x4=210<xk<7The problem is reduced to solvingThe problem is reduced to solving y1 + y2 + y3 + y4 = 17, 0yk5 Solution: take the coefficient by x17 in (1+x+x2+x3+x4+x5)4which is 20which is 20Problemx1+x2+x3=91x122x241x34Solution x1+x2+x3=9 1x12 (x+x2) 2x24 (x2+x3+x4) 1x34 (x+x2+x3+x4)Take the coefficient by x9 in the product of generating functions.Two observations1. A generating function approach is 1. A generating function approach is designed to model a selection of designed to model a selection of allall possible numbers of objects.possible numbers of objects.2. It can be used not only for 2. It can be used not only for counting but for solving the linear counting but for solving the linear DiophantineDiophantine equations equationsThe 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 apple There is a problem (…) with the above expression.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 The power series aa0 0 + a+ a11 x + a x + a22 x x22 +… +…is the is the generating functiongenerating function for the for the infiniteinfinite sequence
View Full Document