英文版课件chapter 3

Chapter3：Counting计数,Counting,CountableSet可数集合Permutationsandcombinations排列与组合PigeonholePrinciple鸽巢原理ElementsofProbability概率基础RecurrenceRelations递归关系,CountableSet,AsetAiscountableifandonlyifwecanarrangeallofitselementsinalinearlistinadefiniteorder.“Definite”meansthatwecanspecifythefirst,second,thirdelement,andsoon.Ifthelistendedandwiththenthelementasitslastelement,itisfinite.Ifthelistgoesonforever,itisinfinite.,ProofofCountability,Thesetofallintegersiscountable.Wecanarrangeallintegerinalinearlistasfollows:0,-1,1,-2,2,-3,3,.thatis:positivekisthe(2k+1)thelement,andnegativekisthe2kthelementinthelist.Isthesetofrationalnumberscountable?yes!,SetofOrderedPairs,Thesetofallobjectswiththeformiscountable,wherei,jarenonnegativeintegers.,So,thesetofrationalnumbersiscountable.,3.1Permutations排列,回忆：好像还有一个加法原则：一件事情有两种做法，第一种做法有n种方式，第二种做法有m种方式，则完成这件事情共有mn种方法.,Theorem1:multiplicationprincipleofcounting(计数的乘法原理)SupposethattwotasksT1andT2aretobeperformedinsequence.IfT1canbeperformedinn1ways,andforeachofthesewaysT2canbeperformedinn2ways,thenthesequenceT1T2canbeperformedinn1n2ways.,Example:LetAbeaset.|A|=n.howmanysubsetsdoesAhave?|p(A)|=2n.Why?定义标识符：由字符开头的8位字符数字串或者一位字符,共有多少个合法标识符？含数字1的小于10000的正整数个数.,Theorem2：SupposethattasksT1,T2,.,Tkaretobeperformedinsequence.IfT1canbeperformedinn1ways,andforeachofthesewaysT2canbeperformedinn2ways,andforeachofthesen1n2waysofperformingT1T2insequence,T3canbeperformedinn3ways,andsoon,thenthesequenceT1T2Tk,canbeperformedinexactlyn1n2nkways.,Problem1:LetAbeanysetwithnelements.（1rn）Howmanydifferentsequences,eachoflengthr,canbeformedfromA,ifelementsmayberepeated?nrIfrepetitionisnotpermitted?n(n-1)(n-r+1)Theorem3：P93Theorem4：nPrthenumberofpermutationsofnobjectstakenratatime(norepetition)n个对象中每次取r个的排列数,permutationofA:whenn=r，nPn=n!,Examples:,从52张扑克牌中发5张牌，如果考虑发牌次序，共有多少种牌型？Howmany“words”ofthreedistinctletterscanbeformedfromthelettersof“MAST”?Howmany“words”ofthreeletterscanbeformedfromthelettersof“MAST”?Howmany“words”ofthreedistinctletterscanbeformedfromthelettersof“MASS”?Howmanydistinct“words”ofthreeletterscanbeformedfromthelettersof“MASS”?,Problem:Howmanydistinguishablepermutationsofthelettersintheword“BANANA”arethere?Permutationswithlimitedrepeat6!*N1N2issameas*N2N1*A1A2A3issameas*A3A2A1So:6!/(2!*3!)Theorem5：P95Howmanydistinct“words”ofthreeletterscanbeformedfromthelettersof“MASS”?4P3/2!,3.2Combinations组合,Problem:LetAbesetwithnelements,and1rn,howmanydifferentsubsetsofAarethere,eachwithrelements?(C)Permutationsof|A|takenratatime:nPrPermutationsofrelements:rPrnPr=CrPr,so,C=nPr/rPrTheorem1:nCr:numberofcombinationsofnobjectstakenratatime(n个对象每次取r个时的组合数).,Examples:,Problem:AthreeCDsprizefromTop10list;Repeatsareallowed,choiceislefttowinnerandtheorderisirrelevant;Supposechoicesarerecordedbyavoicemailsystem;Thenumberofwaysinwhichthewinnercanmake?12C3Theorem2：Supposekselectionsaretobemadefromnitemswithoutregardtoorderandthatrepeatsareallowed,assumingatleastkcopiesofeachofthenitems.Thenumberofwaystheseselectionscanbemadeis(n+k-1)Ck.,Examples:,Ex5:Password:Firstchar:a,b,c,d,e,f,gLast7chars:charandnumberEx6:Seven-personCommittee:4from30men3from20womenInGeneral:OrdermatterspermutationOrderdoesnotmattercombination,3.3PigeonholePrinciple鸽巢原理,Theorem1:Ifnpigeons(鸽子)areassignedtompigeonholes(鸽巢),andm0,thereare(n-m)pigeonshavenotbeenassigned.Itsacontradiction.,Examples,注意：鸽巢原理只是存在性证明，它保证至少有两个对象有这种性质，但是没有信息识别这些元素，只是保证它们的存在；与之相对，构造性证明是通过实际构造出具有某种特性的对象或对象群体来保证存在性。Thekey:Whatispigeonholeandwhatispigeon?Ex2:Showthatifanyfivenumbersfrom1to8arechosen,thentwoofthemwilladdto9.Ex3:Ifany11numbersarechosenfromtheset1,2,20,thenoneofthemwillbeamultipleofanother.,Ex4:NotTooFarApart,Problem:Wehavearegionboundedbyaregularhexagonwhosesidesareoflength1unit.Showthatifanysevenpointsarechoseninthisregion,thentwoofthemmustbenofartherapartthan1unit.,Theregioncanbedividedintosixequilateraltriangles,thenamong7pointsrandomlychoseninthisregionmustbetwolocatedwithinonetriangle.,ShakingHandsataGathering,Situation:atagatheringofnpeople,everyoneshookhandswithatleastoneperson,andnooneshookhandsmorethanoncewiththesameperson.Problem:showthattheremusthavebeenatleasttwoofthemwhohadthesamenumberofhandshaking.Solution:Pigeon:thenparticipantsPigeonhole:differentnumberbetween1andn-1.,ExtendedPigeonholePrinciple推广的鸽巢原理,Theorem2:Ifnpigeonsareassignedtompigeonholes,mrecurrencerelationan=2+3(n-1)=explicitformulaE.g.2bn=2bn-1+1,b1=7bn=2n+2-1,ThinkingRecursively:Problem1,TowersofHanoiHowmanymovesareneedtomoveallthediskstothethirdpegbymovingonlyoneatatimeandneverplacingadiskontopofasmallerone.,T(1)=1T(n)=2T(n-1)+1,SolutionofTowersofHanoi,T(n)=2T(n-1)+12T(n-1)=4T(n-2)+24T(n-2)=8T(n-3)+4.2n-2T(2)=2n-1T(1)+2n-2,T(n)=2n-1,ThinkingRecursively:Problem2,CuttingtheplaneHowmanysectionscanbegeneratedatmostbynstraightlineswithinfinitelength.,Linen,Intersectingalln-1existinglinestogetasmostsectionsaspossible,L(0)=1L(n)=L(n-1)+n,SolutionofCuttingthePlane,L(n)=L(n-1)+n=L(n-2)+(n-1)+n=L(n-3)+(n-2)+(n-1)+n=L(0)+1+2+(n-2)+(n-1)+n,ThinkingRecursively:Problem3,JosephussproblemFindthepositiontolive,ordie!,1,9,10,3,4,5,7,8,2,6,1,9,10,3,4,5,7,8,2,6,11,J(10,2)=5;,J(13,2)=7;,ThinkingRecursively:Problem3(cont.),JosephussproblemGivennpeople,mthmanwillbeexecuted.Findthepositiontolive,ordie!JustJ(n,m),Whenm=2:J(1)=1J(2n)=2J(n)-1J(2n+1)=2J(n)+1,LinearHomogeneousRelation,iscalledlinearhomogeneousrelationofdegreek.,Yes,No,CharacteristicEquation,Foralinearhomogeneousrecurrencerelationofdegreekthepolynomialofdegreekiscalleditscharacteristicequation.Thecharacteristicequationoflinearhomogeneousrecurrencerelationofdeg