月日旅游与酒店管理学院酒店Q

DiscreteMathematics

Chapter5Counting大葉大學資訊工程系黃鈴玲Ch5-2Acountingproblem:(Example15)Eachuseronacomputersystemhasapassword,whichissixtoeightcharacterslong,whereeachcharactersisanuppercaseletteroradigit.Eachpasswordmustcontainatleastonedigit.Howmanypossiblepasswordsarethere?Thissectionintroducesavarietyofothercountingproblemsthebasictechniquesofcounting.§5.1TheBasicsofcountingCh5-3BasiccountingprinciplesThesumrule:Ifafirsttaskcanbedoneinn1waysandasecondtaskinn2ways,andifthesetaskscannotbedoneatthesametime.thentherearen1+n2

waystodoeithertask.Example11Supposethateitheramemberoffacultyorastudentischosenasarepresentativetoauniversitycommittee.Howmanydifferentchoicesarethereforthisrepresentativeifthereare37membersofthefacultyand83students?n1n2n1+n2waysCh5-4Example12Astudentcanchooseacomputerprojectfromoneofthreelists.Thethreelistscontain23,15and19possibleprojectsrespectively.Howmanypossibleprojectsaretheretochoosefrom?

Sol:

23+15+19=57projects.Theproductrule:Supposethataprocedurecanbebrokendownintotwotasks.Iftherearen1waystodothefirsttaskandn2waystodothesecondtaskafterthefirsttaskhasbeendone,thentherearen1n2waystodotheprocedure.n1n2n1×n2waysCh5-5Example2Thechairofanauditorium(大禮堂)is

tobelabeledwithaletterandapositiveinteger

notexceeding100.Whatisthelargestnumberof

chairsthatcanbelabeleddifferently?Sol:

26×100=2600waystolabelchairs.

letter

Example4Howmanydifferentbitstringsarethereoflengthseven?Sol:

1

2

3

4

5

6

7□□□□□□□↑↑↑↑↑↑↑

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-onefunctionsaretherefromasetwithm

elementstoonewithnelement?

(mn)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,8

P6=366-266

P7=367-267

P8=368-268

∴P6

+P7

+P8

=366+367+368-

266

-267-268種Ch5-9Example14InaversionofBasic,thenameofavariableisastringofoneortwoalphanumericcharacters,whereuppercaseandlowercaselettersarenotdistinguished.Moreover,avariablenamemustbeginwithaletterandmustbedifferentfromthefivestringsoftwocharactersthatarereservedforprogramminguse.HowmanydifferentvariablenamesarethereinthisversionofBasic?Sol:

LetVi

bethenumberofvariablenamesoflengthi.

V1=26

V2=26．36–5 ∴26+26．36–5differentnames.Ch5-10※TheInclusion-ExclusionPrinciple(排容原理)ABExample17

Howmanybitstringsoflengtheighteitherstartwitha1bitorendwiththetwobits00?Sol:

１２３４５６７８□□□□□□□□↑↑......①1

0,10,1→共27種②............00→共26種③1...........00→共25種27+26-25種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,…Thm.4of§§4.3放不放放不放放不放空集合及及

