CompSci 102 © Michael Frank11.1Today’s topics••CountingCounting––Generalized Pigeonhole PrincipleGeneralized Pigeonhole Principle––PermutationsPermutations––CombinationsCombinations––Binomial CoefficientsBinomial Coefficients––Writing permutation algorithmsWriting permutation algorithms••Reading: Sections 4.2-4.3, 4.4, 4.6Reading: Sections 4.2-4.3, 4.4, 4.6••UpcomingUpcoming––ProbabilityProbabilityCompSci 102 © Michael Frank11.2Generalized Pigeonhole Principle••If If NN objects are assigned to objects are assigned to kk places, then at places, then atleast one place must be assigned at least least one place must be assigned at least NN//kk objects. objects.••E.g.E.g., there are , there are NN=280 students in this class.=280 students in this class.There are There are kk=52 weeks in the year.=52 weeks in the year.––Therefore, there must be at least 1 week duringTherefore, there must be at least 1 week duringwhich at least which at least 280/52280/52= = 5.385.38=6 students in=6 students inthe class have a birthday.the class have a birthday.CompSci 102 © Michael Frank11.3Proof of G.P.P.••By contradiction. Suppose every place hasBy contradiction. Suppose every place has< < NN//kk objects, thus objects, thus NN//kk11..••Then the total number of objects is at mostThen the total number of objects is at most••So, there are less than So, there are less than NN objects, which objects, whichcontradicts our assumption of contradicts our assumption of NN objects! objects! NkNkkNkkNk ==+< 111CompSci 102 © Michael Frank11.4G.P.P. Example••Given: There are 280 students in the class.Given: There are 280 students in the class.––Without knowing anybodyWithout knowing anybody’’s birthday, what iss birthday, what isthe largest value of the largest value of nn for which we can prove for which we can proveusing the G.P.P. that at least using the G.P.P. that at least nn students must students musthave been born in the same month?have been born in the same month?••Answer:Answer:280/12 = 23.3 = 24CompSci 102 © Michael Frank11.5Permutations (§4.3)••A A permutationpermutation of a set of a set SS of objects is a of objects is asequence that contains each object in sequence that contains each object in SSexactly once.exactly once.––An ordered arrangement of An ordered arrangement of rr distinct elements distinct elementsof of SS is called an is called an r-permutation of Sr-permutation of S..••The number of The number of rr-permutations of a set with-permutations of a set withnn=|=|S|S| elements is elements isPP((nn,,rr) = ) = nn((nn11))……((nnrr+1) = +1) = nn!/(!/(nnrr)!)!CompSci 102 © Michael Frank11.6Permutation Example••You are in a silly action movie where thereYou are in a silly action movie where thereis a bomb, and it is your job to disable it byis a bomb, and it is your job to disable it bycutting wires to the trigger device. Therecutting wires to the trigger device. Thereare 10 wires to the device. If you cutare 10 wires to the device. If you cutexactly the right three wires, in exactly theexactly the right three wires, in exactly theright order, you will disable the bomb,right order, you will disable the bomb,otherwise it will explode! If the wires allotherwise it will explode! If the wires alllook the same, what are your chances oflook the same, what are your chances ofsurvival?survival?P(10,3) = 10·9·8 = 720,so there is a 1 in 720chance that you’ll survive!CompSci 102 © Michael Frank11.7Combinations (§4.3)••An An rr-combination of elements of a set -combination of elements of a set SS is simply is simplya subset a subset TTSS with with rr members, members, ||TT|=|=rr..••The number of The number of r-r-combinations of a set with combinations of a set with nn=|=|SS||elements iselements is••Note that Note that CC((nn,,rr) = ) = CC((nn, , nnrr))––Because choosing the Because choosing the rr members of members of TT is the same thing is the same thingas choosing the as choosing the nnrr non-members of non-members of TT..)!(!!!)!/(!),(),(),(rnrnrrnnrrPrnPrnrnC=== =CompSci 102 © Michael Frank11.8Combination Example••How many distinct 7-card hands can beHow many distinct 7-card hands can bedrawn from a standard 52-card deck?drawn from a standard 52-card deck?––The order of cards in a hand doesnThe order of cards in a hand doesn’’t matter.t matter.••Answer Answer CC(52,7) = (52,7) = PP(52,7)/(52,7)/PP(7,7)(7,7)= 52= 52·51·50·49·48·47·46 / 7·6·5·4·3·2·1·51·50·49·48·47·46 / 7·6·5·4·3·2·1710821752·17·10·7·47·46 = 133,784,560CompSci 102 © Michael Frank11.9Binomial coefficients••Binomial coefficientBinomial coefficient––Given (1 + Given (1 + xx))r––What are the coefficients of What are the coefficients of xxr ??––Show for (1 + Show for (1 + xx))44nr CompSci 102 © Michael Frank11.10Important Theorems on Binomials••Binomial Binomial thereomthereom––In the expansion of (1 + In the expansion of (1 + xx))nn, the coefficient of , the coefficient of xxrr equalsequalsCC((nn,,rr))••PascalPascal’’s Identitys Identity••Proofs?Proofs?CompSci 102 © Michael Frank11.11§4.6, Generating Perms. & Combs.••We will go over algorithms for:We will go over algorithms for:––Generating the next largest permutation, inGenerating the next largest permutation, inlexicographic order.lexicographic order.––Generating the next largest bit string.Generating the next largest bit string.••Remember, a bit string can represent a combination.Remember, a bit string can represent a combination.––Generating the next Generating the next rr-combination in lexicographic-combination in lexicographicorder.order.••Also weAlso we’’ll give recursive algorithms forll give recursive algorithms forgenerating permutations, combinations, and generating permutations, combinations, and rr--combinations.combinations.CompSci 102 © Michael Frank11.12Generating All Permutationsprocedureprocedure genAllPermsgenAllPerms((nn>0: integer)>0: integer){output all permutations of the integers{output all permutations of the integers1,..,1,..,nn, in
View Full Document
Unlocking...