115-251Great Theoretical Ideas in Computer ScienceCounting II: Pigeons, Pirates and PascalLecture 7 (September 15, 2009)Addition Rule(2 Possibly Overlapping Sets)Let A and B be two finite sets:|A| + |B| - |A∩B||A∪B| = Difference MethodTo count the elements of a finite set S, find two sets A and B such that S = A \ BS U B = 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 B∀x,y∈A, x ≠ y ⇒ f(x) ≠ f(y)∀z∈B ∃x∈A 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!2A B∃ injective (1-1) f : A →→→→ B ⇒ | A | ≤ | B |BA∃ surjective (onto) f : A →→→→ B ⇒ | A | ≥ | B |AB∃ bijective f : A →→→→ B ⇒⇒⇒⇒ | A | = | B |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 P1possibilities for the first choice, P2for 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…Pnobjects 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 ways3DEFENSIVE 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)!=nrThe 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.4Claim: 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 letterboxes and n letters,there exists a letterbox with at leastn/m 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 the rearrange the letters in the word 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: r1of type 1, r2of type 2, …, rkof type knr1n-r1r2…n - r1 - r2- … - rk-1rkn!(n-r1)!r1!(n-r1)!(n-r1-r2)!r2!=…=n!r1!r2! … rk!514!2!3!2!= 3,632,428,800CARNEGIEMELLONRemember:The number of ways to arrange n symbols with r1of type 1, r2of type 2, …, rkof 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=6How many integer solutions to the following equations?x1+ x2+ x3+ x4+ x5= 20x1, x2, x3, x4, x5≥ 0Think of xkare 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:7Identical/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…4+ +( )+( ) =++ + + +Polynomials ExpressChoices and OutcomesProducts of Sum = Sums of Products4b2b3b1t1t2t1t2t1t2b1t1b1t2b2t1b2t2b3t1b3t2(b1+b2+b3)(t1+t2) = b1t1b1t2b2t1b2t2b3t1b3t2+ + + + +4There is a correspondence between paths in a choice tree and the cross terms of the product of polynomials!841 X 1 X1 X 1 X1 X1 X1 X1 XXX2XX2X2X3Choice Tree for Terms of (1+X)3Combine like terms to get 1 + 3X + 3X2+ X3The Binomial Formula(1+X)0=(1+X)1=(1+X)2=(1+X)3=(1+X)4=11 + 1X1 + 2X + 1X21 + 3X + 3X2+ 1X31 + 4X + 6X2+ 4X3+ 1X4What is a Closed Form Expression For ck?(1+X)n= c0+ c1X + c2X2+ … + cnXn(1+X)(1+X)(1+X)(1+X)…(1+X)After multiplying things out, but before combining like terms, we get 2ncross terms, each corresponding to a path in the choice
View Full Document
Unlocking...