Session-3-permutaiton-combination-probability-排列组合

1、1.PERMUTATIONSupposenobjectsaretobeorderedfrom1sttonth,eachorderiscalledapermutation.Applythemultiplicationprincipletocountthenumberofpermutationsofnobjects,i.e.n(n-1)(n-2)(n-3)....(3)(2)(1),orn!,callednfactorial.e.g.Supposethat10studentsaregoingonabustrip,andeachofthestudentswillbeassignedtooneofthe10availableseats.Whatisthenumberofpossibledifferentseatingarrangementsofthestudentsonthebus?Notice:nobjectsshouldbedistinguishableandtheyarealwaysorderedinaline.Iftheobjectsarenotorderedinalinebutin。

2、othershapes,suchasacircleorasquare,howtocalculatethenumberofpermutations?e.g.Fivestudentsaregoingtositaroundatable,howmanyarrangementcantherebe?(Iftherelativepositionoftwostudentsisthesame,thenweviewitasonearrangement.)formula:(n-1)!Iftherearesomeobjectsareexactlythesame,thenumberofpermutationsshouldbecalculatedinanotherway.e.g.Howmanydifferentfive-letterwordscanbeformedwhenalllettersinthewordENTERareusedeachtime.formula:n!/(numberofrepeatedobjects)!Supposethatkobjectswillbeselectedfromasetofnob。

3、jects,wherek=n,andthekobjectswillbeplacedinorderfrom1sttokth.Thenumberofpermutationisn(n-1)(n-2)....(n-k+1).e.g.Howmanydifferentfive-digitpositiveintegerscanbeformedusingthedigits1,2,3,4,5,6,and7ifnoneofthedigitscanoccurmorethanonceintheinteger?2.CombinationGiventhefivelettersA,B,C,D,andE,determinethenumberofwaysofselecting3ofthe5letters,butunlikebefore,youdonotwanttocountdifferentordersforthe3letters.i.e.Notethatnchoosekisalwaysequaltonchoosen-ke.g.Youshouldchoose3-personcommitteefromagroupof9s。

4、tudents.Howmanywaysaretheretodothis?Thedifferencebetweenpermutationandcombinationiswhetherorderisconsidered.Ifdifferentordermakesdifferentarrangement,itispermutation,andifdifferentordermakesnodifference,itiscombination.Mostproblemsrequireustocombinethesetwo.e.g.Supposeyouwanttochoose5membersfromagroupof8towatering5differentgardens.Howmanywaystodothis?3.Permutation&combinationMultiplicationPrinciple:IfweneedNstepstodoajobandinthefirststepwehaveM1differentways,secondM2,thirdM3....,thenweapplymulti。

5、plicationprincipletocountthetotalwaysofdoingthisjob,i.e.N=M1*M2*M3....*MnAdditionPrinciple:IfwehaveNdifferentwaystodoajobandinthefirstwaywehaveM1differentways,secondM2,thirdM3...,thenweapplyadditionprincipletocountthetotalwaysofdoingthisjob,i.e.N=M1+M2+M3...+MnNotice:Inmultiplicationprinciplestepsareinterdependent,whileinadditionprincipleeachwaycanindependentlymakethejobdone.Generalmethodtosolvepermutation&combinationproblems:1.Understandwhatneedstobedone2.Decidewhethertotakestepsordivideintodif。

6、ferentways,orboth.Whentakingsteps,howmanystepsarethere;whendividingintodifferentways,howmanywaysintotal.4.Makesureoftherequirementsineachsteporway,permutationorcombination,andcalculatethenumberofarrangementsineachsteporeachway.5.Countthetotalwaysusingmultiplicationprincipleoradditionprinciple.3.1Giveprioritiestospecialelementsandplacese.g.Howmanydifferent5-digitoddnumberscanbeformedwhenchoosingfrom0,1,2,3,4,5andeachnumbercanbeusedonlyonce?(key:288)3.2BundlingStrategye.g.Thereare7studentstostandi。

7、nastraightline.IfstudentAandBshouldalwaysstandsidebyside,soshouldstudentDandG,howmanywaystolinethose7students?(key:480)Remembertomakepermutationbetweenbundlingelements3.3Slotstrategye.g.Thereisgoingtobe2dances,2crosstalks,and1soloinaparty.Ifthe2dancescannotbeperformedinarow,howmanydifferentprogramlistscanwemakeforthisparty?(key:72)Permutationfirstandthenpluginthespecialelements3.4Morethanonelineproblemse.g.Supposeyouaregoingtoarrange8studentsintotworowswithfourstudentsineachrow.StudentAandBmustb。

8、einthefirstrowandStudentCmustinthesecondrow.Howmanywaystoarrange?(key:5760)Turnitintoonestraightlineproblem3.5Mixtureproblemse.g.Supposeweneedtoput5differentballsinto4differentboxesandeachboxshouldcontainatleastoneball.Howmanywaystomakethisdone?(key:240)Firstchooseandthenorder3.6Plankstrategye.g.Anelementaryschoolhas10athletequotatobeassignedto7classes.Ifeveryclassshouldhaveatleastonequota,howmanywaysaretheretoassign?(key:84)Payattentiontothedifferencesbetween3.5and3.64.ProbabilityProbabilityisa。

9、wayofdescribinguncertaintyinnumericalterms.Probabilityexperiment(randomexperiment)Thesetofallpossibleoutcomesofarandomexperimentiscalledthesamplespace,andanyparticularsetofoutcomesiscalledanevent.P(E)=thenumberofoutcomesintheevent/thenumberofpossibleoutcomesintheexperimentGeneralfactsaboutprobability:IfaneventEiscertaintooccur,thenP(E)=1IfanevenEiscertainnottooccur,thenP(E)=0IfanevenEispossiblebutnotcertaintooccur,then0P(E)1TheprobabilitythataneventEwillnotoccurisequalto1-P(E)IfEisanevent,t。

10、hentheprobabilityofEisthesumoftheprobabilitiesofoutcomesinE.Thesumoftheprobabilitiesofallpossibleoutcomesofanexperimentis1.IfEandFaretwoeventsofanexperiment,weconsidertwoothereventsrelatedtoEandF.TheeventthatbothEandFoccur,thatis,alloutcomesinthesetTheeventthatEorF,orboth,occur,thatis,alloutcomesinthesetP(EorF)=P(E)+P(F)-P(bothEandF)P(EorF)=P(E)+p(F)ifEandFaremutuallyexclusiveP(EandF)=P(E)P(F)ifEandFareindependenttheprobabilityofoneeventoccurringktimesduringnindependentexperimentsP(E)=e。