COMPSCI 102.ppt

文档介绍：COMPSCI102IntroductiontoDiscreteMathematicsX1X2++X3Lecture8(September21,2007)CountingIIIHowmanywaystorearrangethelettersintheword“SYSTEMS”?SYSTEMS7placestoputtheY,6placestoputtheT,5placestoputtheE,4placestoputtheM, andtheS’sareforced7X6X5X4=840SYSTEMSLet’spretendthattheS’saredistinct:S1YS2TEMS3Thereare7!permutationsofS1YS2TEMS3ButwhenwestoppretendingweseethatwehavecountedeacharrangementofSYSTEMS3!times,onceforeachof3!rearrangementsofS1S2S37!3!=840Arrangensymbols:r1oftype1,r2oftype2,…,rkoftypeknr1n-r1r2…n-r1-r2-…-rk-1rk(n-r1)!(n-r1-r2)!r2!n!(n-r1)!r1!=…=n!r1!r2!…rk!14!2!3!2!=3,632,428,800CARNEGIEMELLONRemember:Thenumberofwaystoarrangensymbolswithr1oftype1,r2oftype2,…,rkoftypekis:n!r1!r2!…rk!5distinctpirateswanttodivide20identical,?Sequenceswith20G’sand4/’sGG/G//GGGGGGGGGGGGGGGGG/representsthefollowingdivisionamongthepirates:2,1,0,17,0Ingeneral,theithpirategetsthenumberofG’safterthe(i-1)st/andbeforetheith/Thisgivesacorrespondence(bijection)betweendivisionsofthegoldandsequenceswith20G’sand4/’s