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 Technology6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 16Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised November 27, 2005, 851 minutesProblem Set 8Due: November 21Reading: Counting Notes, II.§4–5; Notes on Generating FunctionsProblem 1. Find the coefficients of(a) x10in (x + (1/x))100(b) xkin (x2− (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 haswon more than half the possible games.(a) Suppose that when the Sox finally win the GSeries, the Cards have managed to winexactly r games (so r ≤ n). How many possible win-loss patterns are possible for the Soxto 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 GSerieswhen the Cards win at most r games? Express your answer as a binomial coefficient.(c) Give a combinatorial proof thatrXi=0n + ii=n + r + 1r. (1)(d) Verify equation (1) by induction using algebra.Copyright © 2005, Prof. Albert R. Meyer. All rights reserved.Problem Set 8 2Problem 3. (a)1Let anbe 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 sincethe 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 oflength at least two.Find a recurrence formula for an.(b) Show that−x1 − 2x+x(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 that1(1 − 2x)(1 − 3x)=r1 − 2x+s1 − 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, andbutterscotch. Write generating functions for the number of ways to select the flavors of ndoughnuts, 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 sheet6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 16Prof. Albert R. Meyer and Prof. Ronitt RubinfeldStudent’s Solutions to Problem Set 8Your name:Due date: November 21Submission date:Circle your TA: David Jelani Sayan HansonCollaboration 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:1and referred to:2DO NOT WRITE BELOW THIS LINEProblem Score1234TotalCopyright © 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...