Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15The Pigeonhole PrincipleExample of how to use the pigeonhole principle…Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Another combinatorial proofSlide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 8315-251Great Theoretical Ideas in Computer ScienceCounting II: Pigeons, Pirates and PascalLecture 7 (February 3, 2009)Addition Rule(2 Possibly Overlapping Sets)Let A and B be two finite sets:|A| + |B| - |AB||AB| =Difference MethodTo count the elements of a finite set S, find two sets A and B such that S = A \ BandB µ Athen |S| = |A| - |B|f is injective if and only iff is surjective if and only ifLet f : A B Be a Function From a Set A to a Set Bx,yA, xyf(x) f(y)zB xA f(x) = zf is bijective if f is both injective and surjectiveCorrespondence PrincipleIf two finite sets can be placed into bijection, then they have the same sizeIt’s one of the most important mathematical ideas of all time!The number of subsets of an n-element set is 2nProduct RuleSuppose every object of a set S can be constructed by a sequence of choices with P1 possibilities for the first choice, P2 for the second, and so on. IF 1. Each sequence of choices constructs an object of type S2. No two different sequences create thesame objectThere are P1P2P3…Pn objects of type SANDTHENThe three big mistakes people make in associating a choice tree with a set S are:1. Creating objects not in S2. Missing out some objects from the set S3. Creating the same object two different waysDEFENSIVE THINKINGask yourself:Am I creating objects of the right type?Can I create every object of this type? Can I reverse engineer my choice sequence from any given object?Permutations vs. Combinationsn!(n-r)!n!r!(n-r)!=nrOrderedUnorderedNumber of ways of ordering, per-muting, or arranging r out of n objectsn choices for first place, n-1 choices for second place, . . .n × (n-1) × (n-2) ×…× (n-(r-1))n!(n-r)!=n “choose” rA combination or choice of r out of n objects is an (unordered) set of r of the n objectsThe number of r combinations of n objects:n!r!(n-r)!=nrABif |A| > |B| there is at least one b in Bwith two elements a and a’ in A mapping to itABif |A| > |B| there is at least one b in Bwith two elements a and a’ in A mapping to itThe Pigeonhole PrincipleIf there are n pigeons placed in n-1 holesthen some pigeonhole contains at least two pigeonsalso known the Dirichlet’s (box) principleExample of how to use the pigeonhole principle…At a party with n people, some handshaking took place.Each pair shook hands at most onceShow that there exist two people who shook the same number of hands.Claim: if someone shook n-1 hands, no one can have shaken 0 hands.The number of shakes done by people lie inthe set {0, 1, 2, …, n-1} the number of shakes either all lie in{0, 1, 2, …, n-2}or {1, 2, …, n-1} there are n people and n-1 possible values. two people with the same number of shakesThe “Letterbox” PrincipleIf there are m letters and n letterboxes,there exists a letterbox with at leastm/n lettersNow, continuing on last Now, continuing on last week’s theme…week’s theme…How many ways to How many ways to rearrange the letters in rearrange the letters in the word the word “SYSTEMS”??SYSTEMS7 places to put the Y, 6 places to put the T, 5 places to put the E, 4 places to put the M, and the S’s are forced7 X 6 X 5 X 4 = 840SYSTEMSLet’s pretend that the S’s are distinct:S1YS2TEMS3There are 7! permutations of S1YS2TEMS3But when we stop pretending we see that we have counted each arrangement of SYSTEMS 3! times, once for each of 3! rearrangements of S1S2S37!3!= 840Arrange n symbols: r1 of type 1, r2 of type 2, …, rk of type knr1n-r1r2…n - r1 - r2 - … - rk-1rkn!(n-r1)!r1!(n-r1)!(n-r1-r2)!r2!=…=n!r1!r2! … rk!14!2!3!2!= 3,632,428,800CARNEGIEMELLONRemember:The number of ways to arrange n symbols with r1 of type 1, r2 of type 2, …, rk of type k is:n!r1!r2! … rk!5 distinct pirates want to divide 20 identical, indivisible bars of gold. How many different ways can they divide up the loot?Sequences with 20 G’s and 4 /’sGG/G//GGGGGGGGGGGGGGGGG/represents the following division among the pirates: 2, 1, 0, 17, 0In general, the ith pirate gets the number of G’s after the i-1st / and before the ith /This gives a correspondence between divisions of the gold and sequences with 20 G’s and 4 /’sSequences with 20 G’s and 4 /’sHow many different ways to divide up the loot?244How many different ways can n distinct pirates divide k identical, indivisible bars of gold?n + k - 1n - 1n + k - 1k=How many integer solutions to the following equations?x1 + x2 + x3 + x4 + x5 = 20x1, x2, x3, x4, x5 ≥ 0Think of xk are being the number of gold bars that are allotted to pirate k244How many integer solutions to the following equations?x1 + x2 + x3 + … + xn = kx1, x2, x3, …, xn ≥ 0n + k - 1n - 1n + k - 1k=How many integer solutions to the following equations?x1 + x2 + x3 + … + xn = kx1, x2, x3, …, xn ≥ 1How many integer solutions to the following equations?x1 + x2 + x3 + … + xn = kx1, x2, x3, …, xn ≥ 1in bijection with solutions tox1 + x2 + x3 + … + xn = k-nx1, x2, x3, …, xn ≥ 0MultisetsA multiset is a set of elements, each of which has a multiplicityThe size of the multiset is the sum of the multiplicities of all the elementsExample: {X, Y, Z} with m(X)=0 m(Y)=3, m(Z)=2Unary visualization: {Y, Y, Y, Z, Z}Counting Multisets=n + k - 1n - 1n + k - 1kThe number of ways to choose a multiset of size k from n types of elements is:Identical/Distinct DiceSuppose that we roll seven diceHow many different outcomes are there, if order matters?67What if order doesn’t matter?(E.g., Yahtzee)127Remember to distinguish betweenIdentical / Distinct ObjectsIf we are putting k objects into n distinct bins.Objects are distinguishableObjects are indistinguishablek+n-1knkOn to Pascal…The Binomial
View Full Document