Problem 1(a)(b)Problem 2(a)(b)(c)(d)Problem 3(a)(b)(c)(d)Problem 4(a)(b)(c)(d)(e)Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 16 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised November 27, 2005, 851 minutes Problem Set 8 Due: November 21 Reading: Counting Notes, II.§4–5; Notes on Generating Functions Problem 1. Find the coefficients of (a) x10 in (x + (1/x))100 2(b) xk in (x − (1/x))n . Problem 2. Suppose a generalized World Series between the Sox and the Cardinals in-volved 2n + 1 games. As usual, the generalized Series will stop as soon as one team has won more than half the possible games. (a) Suppose that when the Sox finally win the GSeries, the Cards have managed to win exactly r games (so r ≤ n). How many possible win-loss patterns are possible for the Sox to win the GSeries in this way? Express your answer as a binomial coefficient. (b) How many possible win-loss patterns are possible for the Sox to win the GSeries when the Cards win at most r games? Express your answer as a binomial coefficient. (c) Give a combinatorial proof that r� � � �� n + i n + r + 1 = . (1)i r i=0 (d) Verify equation (1) by induction using algebra. Copyright © 2005, Prof. Albert R. Meyer.2 Problem Set 8 Problem 3. (a) 1 Let an be the number of length n ternary strings (strings of the digits 0, 1, and 2) that contain two consecutive digits that are the same. For example, a2 = 3 since the only ternary strings of length 2 with matching consecutive digits are 11, 22, and 33. Also, a0 = a1 = 0, since in order to have consecutive matching digits, a string must be of length at least two. Find a recurrence formula for an. (b) Show that x−x + 1 − 2x (1 − 3x)(1 − 2x) is a closed form for the generating function of the sequence a0, a1, . . . (c) Find real numbers r and s such that 1 r s = + . (1 − 2x)(1 − 3x) 1 − 2x 1 − 3x (d) Use the previous results to write a closed form for the nth term in the sequence. Problem 4. Suppose there are four kinds of doughnuts: plain, chocolate, glazed, and butterscotch. Write generating functions for the number of ways to select the flavors of n doughnuts, subject to the following different constraints. (a) Each flavor occurs an odd number of times. (b) Each flavor occurs a multiple of 3 times. (c) There are no chocolate doughnuts and at most one glazed doughnut. (d) There are 1, 3, or 11 chocolate doughnuts, and 2, 4, or 5 glazed. (e) Each flavor occurs at least 10 times. 1From Rosen, 5th ed., §6.1, Exercise 34.Massachusetts Institute of Technology Solutions cover sheet 6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 16 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld Student’s Solutions to Problem Set 8 Your name: Due date: November 21 Submission date: Circle your TA: David Jelani Sayan Hanson Collaboration statement: Circle one of the two choices and provide all pertinent info. 1. I worked alone and only with course materials. 2. I collaborated on this assignment with: got help from:1 and referred to:2 DO NOT WRITE BELOW THIS LINE Problem Score 1 2 3 4 Total Copyright © 2005, Prof. Albert R. Meyer. All rights reserved. 1People other than course staff. 2Give citations to texts and material other than the Fall ’02 course
View Full Document
Unlocking...