6.042/18.] Mathematics for Computer Science Apri!8,2005 Srini devadas and Eric Lehman Notes for recitation 16 Problem 1. Find closed-form generating functions for the following sequences. Do not concern yourself with issues of convergence (a)(2,3,5,0,0,0,0.,…) Solution 2+3x+5 (b)(1,1,1,1,1,1,1,) Solution 1+x+x2+x3+...= (c)(1,2,4,8,16,32,64, Solution 1+2x+4x2+8x32+…=(2x)+(2x)2+(2x)2+(2x)3+ (d)(1,0,1,0.,1,0,1,0,…) Solution 1+x2+x4 (e)(0,0,0,1,1,1,1,1, Solution x3(1+x+x2 (f)(1,3,5,7,9.,11
6.042/18.062J Mathematics for Computer Science April 8, 2005 Srini Devadas and Eric Lehman Notes for Recitation 16 Problem 1. Find closedform generating functions for the following sequences. Do not concern yourself with issues of convergence. (a) �2, 3, 5, 0, 0, 0, 0, . . .� Solution. 2 + 3x + 5x 2 (b) �1, 1, 1, 1, 1, 1, 1, . . .� Solution. 1 3 1 + x + x 2 + x + . . . = 1 − x (c) �1, 2, 4, 8, 16, 32, 64, . . .� Solution. 3 1 3 1 + 2x + 4x 2 + 8x + . . . = (2x) 0 + (2x) + (2x) 2 + (2x) + . . . 1 = 1 − 2x (d) �1, 0, 1, 0, 1, 0, 1, 0, . . .� Solution. 1 4 6 1 + x 2 + x + x + . . . = 1 − x2 (e) �0, 0, 0, 1, 1, 1, 1, 1, . . .� Solution. 3 3 4 5 6 3 3 x x + x + x + x + . . . = x (1 + x + x 2 + x + . . .) = 1 − x (f) �1, 3, 5, 7, 9, 11, . . .�
Recitation 16 Solution d d 1 1+x+x2+x3+ 1+2x+3x2+4xr2+ 2 2+4x+6x2+8x2+ 1+3x+5x2+7x3+ (1-x)
Recitation 16 2 Solution. 1 3 1 + x + x 2 + x + . . . = 1 − x d d 1 1 + x + x 2 + x 3 + . . . = dx dx 1 − x 1 2 1 + 2x + 3x 2 + 4x + . . . = (1 − x ) 2 2 2 2 + 4x + 6x 2 + 8x + . . . = (1 − x ) 2 2 1 3 1 + 3x + 5x 2 + 7x + . . . = (1 − x )2 − 1 − x 1 + x = (1 − x)2
Recitation 16 Problem 2. Find a closed-form generating function for the sequence where tn is the number of different ways to compose a bag of n donuts subject to the following restrictions (a) All the donuts are chocolate and there are at least 3 Solution (b) all the donuts are glazed and there are at most 4 Solution 1 (c) All the donuts are coconut and there are exactly 2 Solution (d) All the donuts are plain and the number is a multiple of 4. Solution (e) The donuts must be chocolate, glazed, coconut, or plan and There must be at least 3 are chocolate donuts There must be at most 4 glazed There must be exactly 2 coconut. There must be a multiple of 4 plain Solution 121-1 x5(1+x2+x3+x4) (1-x)(1-x4)
Recitation 16 3 Problem 2. Find a closedform generating function for the sequence (t0, t1, t2, . . .) where tn is the number of different ways to compose a bag of n donuts subject to the following restrictions. (a) All the donuts are chocolate and there are at least 3. Solution. 3 x 1 − x (b) All the donuts are glazed and there are at most 4. Solution. 1 − x5 1 − x (c) All the donuts are coconut and there are exactly 2. Solution. 2 x (d) All the donuts are plain and the number is a multiple of 4. Solution. 1 1 − x4 (e) The donuts must be chocolate, glazed, coconut, or plan and: • There must be at least 3 are chocolate donuts. • There must be at most 4 glazed. • There must be exactly 2 coconut. • There must be a multiple of 4 plain. Solution. x3 1 − x5 5 3 1 x (1 + x2 + x + x4) 2 x = 1 − x 1 − x 1 − x4 (1 − x)(1 − x4)
Recitation 16 Problem 3. [20 points] A previous problem set introduced us to the Catalan numbers Co, C1, C2,..., where the n-th of them equals the number of balanced strings that can be built with 2n paretheses. Here is a list of the first several of them 42132429143048621679658 Then, in lecture we were all amazed to see that the decimal expansion of the irrational number500000-1000√/24999 1.000001000002000005000014000042000132000429001430004862016796058786208012 encodes"these numbers! Now there are many reasons why one may want to turn to religion, but this revelation is probably not a good one. Let's explain why (a) Let pn be the number of balanced strings containing n('s. Explain why the fol- lowing recurrence hold Po (the empty string for n >1 k=1 Solution. Note that every nonempty balanced string consists of a sequence of one or more balanced strings. The first balanced string in the sequence must begin with a( and end with a"matching"). That is, any balanced string, rn, with n>1('s consists of a balanced string, Sk-1, enclosed in brackets and containing k-1 ('s followed by a balanced string, tn-k, with n-k('s n=(Sk-1)followed by t where 1 <k<n. This observation leads directly to the recurrence (b) Now consider the generating function for the number of balanced strings P(a)=po+plC+p2.c4+P3.'+ Prove that P(ar)=rP(a)+ Solution. We can verify this equation using the recurrence relation (x)2 x(+(Pp1+p1p)x+(p2+p1p1+p2pb)x2+…)+1 1+p2x+(P0p1+p1P0)x2+(P2+pp1+p2p)x23+ t p1C+ p2C-+ p3I
� Recitation 16 4 Problem 3. [20 points] A previous problem set introduced us to the Catalan numbers: C0, C1, C2, . . . , where the nth of them equals the number of balanced strings that can be built with 2n paretheses. Here is a list of the first several of them: n 0 1 2 3 4 5 6 7 8 9 10 11 12 Cn 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 Then, in lecture we were all amazed to see that the decimal expansion of the irrational number 500000 − 1000√249999 1.000001000002000005000014000042000132000429001430004862016796058786208012 . . . “encodes” these numbers! Now, there are many reasons why one may want to turn to religion, but this revelation is probably not a good one. Let’s explain why. (a) Let pn be the number of balanced strings containing n (’s. Explain why the following recurrence holds: p0 = 1, (the empty string) n pn = pk−1 · pn−k, for n ≥ 1. k=1 Solution. Note that every nonempty balanced string consists of a sequence of one or more balanced strings. The first balanced string in the sequence must begin with a ( and end with a “matching” ). That is, any balanced string, rn, with n ≥ 1 (’s consists of a balanced string, sk−1, enclosed in brackets and containing k − 1 (’s, followed by a balanced string, tn−k, with n − k (’s: rn = (sk−1) followed by tn−k where 1 ≤ k ≤ n. This observation leads directly to the recurrence. (b) Now consider the generating function for the number of balanced strings: 3 P(x) = p0 + p1x + p2x 2 + p3x + · · · . Prove that P(x) = xP(x) 2 + 1. Solution. We can verify this equation using the recurrence relation. xP(x) 2 + 1 = x(p0 + p1x + p2x 2 + p3x 3 + · · ·) 2 + 1 = x(p 2 0 + (p0p1 + p1p0)x + (p0p2 + p1p1 + p2p0)x 2 + · · ·) + 1 = 1 + p 2 0x + (p0p1 + p1p0)x 2 + (p0p2 + p1p1 + p2p0)x 3 + · · · = 1 + p1x + p2x 2 + p3x 3 + · · · = P(x)
Recitation 16 (c) Find a closed-form expression for the generating function P(a) Solution. Given that P(a)=aP()2+1, the quadratic formula implies that 1土 P(a) If z is small, then P(a) should be about po= 1. Therefore, the correct choice of sign P (d) Show that P(1/100000=5000001000√24999 Solution P(1/100000 1-y1-4/10000 2/1000000 /24999 500000-500000 250000 5000001000√249999 (e) Explain why the digits of this irrational number encode these successive numbers of balanced strings Solution. Suppose that we symbolically carry out the substitution done in the pre- ceding problem part P(x)=p+p1x+p2x2+3x3+ P(10-6)=p+p10-6+m210-12+p310-18+ hus, po appears in the units position, pi appears in the millionths position, p2 ap pears in the trillionths position, and so forth
Recitation 16 5 (c) Find a closedform expression for the generating function P(x). Solution. Given that P(x) = xP (x)2 + 1, the quadratic formula implies that 1 ± √1 − 4x P(x) = . 2x If x is small, then P(x) should be about p0 = 1. Therefore, the correct choice of sign is 1 − √1 − 4x P(x) = . 2x (d) Show that P(1/1000000) = 500000 − 1000√249999. Solution. � P(1/1000000) = 1 − 1 − 4/1000000 2/1000000 �249999 = 500000 − 500000 250000 = 500000 − 1000√ 249999 (e) Explain why the digits of this irrational number encode these successive numbers of balanced strings. Solution. Suppose that we symbolically carry out the substitution done in the preceding problem part. 3 P(x) = p0 + p1x + p2x 2 + p3x + · · · P(10−6 ) = p0 + p110−6 + p210−12 + p310−18 + · · · Thus, p0 appears in the units position, p1 appears in the millionths position, p2 appears in the trillionths position, and so forth
Recitation 16 Problem 4. Consider the following recurrence equation n=0 Tn={2 1 n-1+3Tn-2(n≥ Let f(a) be a generating function for the sequence(T0, T1, T2, T3, (a)Give a generating function in terms of f(a)for the sequence (1,2,2Ti+310,22+3T1,213+312, Solution. We can break this down into a linear combination of three sequences 1,2,0,0,0, 0,T0,T1,T2,T3,…)=xf(x) 0,0,T,T1,T,…)=x2f(x) In particular, the sequence we want is very nearly generated by 1+2 r+ 2 f(ar)+ 3x f(a). However, the second term is not quite correct; were generating 2+2T0=4 instead of the correct value, which is 2. We correct this by subtracting 2.c from the generating function, which leaves 1+2xf(x)+3x2f(x) (b)Form an equation in f(r)and solve to obtain a closed-form generating function Solution. The equation f(x)=1+2rf(x)+3x2f(x) equates the left sides of all the equations defining the sequence To, T1, T2, .with all the right sides. Solving for f(a) gives the closed-form generating function ∫(x) (c) Expand the closed form for f(a)using partial fractions Solution We can write (1+x)(1-3 Thus there exist constants A and B such that: f()
� � � � � Recitation 16 6 Problem 4. Consider the following recurrence equation: ⎧ ⎪⎨ ⎪⎩ 1 n = 0 Tn = 2 n = 1 2Tn−1 + 3Tn−2 (n ≥ 2) Let f(x) be a generating function for the sequence �T0, T1, T2, T3, . . .�. (a) Give a generating function in terms of f(x) for the sequence: �1, 2, 2T1 + 3T0, 2T2 + 3T1, 2T3 + 3T2, . . .� Solution. We can break this down into a linear combination of three sequences: 1, 2, 0, 0, 0, . . . = 1 + 2x 0, T0, T1, T2, T3, . . . = xf(x) 0, 0, T0, T1, T2, . . . � = x2f(x) In particular, the sequence we want is very nearly generated by 1 + 2x + 2xf(x) + 3x2f(x). However, the second term is not quite correct; we’re generating 2 + 2T0 = 4 instead of the correct value, which is 2. We correct this by subtracting 2x from the generating function, which leaves: 1 + 2xf(x) + 3x 2 f(x) (b) Form an equation in f(x) and solve to obtain a closedform generating function for f(x). Solution. The equation f(x) = 1 + 2xf(x) + 3x 2 f(x) equates the left sides of all the equations defining the sequence T0, T1, T2, . . . with all the right sides. Solving for f(x) gives the closedform generating function: 1 f(x) = 1 − 2x − 3 2 x (c) Expand the closed form for f(x) using partial fractions. Solution. We can write: 1 − 2x − 3 2 x = (1 + x)(1 − 3x) Thus, there exist constants A and B such that: 1 A B f(x) = = + 1 − 2x − 3x2 1 + x 1 − 3x
Recitation 16 Now substituting a =0 and r=l gives the system of equations 1=A+B 1 A B Solving the system, we find that A=1/4 and B=3/4. Therefore, we have /43/4 1+x (d) Find a closed-form expression for Tn from the partial fractions expansion Solution. Using the formula for the sum of an infinite geometric series gives f(x)=(1-x+x2-x3+x4-…)+(1+3x+32x2+3x32+3x4+…) Thus, the coefficient of xn is: 3 (-1)+x·32
Recitation 16 7 Now substituting x = 0 and x = 1 gives the system of equations: 1 = A + B 1 A B − =4 2 − 2 Solving the system, we find that A = 1/4 and B = 3/4. Therefore, we have: 1/4 3/4 f(x) = + 1 + x 1 − 3x (d) Find a closedform expression for Tn from the partial fractions expansion. Solution. Using the formula for the sum of an infinite geometric series gives: 1 � � 3 � � 1 − x + x 2 3 4 2 3 4 4 f(x) = 4 − x + x − . . . + 4 1 + 3x + 3 x 2 + 3 x 3 + 3 x + . . . Thus, the coefficient of xn is: 1 3 3n Tn = 4 · (−1)n + 4 ·