Problem 1Problem 2Problem 3� � � � � Massachusetts Institute of Technology 6.042J/18.062J, Spring ’10: Mathematics for Computer Science April 14 Prof. Albert R. Meyer revised April 16, 2010, 1343 minutes Problem Set 10 Due: April 23 Reading: Notes Ch. 16.10–16.12 Problem 1. Let’s develop a proof of the Inclusion-Exclusion formula using high school algebra. (a) Most high school students will get freaked by the following formula, even though they actu-ally know the rule it expresses. How would you explain it to them? n(1 − xi) = (−1)|I| xj . (1) i=1 I⊆{1,...,n} j∈I Hint: Show them an example. For any set, S, let MS be the membership function of S: MS(x) = 1 if x ∈ S, 0 if x /∈ S. Let S1, . . . , Sn be a sequence of finite sets, and abbreviate MSi as Mi. Let the domain of discourse, D, be the union of the Si’s. That is, we let n D ::= Si, i=1 and take complements with respect to D, that is, T ::= D − T, for T ⊆ D. (b) Verify that for T ⊆ D and I ⊆ {1, . . . n}, MT = 1 − MT , (2) M(T Si)= MSi , (3)i∈I i∈I � M(S Si)= 1 − (1 − Mi). (4)i∈I i∈I (Note that (3) holds when I is empty because, by convention, an empty product equals 1, and an empty intersection equals the domain of discourse, D.) Creative Commons 2010, Prof. Albert R. Meyer.� � � � ����� � ����� � ������ � ������ � � � � � � � � � � � � � � 2 Problem Set 10 (c) Use (1) and (4) to prove MD = (−1)|I|+1 Mj . (5) ∅�=I⊆{1,...,n} j∈I (d) Prove that |T | = MT (u). (6) u∈D (e) Now use the previous parts to prove (−1)|I|+1 Si (7) | D | = ∅�=I⊆{1,...,n} i∈I (f) Finally, explain why (7) immediately implies the usual form of the Inclusion-Exclusion Prin-ciple: | D | = n� i=1 (−1)i+1 I⊆{1,...,n}|I|=i j∈I Sj . (8) Problem 2. Give combinatorial proofs of the identities below. Use the following structure for each proof. First, define an appropriate set S. Next, show that the left side of the equation counts the number of elements in S. Then show that, from another perspective, the right side of the equation also counts the number of elements in set S. Conclude that the left side must be equal to the right, since both are equal to |S|. (a) 2n n= n k · n − k k=0 n n (b) ri r i=0 Hint: consider a set of binary strings that could be counted using the right side of the equation, then try partitioning them into subsets countable by the elements of the sum on the left. Problem 3. According to the Multinomial Theorem 16.11.3, (x1 + x2 + ... + xk)n can be expressed as a sum of n + i = n + r + 1 terms of the form n r1 r2 rkx1 x2 ...xk . r1, r2, ..., rk (a) How many terms are there in the sum?� � 3 Problem Set 10 (b) The sum of these multinomial coefficients has an easily expressed value: � n = kn (9) r1, r2, ..., rk r1+r2+...+rk=n, ri∈N Give a combinatorial proof of this identity. Hint: How many terms are there when (x1 + x2 + ... + xk)n is expressed as a sum of monomials in xi before terms with like powers of these variables are collected together under a single coefficient?4 Problem Set 10Massachusetts Institute of Technology Solutions cover sheet 6.042J/18.062J, Spring ’10: Mathematics for Computer Science April 14 Prof. Albert R. Meyer Student’s Solutions to Problem Set 10 Your name: Due date: April 23 Submission date: Circle your TA/LA: Megumi Tom Richard Eli 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 Total Creative Commons 2010, Prof. Albert R. Meyer. 1People other than course staff. 2Give citations to texts and material other than the Spring ’10 course materials.MIT OpenCourseWarehttp://ocw.mit.edu 6.042J / 18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...