6.042/18.] Mathematics for Computer Science March 31. 2005 Srini devadas and Eric Lehman Lecture notes Counting Il We realize everyone has been working pretty hard this term, and were considering Warding some prizes for truly exceptional coursework. Here are some possible categories Best Administrative Critique We asserted that the quiz was closed-book. On the cover page, one strong candidate for this award wrote, There is no book. Best Collaboration Statement Inspired by the student who wrote"I worked alone"on 1 Olfactory Fixation Award A surprisingly competitive category this term, this goes to the student who comes up with the greatest number of odor-related mathematical ex- amples We also considered some less flattering categories such as Proof Most Likely Readable from the Surface of the Moon, Solution Most Closely Resembling a Football Play Diagram with Good Yardage Potential, etc. But then we realized that you all might think up sim- ilar"awards"for the course staff and decided to turn the whole matter into a counting problem. In how many ways can, say, three different prizes be awarded to n people? Remember our basic strategy for counting 1. Learn to count sequences 2. Translate everything else into a sequence-counting problem via bijections We'll flesh out this strategy considerably today but the rough outline above is good r now So we first need to find a bijection that translates the problem about awards into a problem about sequences. Let P be the set of n people in 6.042. Then there is a bijection from ways of awarding the three prizes to the set Px PxP. In particular, the assignment person r wins prize #1, y wins prize #2, and z wins prize #3 maps to the sequence(a, y, 2). All that remains is to count these sequences. By the Product Rule, we have P×P×P=|P|·|P|·|P Thus, there are nways to award the prizes to a class of n people ' Actually, these notes were written last fall, but the problem sets are no easier this term.6.042/18.062J Mathematics for Computer Science March 31, 2005 Srini Devadas and Eric Lehman Lecture Notes Counting II We realize everyone has been working pretty hard this term1, and we’re considering awarding some prizes for truly exceptional coursework. Here are some possible categories: Best Administrative Critique We asserted that the quiz was closed­book. On the cover page, one strong candidate for this award wrote, “There is no book.” Best Collaboration Statement Inspired by the student who wrote “I worked alone” on quiz 1. Olfactory Fixation Award A surprisingly competitive category this term, this goes to the student who comes up with the greatest number of odor­related mathematical ex￾amples. We also considered some less flattering categories such as Proof Most Likely Readable from the Surface of the Moon, Solution Most Closely Resembling a Football Play Diagram with Good Yardage Potential, etc. But then we realized that you all might think up sim￾ilar “awards” for the course staff and decided to turn the whole matter into a counting problem. In how many ways can, say, three different prizes be awarded to n people? Remember our basic strategy for counting: 1. Learn to count sequences. 2. Translate everything else into a sequence­counting problem via bijections. We’ll flesh out this strategy considerably today, but the rough outline above is good enough for now. So we first need to find a bijection that translates the problem about awards into a problem about sequences. Let P be the set of n people in 6.042. Then there is a bijection from ways of awarding the three prizes to the set P ×P ×P. In particular, the assignment: “person x wins prize #1, y wins prize #2, and z wins prize #3” maps to the sequence (x, y, z). All that remains is to count these sequences. By the Product Rule, we have: | | | P × P × P = P P P 3 | · | | · | | = n Thus, there are n3 ways to award the prizes to a class of n people. 1Actually, these notes were written last fall, but the problem sets are no easier this term. :­)