CPS102- Homework 4Due on November 13, 2006Questions may continue on the back. Please write clearly. What I cannot read, I will not grade. Typedhomework is preferable. A good compromise is to type the words and write the math by hand. Show allyour work in detail.The Duke Community Standard requires every undergraduate student to sign the statement below uponcompletion of each academic assignment. I am not allowed to accept your assignment unless you sign on theline below, if you intend to return this sheet, or you copy and sign the same statement on your own paper.I have adhered to the Duke Community Standard in completing this assignment.Signature:In all answers, show your work in detail.1. In this problem we address the following question, posed by Alan Tucker:In how many ways can a four-member committee with at least two women be formed from four men and sixwomen, and so that Mr. John Baggins and Mrs. Samantha Baggins, both among the candidates, will not servetogether?Of course, people are distinguishable. For instance, two committees with four women are different if they are composed ofdifferent women.Since this problem is tricky (as most combinatorial problems are), we will solve it in two different ways, and verify thatwe obtain the same solution.(a) Let Cmbe the set of committees with m men, for m = 0, 1, 2, ignoring the rule about the Bagginses. What are thecardinalities ](Cm) for each value of m? Answer with both a general formula in terms of m and actual numbers.(b) For each value of m = 0, 1, 2, let Vmbe the set of committees with m men that violate the rule about the Bagginses.Find the cardinalities ](Vm). Again, use a formula and actual numbers in your answer.(c) Assemble your answer to the committee problem from the cardinalities you found in your previous answers. Whendoing so, state clearly the reasons why you can add or subtract any values you add or subtract. Use the expressionKmfor the number of valid committees with m men, and K for the total number of valid committees. A committee isvalid if it satisfies all conditions of the problem.(d) As a sanity check, and as an exercise on a different method for counting, compute K by the counting method for setsof structured elements described in Section 3 of the handout on counting. To this end, determine first the numberO of committees you could form if the order in which the committee members are chosen were to matter (i.e., twocommittees that differ only by the order in which the members are chosen are temporarily assumed to be differentcommittees). This will give you a greater numb er of committees than in your previous answer. In the question afterthis, you will be asked to correct for this over-counting.Thus, an ordered committee is made of P = 4 parts: member 1, member 2, member 3, and member 4. For each part,a member is one of four choices, whenever possible: M for “male but not Mr. Baggins,” F for “female but not Mrs.Baggins,” J for “Mr. John Baggins,” or S for “Mrs. Samantha Baggins.” Build a labelled tree of depth 4 as describedin the handout, and compute the number O of ordered committees from it.Make sure that you do not draw dead ends (subtrees that cannot lead to valid committees). Show your tree and yourmath in detail. Because of the (at most) four options for each part, the tree grows wide. Please redraw the tree untilyou get a decent drawing, don’t just hand in a bowl of spaghetti. It is OK to break the tree into subtrees and displayCPS102 — Duke — November 5, 2006the subtrees separately if you wish. In that case, label the subtree roots (say S1, etc), and use the labels to show clearlywhere each subtree is to be appended. Warning: this exercise requires patience.(e) In the previous question, committees with the same people listed in different orders were considered as different com-mittees. How many times is each unordered committee counted in the set of ordered committees? In other words, bywhat factor is O greater than K?(f) Determine K from O, and check that the answer is the same you obtained earlier with the set composition method.If you obtain different answers, check and revise your work until the two numbers agree. Counting unordered committeesby counting ordered ones first is useful as a sanity check. Hopefully, this exercise will also make you appreciate theimportance of choosing a counting method that is appropriate for a given problem.2. Prove by direct manipulation that the following identity holds for m ≥ n ≥ k ≥ 0µmn¶µnk¶=µmk¶µm − kn − k¶.3. Prove that(x + y + z)n=nXi=0n−iXj=0µni¶µn − ij¶xiyjzn−i−jfor n ≥ 0.CPS102 — Duke — November 5,
View Full Document
Unlocking...