會計學(xué)1ChCounting離散數(shù)學(xué)英文實用ThePigeonholePrinciple2PigeonholePrinciple:Letkandnbepositiveintegers(n>k),andwedividenballsamongkboxes,thenatleastoneboxcontains2balls13Pigeons,12Boxes第1頁/共33頁GeneralizedPigeonholePrincipleTheorem:Ifwehaven>kballs,kandnarepositiveintegers,andwedividethemamongkboxes,thenatleastoneboxcontainsn/kballsAssume10boxes(k=10).

Numberofballsn=11~20,atleastaboxhas2balls

Numberofballsn=21~30,atleastaboxhas3balls

Numberofballsn=31~40,atleastaboxhas4balls

…Example:Inagroupof1,000peoplethereareatleast3peoplewhohavetheirbirthdayonthesameday.Why?Thisisbecause1000/365=33第2頁/共33頁GeneralizedPigeonholePrincipleProofoftheGeneralizedPigeonholeTheorem:Bycontradiction:Assumenoneofthekboxescontainsn/kballs.Then,eachboxcontainsatmost

n/k–1balls.So,nk(n/k–1).Weknown/k<n/k+1(fromtheproperty:x<x+1).So,

nk(n/k–1)<k(n/k+1–1)=n.Or,n<n.Contradiction!

4第3頁/共33頁PigeonholePrincipleExampleWehave5possiblegrades:A,B,C,D,andF.Howmanystudentsdoweneedtohavetobesureatleast6studentsgetthesamegrade?Boxes=grades=5.Balls=students=n.

Trytofilltheboxesevenly:Ifwehave25students,thenwecanevenlyhave5A’s,5B’setc.Soifwehave26students,weneedaddastudenttoagradewhichthenhas6studentsFormally,n/5

6.So,n265第4頁/共33頁PigeonholePrincipleExampleForeverypositiveintegern,thereisanintegermthatisamultipleofn,andmconsistsofonlythedecimaldigitsof0’sand1’sToshowthis,weconstructmfromn+1numbers:1,11,111,1111,…,11…11(n+11’s)Divideeachbynandfindthetwonumbers(aandb)thatarecongruent(modn)(sameremainders)byPigeonholePrinciple(how?)Thenn|a–b(assumea>b).Definitionofcongruence.Letm=a–b.misamultipleofnandhasonly1s&0s6第5頁/共33頁PigeonholePrincipleExampleConsiderthecasen=3.Constructmfromn+1=4integersasfollows:1,11,111,1111Divideeachofthembyn(3)toget:1=30+1,11=33+2,111=337+0,1111=3370+1.Inthiscase:1mod3=1,1111mod3=1.Ifwesubtractthesetwointegerswegetanewintegerthatisdivisiblebyn:m=1111–1=1110(=3370),whichisamultipleof37第6頁/共33頁PigeonholePrincipleExampleAtapartyof6people,everytwopeopleareeitherenemiesorfriends.Showthatthereareatleast3mutualfriendsor3mutualenemiesattheparty8friendsfriendsfriendsenemiesenemiesenemiesOR第7頁/共33頁PigeonholePrincipleExampleProof:ConsiderpersonA:Acertainlyhaseither3friendsor3enemiesattheparty(PigeonholePrinciple:5peoplein2categories).AssumethreeofthemarefriendsofA.Ifthethreearemutualenemiesthenwehave3mutualenemiesandwearedone.Ifnot,thenatleast2arefriends,buttheyarealsoA’sfriends,whichmakesagroupofthreemutualfriends.Similarproofforthecaseofthreeenemies9第8頁/共33頁Workstation-ServerExampleWeconnect15workstationsto10servers.Oneservercanonlyletoneworkstationuseittocommunicateatatime.Werequirethatany10workstationscanusethe10serversatanytime10ServersWorkstations第9頁/共33頁Workstation-ServerExampleClaim:Theminimalnumberofcablesrequiredtoconnectbetweenworkstationsandserversis60Proof:Bycontradiction.Assumeitis59.ThenoneserverS’mustconnecttoatmost5workstations(59/10=5).Thismeansthattheremaining10workstationsarenotconnectedtoS’.Sothese10workstationscanonlycommunicatetoatmost9servers.Itisacontradiction!11第10頁/共33頁Permutationsr-permutation:Anorderedarrangementofrelementsofasetofndistinctelements,rnExample:S={1,2,3,4}:2134isapermutationofS

321isa3-permutationofS

32isa2-permutationofSPermutationTheorem:Thenumberofr-permutationsofnobjectsis:

P(n,r)=n(n–1)(n–2)...(n–r+1)=

Firstobjectcanbechoseninnways,secondin(n–1)ways,...,r-thobjectinn–r+1ways.UseproductruletogettheaboveresultWhenr=n,P(n,n)=n(n–1)(n–2)...1=n!12第11頁/共33頁PermutationExamplesAmailmanneedstobring8packagesto8cities.Hestartsatcity1.Howmanywaysaretheretovisittheremaining7cities?Picksecondcityamong7,3rdamong6,4thamong5,... Answer:7!Howmanypermutationsoftheletters“a,b,c,d,e,f,g,h”contain“abc”asablock.Rename“abc”toB.Nowwehave:howmanypermutationsofB,d,e,f,g,harethere? Answer:6!13第12頁/共33頁Combinationsr-combinationC(n,r):Anunorderedselectionofrelements(orsubsetofsizer)fromasetofnelements.Example:S={1,2,3,4}.Then{3,2,1}={1,2,3}isa3-combination.{1,3,4}isanotherand{1,4}isa2-combinationCombinationTheorem:Thetotalnumberofr-combinationsofasetofsizen,0rn,isgivenby14第13頁/共33頁CombinationsProofofcombinationtheorem:P(n,r)countsthetotalnumberoforderedarrangements.However,thedifferenceofC(n,r)isthatitisonlyinterestedinunorderedarrangementshere.Foreverysubsetofrelementsonecanexactlyconstructr!orderedarrangementsinthepermutation,everyoneofwhichisincludedinP(n,r).Theser!arrangementsshouldbeconsideredthesameinC(n,r).WethusneedtodivideP(n,r)byr!15第14頁/共33頁CombinationsNotethatC(n,r)=C(n,n–r).It’ssymmetric