只有有1個元素的的集合Ch5-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,10boxestheremustbeoneboxcontainingatleastobjects.Ch5-15Example5Among100peoplethereareatleastwhowereborninthesamemonth.(100objects,12boxes)Ch5-16Example10Duringamonthwith30daysabaseballteamplaysatleast1gameaday,butnomorethan45games.Showthattheremustbeaperiodofsomenumberofconsecutivedaysduringwhichtheteammustplayexactly14games.存在一段段時間的的game數和=14(跳過)Ch5-17Sol:Letajbethenumberofgamesplayedonorbeforethejthdayofthemonth.(第1天～第j天的比賽賽數和)ThenisanincreasingsequenceofdistinctintegerswithMoreover,isalsoanincreasingsequenceofdistinctintegerswithThereare60positiveintegersbetween1and59.Hence,suchthat(跳過)Ch5-18Def.Supposethatisasequenceofnumbers.Asubsequenceofthissequenceisasequenceoftheformwheree.g.sequence:8,11,9,1,4,6,12,10,5,7subsequence:8,9,12()9,11,4,6()Def.Asequenceiscalledincreasing(遞增)ifAsequenceiscalleddecreasing(遞減)ifAsequenceiscalledstrictlyincreasing(嚴格遞增增)ifAsequenceiscalledstrictlydecreasing(嚴格遞減減)ifCh5-19Theorem3.Everysequenceofn2+1distinctrealnumberscontainsasubsequenceoflengthn+1thatiseitherstrictlyincreasingorstrictlydecreasing.Example12.Thesequence8,11,9,1,4,6,12,10,5,7contains10=32+1terms(i.e.,n=3).Thereisastrictlyincreasingsubsequenceoflengthfour,namely,1,4,5,7.Thereisalsoadecreasingsubsequenceoflength4,namely,11,9,6,5.Exercise21Constructasequenceof16positiveintegersthathasnoincreasingordecreasingsubsequenceof5terms.Sol:Exercise:5,13,15,31(跳過)Ch5-20§5.3Permutations(排列)andCombinations(組合)Def.Apermutationofasetofdistinctobjectsisanorderedarrangementoftheseobjects.Anorderedarrangementofrelementsofasetiscalledanr-permutation.Example2.LetS={1,2,3}.Thearrangement3,1,2isapermutationofS.Thearrangement3,2isa2-permutationofS.Theorem1.Thenumberofr-permutationofasetwithndistinctelementsis位置：123……r□□□□□…□□放法：…Ch5-21Example4.Howmanydifferentwaysaretheretoselectafirst-prizewinner(第一名),asecond-prizewinner,andathird-prizewinnerfrom100differentpeoplewhohaveenteredacontest?Sol:Example6.Supposethatasaleswomanhastovisit8differentcities.Shemustbeginhertripinaspecifiedcity,butshecanvisittheothercitiesinanyordershewishes.Howmanypossibleorderscanthesaleswomanusewhenvisitingthesecities?Sol:Ch5-22Def.Anr-combinationofelementsofasetisanunorderedselectionofrelementsfromtheset.Example9LetSbetheset{1,2,3,4}.Then{1,3,4}isa3-combinationfromS.Theorem2Thenumberofr-combinationsofasetwithnelements,wherenisapositiveintegerandrisanintegerwith,equalspf:稱為binomialcoefficientCh5-23Example10.WeseethatC(4,2)=6,sincethe2-combinationsof{a,b,c,d}arethesixsubsets{a,b},{a,c},{a,d},{b,c},{b,d}and{c,d}Corollary2.Letnandrbenonnegativeintegerswithrn.ThenC(n,r)=C(n,n-r)pf:FromThm2.組合意義義：選r個拿走,相當於是是選n-r個留下.Ch5-24Example12.Howmanywaysaretheretoselect5playersfroma10-membertennisteamtomakeatriptoamatchatanotherschool?Sol:C(10,5)=252Example15.Supposethereare9facultymembersinthemathdepartmentand11inthecomputersciencedepartment.Howmanywaysaretheretoselectacommitteeifthecommitteeistoconsistof3facultymembersfromthemathdepartmentand4fromthecomputersciencedepartment?Sol:Exercise:3,11,13,21,33,34.Ch5-25§5.4BinomialCoefficients(二項式係係數)Example1.要產生xy2項時，需需從從三個括括號中選選兩個括括號提供供y，剩下一一個則提提供x(注意：同同一個括括號中的的x跟y不可能相相乘)∴共有種種不不同來源源的xy2∴xy2的係數=Theorem1.(TheBinomialTheorem,二項式定定理)Letx,ybevariables,andletnbeapositiveinteger,thenCh5-26Example4.What