月日旅游与酒店管理学院酒店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※TreeDiagrams

Example18Howmanybitstringsoflengthfourdo

nothavetwoconsecutive1s?

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,then

a1=an,a2=an-1,

a3=an-2,…Thm.4of§4.3

放不放

放不放

放不放空集合及

只有1個元素的集合Ch5-13§5.2ThePigeonholePrinciple(鴿籠原理)Theorem1(ThePigeonholePrinciple)If

k+1ormoreobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingtwoormoreoftheobjects.ProofSupposethatnoneofthe

kboxescontainsmorethan

oneobject.Thenthetotalnumberofobjectswouldbeatmostk.Thisisacontradiction.Example1.Amongany367people,theremustbeatleasttwowiththesamebirthday,becausethereareonly366possiblebirthdays.Ch5-14Example2Inanygroupof27Englishwords,theremustbeatleasttwothatbeginwiththesameletter.Example3Howmanystudentsmustbeinaclasstoguaranteethatatleasttwostudentsreceivethesamescoreonthefinalexam?(0~100points)Sol:

102.(101+1)Theorem2.(Thegeneralizedpigeonholeprinciple)IfN

objectsareplacedintokboxes,thenthereisatleastoneboxcontainingatleastobjects.e.g.21objects,10boxestheremustbeonebox

containingatleastobjects.Ch5-15Example5Among100peoplethereareatleastwhowereborninthesamemonth.(100objects,12

boxes)Ch5-16Example10Duringamonthwith30daysabaseballteamplaysatleast1gameaday,butnomorethan45games.Showthattheremustbeaperiodofsomenumberofconsecutivedaysduringwhichtheteammustplayexactly14games.存在一段時間的game數和=14(跳過)Ch5-17Sol:Letaj

bethenumberofgamesplayedonorbeforethejthdayofthemonth.(第1天～第j天的比賽數和)ThenisanincreasingsequenceofdistinctintegerswithMoreover,isalsoanincreasingsequenceofdistinctintegerswithThereare60positiveintegersbetween1and59.Hence,suchthat(跳過)Ch5-18Def.

Supposethatisasequenceofnumbers.Asubsequenceofthissequenceisasequenceof

theformwhere

e.g.sequence:8,11,9,1,4,6,12,10,5,7subsequence:8,9,12()9,11,4,6()Def.Asequenceiscalledincreasing

(遞增)ifAsequenceiscalled

decreasing

(遞減)ifAsequenceiscalledstrictlyincreasing

(嚴格遞增)

ifAsequenceiscalled

strictlydecreasing

(嚴格遞減)

ifCh5-19Theorem3.Everysequenceofn2+1