ThisisbecauseAlso,

16第15頁/共33頁CombinationExampleHowmanypokerhandsoffivecardscanbedealtfromastandarddeckof52cards?Also,howmanywaysaretheretoselect47cardsfromadeckof52cards?Solution:Sincetheorderinwhichthecardsaredealtdoesnotmatter,thenumberoffivecardhandsis:Thedifferentwaystoselect47cardsfrom52is

第16頁/共33頁CombinationExamplesHowmanybit-stringsoflength8containfour1’sWeneedtoformacommitteeof7people,3frommathand4fromcomputersciencetodevelopadiscretemathcourse.Thereare9mathcandidatesand11CScandidatesTTwoseparateproblemsthatneedtobecombinedusingtheproductrule.C(9,3)possibilitiesformathandC(11,4)possibilitiesforCS:Total=C(9,3)C(11,4)=27,72018第17頁/共33頁CombinationExampleHowmanypathsaretherefrom(0,0)to(m,n)withrightandupmovesastheonlyallowedmoves?Weneedexactlynupmovesandmrightmovestogetto(m,n).Let“up”bea“1”andrightbea“0”.Thusweneedtocountthetotalnumberofbit-stringswithexactlym1’sandn0’s.19Onepossiblepath(m,n)(0,0)Thisisequivalenttoselectn(orm)elementsfromasetofn+melements:C(n+m,n)011100001010(7,5)第18頁/共33頁BinomialCoefficientsBinomialTheorem(n,j0andjn)

(Notethat )When(x+y)nisinitsexpandedform,thecoefficientoftermxn-jyjis20第19頁/共33頁BinomialCoefficientExamplesWhatisthecoefficientofx12y13intheexpansionof(x+y)25?Weneedtopick12x’sfrom25terms:C(25,12)=C(25,13)=25!/(12!13!)Whatisthecoefficientofx12y13in(2x–3y)25? Firstreplacea=2xandb=-3y.Thecoefficientofa12b13in(a+b)25isC(25,13).thusitfollowsthat:C(25,13)a12b13=C(25,13)212x12(-3)13y13.Sothecoefficientofx12y13is

C(25,13)212(-3)13=-(25!/(12!13!))21231321第20頁/共33頁BinomialCoefficientExampleWhatarecoefficientsforxkintheexpansionof(x+1/x)100intermsofk,wherekisaninteger?Atypicaltermforjis (i)Letk=100–2j.Thenj=(100–k)/2Asjrunsfrom0to100,krunsfrom100to-100indecrementsof2(100,98,…,0,-2,…,-100)So,(i)isequivalentto22第21頁/共33頁BinomialCoefficientCorollariesLetnbenonnegativeinteger.ThenLetx=1andy=1intheBinomialTheoremLetnbenonnegativeinteger.Then

Letx=1andy=2in(i)andletx=1andy=-1in(ii)intheBinomialTheorem23(i)and(ii)第22頁/共33頁24Pascal’sTriangle/Identity第23頁/共33頁Pascal’sIdentityPascal’sIdentity,wheren,k>0andkn:Proof:DenoteT={a1,a2,…,ak+1},andS=T–{aj}whereajissomearbitraryelementinT.ThenumberofsubsetsofkelementsofTisC(n+1,k).ThismustbeequaltothenumberofwaystopickkelementsfromTthatdonotcontainaj(=pickingkelementsfromS,orC(n,k)),plusthenumberofwaystopickkelementsthatalwayscontainaj(=pickingk–1elementsfromS,orC(n,k–1)).HenceC(n+1,k)=C(n,k)+C(n,k–1)25第24頁/共33頁Pascal’sIdentityPascal’sIdentity,wheren,k>0andkn:Analgebraicproof

26第25頁/共33頁PermutationwithRepetitionThenumberofr-permutationsofasetofnobjectswithrepetitionallowedisnrExample:Howmany3-permutationscanbeformedfromS={1,2,3,4}withrepetition?

Firstobjectcanbechosenin4ways.Thesecondobjectcanbechosenalsoin4waysbecausetheelementscanbeusedrepeatedly.So,444=43Example:HowmanystringsoflengthrcanbeformedfromtheEnglishalphabet?

Thisis262626…26(rofthemmultipliedtogether)=26r,becauseeachpositioncanrepeatedlyselectanyofthe26Englishletters第26頁/共33頁CombinationwithRepetitionThenumberofr-combinationsofasetofnobjectswithrepetitionallowedis

Example:Howmany2-combinationswithrepetitionfrom{1,2,3,4}?

Theyare{1,1},{1,2},{1,3},{1,4},{2,2},{2,3},{2,4},{3,3},{3,4},{4,4}.

ThereareC(4+2–1,2)=C(5,2)=10第27頁/共33頁CombinationwithRepetitionExample:Howmanywaysaretheretoselectfivebillsfromacashboxconta