1Generating Functions IGreat Theoretical Ideas In Computer ScienceV. AdamchikD. SleatorCS 15-251 Spring 2010Lecture 6 Jan. 28, 2010 Carnegie Mellon University++()+() = ?X1X2++X3Could Your iPod Be Holding the Greatest Mystery in Modern Science?Warm-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 EconomistIf 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 approach2ProblemUla 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, apple2stand 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 a polynomial expansionf(x)=a0 + a1x + …+ anxnis the generating functionfor the sequencea0,a1,…,an3If the polynomial (1+x+x2)4is the generating polynomialfor 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 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 x8shows 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 x8shows 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 xRin (1+x+x2)34Coefficient by xRin (1+x+x2)3(1+x+x2)3 = (x0+x1+x2)(x0+x1+x2)(x0+x1+x2)3e2e1eXXX Find the number of ways to select R balls from a pile of 2 red, 2 green and 2 blue ballse1 + e2 + e3 = R0 b ekb 23e2e1eXXX ExerciseFind the number of integer solutions tox1+x2+x3+x4=210bxkb7Take the coefficient by x21in (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< 7Observe0 < xk< 7 -1 < xk-1 < 6 0 b xk-1 b 5Than (x1-1)+(x2-1)+(x3-1)+(x4-1) = 21-4x1+x2+x3+x4=210<xk<7The problem is reduced to solvingy1 + y2 + y3 + y4 = 17, 0bykb5 Solution: take the coefficient by x17in (1+x+x2+x3+x4+x5)4which is 205Problemx1+x2+x3=91bx1b22bx2b41bx3b4Solutionx1+x2+x3=91bx1b2 (x+x2) 2bx2b4 (x2+x3+x4)1bx3b4 (x+x2+x3+x4)Take the coefficient by x9in the product of generating functions.Two observations1. A generating function approach is designed to model a selection of allpossible numbers of objects.2. It can be used not only for counting but for solving the linear DiophantineequationsThe 251-staff Danish partyAdam 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.6Counting 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 + a1x + a2x2+…is the generating functionfor the infinitesequencea0, a1, a2, …,0kkkxaA famous generating function from calculus:0!kxkxekWe can use the generating function technique to solve almost all the mathematical problems you have met in your life so far.ExerciseCount the number of N-letter combinations of MATH in which M and A appear with repetitions and T and H only once.Coefficient by xNin (1+x+x2+…)2(1+x)2What is the coefficient of Xkin the expansion of:( 1 + X + X2 + X3 + X4 + . . . . )n?A solution to: e1+ e2+ . . . + en = kek≥ 07What is the coefficient of Xkin the expansion of:( 1 + X + X2 + X3 + X4 +. . . . )nk1knBut what is the LHS?x11...xx120kkn 2x k1kn...)xx(1...xx1yx-111x)-y(11 yx -y... x x yx...xx1 y2220kk x k1kn n x) - (11x-1x x...xx 1n1-n21...(when x ≠ 1)(when |x| < 1)1-xx x...xx 1n1-n21We will be dealing with formalpower series (also called generating functions)0kkkxa8The coefficients can be any complex numbers, though we will be mainly working over the integers.0kkkxaPower series have no analytic interpretation.0kkkxaFORMAL MANIPULATION:We deal with power series as we deal we numbers!FORMAL MANIPULATION:1/P(X) is defined to be the polynomial Q(X) such that Q(X) P(X) = 1.Th: P(X) will have a reciprocal if and only if a00. In this case, the reciprocal is unique.Power series make a commutative ring!FORMAL MANIPULATION:The derivative of is defined by:9Power Series = Generating FunctionGiven a sequence of integers a0, a1, …, anWe will associate with it a functionThe On-Line Encyclopedia of Integer Sequences 0kkkxaf(x)Generating FunctionsSequence: 1, 1, 1, 1, …Generating function:x11xxaf(x)0kk0kkkFind a generating function f(x) 1, 2, 3, 4, 5,
View Full Document
Unlocking...