Permutation-and-Combination

NationalJuniorCollegeMathematicsDepartment20102010/SH1/H2Maths/PermutationsandCombinations1NationalJuniorCollege2010H2Mathematics(SeniorHigh1)PermutationsandCombinations(LectureNotes)PermutationsandCombinationsObjectivesAttheendofthistopic,studentsshouldbeabletousetheadditionandmultiplicationprinciplesforcounting.distinguishbetweenpermutationsandcombinations.understandthatnrPisthenumberofpermutationsofrobjectstakenfromndistinctobjects;andthatinthespecialcasewhenr=n,thenumberofpermutationsofnobjectsarrangedinastraightlineisn!usetheformula!!nrnPnr.understandthatnr(ornrC)isthenumberofcombinationsofrobjectsfromndistinctobjects.usetheformula!!!nnrnrr.interpretandusetherelation!nrnPrr.findthepermutationsofnobjects,notalldistinct.findthepermutationsofndistinctobjectsarrangedinacircle.usenrP,nrand!rtosolvecountingproblems,includingcasesinvolvingrepetitionsandrestrictions.§1IntroductionIfyouwentonashoppingspreeandboughttwopairsofjeans,threeshirts,andtwopairsofshoes,howmanynewoutfits(consistingofanewpairofjeans,anewshirt,andanewpairofshoes)wouldyouhave?Whataretheassumptionsyoumade?TheJackpotprizefortheLunarNewYearTOTOistenmilliondollars.AsaMathematicsstudent,howmany6numberticketsmustbeboughtinordertohittheJackpot?Howmanynumbersarethere?Howmuchisoneticket?Whatisyouradvice?Howdoessystem-7work?Theanswerstoquestionslikethesecanbeobtainedbylistingallthepossibilitiesorbyusingthesecountingtechniques:thefundamentalprinciplesofcounting,permutationsandcombinations.Collectively,thesetechniquesareknownascombinatorics.1.1TheFactorialNotation(!)n!=nnn)1)(2...(321,wherenZ+and0!=1(ByDefinition)NationalJuniorCollegeMathematicsDepartment20102010/SH1/H2Maths/PermutationsandCombinations2§2FundamentalPrinciplesofCounting2.1AdditionPrincipleIfthereismorethan1optioninperformingaparticulartask,thenthenumberofwaysofperformingthetaskisequaltothesumofthenumberofdifferentoptions.Thedifferentoptionscannotoccuratthesametime.Example2.1AnNJCstudenthastheoptionoftaking3differentdirectbusesortakingataxitocollege.Howmanywayscanshegotoschool?Solution:Bus3waysModeoftransportTotalnumberofways=3+1=4Taxi1way2.2MultiplicationPrincipleIfonetaskcanbeperformedinrways,andfollowingthis,asecondtaskcanbeperformedinsways,thenthenumberofwaysofperformingthe2tasksinsuccessionis(rs)ways.Appliedwhen2ormoretaskshastobecompletedinsuccession.Canbeextendedto3tasksormore.Example2.2AnNJCstudenthastheoptionoftakingeitherabus,taxiorwalktocollege.Forhisreturnjourney,hehastheadditionaloptionofwaitingforhisdadtocomefetchhiminacar.Howmanydifferentwayscanhetraveltocollegeandbackhome?Solution:3ways4waysTotalnumberofways=1243Example2.3InhowmanywayscanAmy,BernardandCarolarrangethemselvesinaqueue?Solution:*Strategy:Wewillthinkofthisproblemasfillingspaces.321Totalnumberofways=6123(Alternatively,dobyexhaustion!)HomeSchoolHomeNationalJuniorCollegeMathematicsDepartment20102010/SH1/H2Maths/PermutationsandCombinations3§3PermutationsApermutationisanorderedarrangementofobjects.Inpermutations,ordermatters.ie.the3-letterarrangementofABCandACBareconsidered2differentarrangements.Someotherexampleswhereordercounts:1.Arranging3booksonashelf.2.Sitting5peopleinarow.3.Forming3digitnumbersusingthenumbers1,2,3,4,5.3.1Permutationofndistinctobjects(inarow)Givenndistinctobjects,thenumberofwaysofarrangingallthesenobjectscanbededucedas:……Hence,numberofways=12......3.2.1!nnnnNote:Thismethodoffilling“oneplaceatatime”takesorderintoconsideration.Example2.3isanexampleofsuchapermutation.Example3.1Inhowmanywayscanfourdifferentbooksbearrangedonashelf?Solution:Theorder(ie.whichbookcomesfirst)matters:4321No.ofways=4!=243.2PermutationswithandwithoutrepetitionsExample3.2Howmanypossibilitiesaretherein4-Dlotteryforecastif(i)norepetitionofthenumbersisallowed?(ii)repetitionisallowed?Solution:(i)10987Numberofpossibilities=504078910(ii)10101010Numberofpossibilities=10000104Noticeinthisexample,wedon’tuseallthe“distinctobjects”!nn-1n-23211stslotnthslotNationalJuniorCollegeMathematicsDepartment20102010/SH1/H2Maths/PermutationsandCombinations43.3PermutationofrobjectstakenfromndistinctobjectsGivenndistinctobjects,thenumberofwaysarrangingroftheseobjects(0rn)canbededucedas:……Hence,numberofways=nrPwhere12....3211....3.2.112....3211....3.2.1!!nrPnnnnrnrnrnrnrnnnnrnrnrnrnrnnrInparticular,whenr=n,!!!0!!nnnnPnnn(Recallthat0!=1)QuickQuiz:Whatis0nP?Answer:0nP!1(0)!nnExample3.3Howmany6-lettercodewords(norepetitionofletters)canbeformedfromthelettersoftheword“SINGAPORE”?Solution:Noticethatnolettersarerepeated.Thereare9distinctletters.Numberof6-lettercodewords969!60480(96)!PAlternatively,987654Numberof6-lettercodewords=9x8x7x6x5x4=60480nn-1n-2n-r+3n-r+2n-r+11stslotrthslotNationalJuniorCollegeMathematicsDepartment20102010/SH1/H2Maths/PermutationsandCombinations53.4Permutationsinvolvingnon-distinct/identicalobjectsThenumberofpermutationsofnobjectswithk1objectsofthefirstkind,k2objectsofthesecondkind,………,krobj