distinctrealnumberscontainsasubsequenceoflengthn+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.3镜P奇ermu标tati妹ons(排列)an孤dCo云mbin患atio惕ns(組合)Def览.Aperm帐utat障ionofa繁set骡of强dist荣inct检obj摘ects数is德ano蓄rder恰eda挺rran旬geme台nto异fth共ese鸽obje瓜cts.废An遗orde途red野arra柏ngem燥ent坐ofrelem投ents员of宴ase帐tis淋cal避led知anr-per悼muta伤tion.Exam鸟ple侍2.LetS={1,赖2,3挣}.The裕ar衬ran泰gem震ent3,1,尚2is吊ap蛾erm锯uta胁tio敏no绪fS.燃The认ar混ran辛gem凶ent3,2isa养2-p叫ermu丘tati纯ono醋fS.The亲ore销m1丧.The谷nu催mbe仙ro捎fr-pe墙rmu花tat傅ion好of孝a斧set经wi完thndist陷inct冷ele峡ment袭sis位置：1狠2羊3亡…狸r□□汇□…□放法：…Ch5-21Exam信ple钳4.How戏many锐dif盼fere翻ntw染ays译are闸ther知eto易sel决ectafi胀rst-苦priz堡ewi棕nner司(第一名),送as朵eco确nd-傻pri铲ze隔win久ner奶,a咏nd芒a舱th沟ird约-pr偏ize竿wi槽nne惕rf弊rom伍10汗0d扇iff牌ere思nt皮peo垒ple上wh闸oh役ave龟ent膜ere穴da夫co抹nte呜st删?Sol逝:Exam坚ple弄6.Supp故ose兰that建as研ales殿woma仗nha泉sto挺vis辨it8di拨ffer柿ent铁citi养es.健She郊must扬beg淘inh政ert锹rip痛ina疫spe果cifi董ed厦city爱,bu扶tsh兄eca掌nvi义sit赵the充othe甩rci笨ties株in传any锻orde司rsh屑e啊wish巴es.纪How务many势pos狸sibl湖eor桶ders丈can啦the始sal恢eswo情man垃use今whe坏nvi郑siti彻ngt宽hese卖cit答ies欺?Sol衰:Ch5-22Def.Anr-co瓣mbi忍nat泳ionofe朱leme夫nts缴ofa掠set才is北anuno代rde喂red违se台lec扎tio圆no络frelem咽ents秒fro战mth汉ese巴t.Exa之mpl把e9LetSbe顺the只se鸭t{1,肢2,3骂,4}.钳The赠n{1,旬3,延4}is狂a3-co千mbi圆nat趴ion蝇fr拥omS.The幻玉ore驴m2The照nu胜mbe袜ro考fr-co授mbi卡nat最ion俘so漫fa味se魔t岗wit太hnele贝men裹ts,书wh古erenis煎ap窄osi托tiv给ei片nte修ger归an感drisan悄int粪ege破rw席ith特,摊eq萌ual贯spf:稱為binomialcoefficientCh5-23Exam徐ple住10.We仰see壮th仗atC(4,2驰)=6,sin醒ce宏the2-co伶mbin侄atio傲nso旅f{a,b,c,d}are且the斗six局subs臣ets{a,b},全{a,c},聋{a,d},{b,c},{b,d}and{c,d}Coro吼llar呈y2.Letnandrbe岁non贡neg筑ati抢ve布int夹ege概rs边wit绳hrn.The川nC(n,r)=C(n,n-r)pf:FromThm霞2.組合意仰義：選r個拿走,相當於竞是選n-r個留下.Ch5体-24Exam厦ple愉12.How炎many筑way蜘sar芒eth妨ere必tos昨elec币t5围play腊ers隐from裹a1窝0-me岩mber羽ten居nis旷team讽to城make五at遗rip继toa凭mat额cha君tan奔othe劣rsc仰hool哥?Sol:C(10贩,5)红=25捐2Exam挤ple辈15.Supp骨ose疏ther克ear搁e9惜facu复lty辱memb稍ers右int港hem立ath龙depa烤rtme贱nta衬nd1招1in挪the比com绪pute桃rsc确ienc泪ede卡part晴ment匪.Ho给wma晃nyw外ays走are苹ther拿eto铃sel茅ect嚼a评co气mmit谎tee宫ift佳hec狐ommi谨ttee准is篇toc葛onsi亩sto薯f3谣facu营lty示memb凑ers执from替the蒙mat逼hde疤part挪ment斥and据4f炊rom咐the配comp醋uter隙sci启ence贺dep协artm严ent?Sol:Exer锦cise私:3,览11,再13恳,2作1,内33,乘34慕.Ch5-25§5.乌4型B己ino环mia屠lC性oef形fic礼ien萄ts泛(二項式係趋數)Exam荷ple筝1.要產生xy2項時，昼需從三個史括號中選位兩個括號懒提供y，剩下一醒個則提供x(注意：同研一個括號筋中的x跟y不可能相劝乘)∴共有徐種笨不同來占源的xy2∴xy2的係數=Theo椒rem螺1.(Th下eB固ino效mia荒lT君heo错rem酱,二項式绣定理)Letx,ybev毛aria渐bles剧,an尤dle挠tnbea携pos刃itiv认ein投tege激r,t缩慧henCh5及-26Exam凯ple橡4.What折is邪the氏coef沃fici谷ent季ofx12y13inthe互expa反nsio滑nof后?Sol泥:∴Cor竿1.Letnbea骗pos移itiv拔ein慰tege拣r.T这henpf:By驾Thm踩1,目l魄etx=y=1Cor堂2.Letnbea板pos窑itiv铁ein的tege扭r.贸Thenpf:by绵Thm毙1.(1-1)n=0Ch5-27Theo达rem粮2.(Pa炒sca支l’s肤id姑ent视ity索)Letnandkbe记pos哑iti派ve纤int