12月3日旅游与酒店管理学院酒店Q0441。。。

DiscreteMathematicsChapter5Counting大葉大學資訊工程系黃鈴玲酒店设计Acountingproblem:(Example15)Eachuseronacomputersystemhasapassword,whichissixtoeightcharacterslong,whereeachcharactersisanuppercaseletteroradigit.Eachpasswordmustcontainatleastonedigit.Howmanypossiblepasswordsarethere?Thissectionintroducesavarietyofothercountingproblemsthebasictechniquesofcounting.§5.1TheBasicsofcountingCh5-3BasiccountingprinciplesThesumrule:Ifafirsttaskcanbedoneinn1waysandasecondtaskinn2ways,andifthesetaskscannotbedoneatthesametime.thentherearen1+n2waystodoeithertask.Example11Supposethateitheramemberoffacultyorastudentischosenasarepresentativetoauniversitycommittee.Howmanydifferentchoicesarethereforthisrepresentativeifthereare37membersofthefacultyand83students?n1n2n1+n2waysCh5-4Example12Astudentcanchooseacomputerprojectfromoneofthreelists.Thethreelistscontain23,15and19possibleprojectsrespectively.Howmanypossibleprojectsaretheretochoosefrom?Sol:23+15+19=57projects.Theproductrule:Supposethataprocedurecanbebrokendownintotwotasks.Iftherearen1waystodothefirsttaskandn2waystodothesecondtaskafterthefirsttaskhasbeendone,thentherearen1n2waystodotheprocedure.n1n2n1×n2waysCh5-5Example2Thechairofanauditorium(大禮堂)istobelabeledwithaletterandapositiveintegernotexceeding100.Whatisthelargestnumberofchairsthatcanbelabeleddifferently?Sol:26×100=2600waystolabelchairs.letterΝxx1001Example4Howmanydifferentbitstringsarethereoflengthseven?Sol:1234567□□□□□□□↑↑↑↑↑↑↑0,10,10,1......0,1→27種Ch5-6Example5Howmanydifferentlicenseplates(車牌)areavailableifeachplatecontainsasequenceof3lettersfollowedby3digits?Sol:□□□□□□→263．103letterdigitExample6Howmanyfunctionsaretherefromasetwithmelementstoonewithnelements?Sol:f(a1)=?可以是b1～bn,共n種f(a2)=?可以是b1～bn,共n種：f(am)=?可以是b1～bn,共n種∴nma1a2．．．amb1b2．．．bnfCh5-7Example7Howmanyone-to-onefunctionsaretherefromasetwithmelementstoonewithnelement?(mn)Sol:f(a1)=?可以是b1～bn,共n種f(a2)=?可以是b1～bn,但不能=f(a1),共n-1種f(a3)=?可以是b1～bn,但不能=f(a1),也不能=f(a2),共n-2種：：f(am)=?不可=f(a1),f(a2),...,f(am-1),故共n-(m-1)種∴共n．(n-1)．(n-2)．...．(n-m+1)種1-1function#Ch5-8Example15Eachuseronacomputersystemhasapasswordwhichis6to8characterslong,whereeachcharacterisanuppercaseletteroradigit.Eachpasswordmustcontainatleastonedigit.Howmanypossiblepasswordsarethere?Sol:Pi:#ofpossiblepasswordsoflengthi,i=6,7,8P6=366-266P7=367-267P8=368-268∴P6+P7+P8=366+367+368-266-267-268種Ch5-9Example14InaversionofBasic,thenameofavariableisastringofoneortwoalphanumericcharacters,whereuppercaseandlowercaselettersarenotdistinguished.Moreover,avariablenamemustbeginwithaletterandmustbedifferentfromthefivestringsoftwocharactersthatarereservedforprogramminguse.HowmanydifferentvariablenamesarethereinthisversionofBasic?Sol:LetVibethenumberofvariablenamesoflengthi.V1=26V2=26．36–5∴26+26．36–5differentnames.Ch5-10※TheInclusion-ExclusionPrinciple(排容原理)ABExample17Howmanybitstringsoflengtheighteitherstartwitha1bitorendwiththetwobits00?Sol:１２３４５６７８□□□□□□□□↑↑......①10,10,1→共27種②............00→共26種③1...........00→共25種27+26-25種BABABA-=Ch5-1101bit1※TreeDiagramsExample18Howmanybitstringsoflengthfourdonothavetwoconsecutive1s?Sol:Exercise:11,17,23,27,38,39,47,5300000111001(0000)(0001)(0010)(0100)(0101)(1000)(1001)(1010)∴8bitstrings00110bit3Ch5-12Ex38.Howmanysubsetsofasetwith100elementshavemorethanoneelement?Sol:Ex39.Apalindrome(迴文)isastringwhosereversalisidenticaltothestring.Howmanybitstringsoflengthnarepalindromes?(abcdcba是迴文,abcd不是)Sol:Ifa1a2...anisapalindrome,thena1=an,a2=an-1,a3=an-2,…10122100...9810099100100100)1(100-==Thm.4of§4.310021,...,,)2(aaa1012□,...,□,□:subset100-放不放放不放放不放空集合及只有1個元素的集合string.種22nCh5-13§5.2ThePigeonholePrinciple(鴿籠原理)Theorem1(ThePigeonholePrinciple)Ifk+1ormoreobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingtwoormoreoftheobjects.ProofSupposethatnoneofthekboxescontainsmorethanoneobject.Thenthetotalnumberofobjectswouldbeatmostk.Thisisacontradiction.Example1.Amongany367people,theremustbeatleasttwowiththesamebirthday,becausethereareonly366possiblebirthdays.Ch5-14Example2Inanygroupof27Englishwords,theremustbeatleasttwothatbeginwiththesameletter.Example3Howmanystudentsmustbeinaclasstoguaranteethatatleasttwostudentsreceivethesamescoreonthefinalexam?(0~100points)Sol:102.(101+1)Theorem2.(Thegeneralizedpigeonholeprinciple)IfNobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingatleastobjects.e.g.21objects,10boxestheremustbeoneboxcontainingatleastobjects.kN31021=Ch5-15Example5Among100peoplethereareatleastwhowereborninthesamemonth.(100objects,12boxes)912100=Ch5-16Example10Duringamonthwith30daysabaseballteamplaysatleast1gameaday,butnomorethan45games.Showthattheremustbeaperiodofsomenumberofconsecutivedaysduringwhichtheteammustplayexactly14games.day12345...1530#ofgame321245sum存在一段時間的game數和=14(跳過)Ch5-17Sol:Letajbethenumberofgamesplayedonorbeforethejthdayofthemonth.(第1天～第j天的比賽數和)ThenisanincreasingsequenceofdistinctintegerswithMoreover,isalsoanincreasingsequenceofdistinctintegerswithThereare60positivei