chapter 6advanced counting

《chapter 6advanced counting》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter6AdvancedCounting6.1RecurrenceRelationsRecurrenceRelationsDefinition:Anequationthatexpressestheelementanofthesequence{an}intermsofoneormoreprevioustermsofthesequencea0,...,an-1.Asequenceisasolutionoftherecurrencerelationifitstermssatisfytherecurrence

2、relation.Example:Considertherecurrencerelationan=2a(n-1)–a(n-2),ninNConsiderthesequence:an=3n.Isitasolution?2x3x(n-1)-3x(n-2)=3nYES!(a0=0,a1=3,a2=6,...)Considerthesequencean=5.Isitasolution?2x5–5=5YES!(a0=5,a1=5,...)weseethattosequencescanbeasolutionofthes

3、amerecurrencerelationsincetheinitialconditionsarealsoveryimportant.Theinitialconditionsplustherecurrencerelationprovideauniquerecursivedefinitionofasequence.ModellingLet’ssayyouput$1dollarinthebanknow.Howmuchwillyoureceivein50yearsiftheinterestis4%?B(0)=1.B(

4、n)=B(n-1)+0.04xB(n-1)(addtheinterest).=1.04xB(n-1).=1.04^2B(n-2)=1.04^50B(0)=$7.1TowerofHanoiHowmanymovesdoesittaketosolvetheHanoipuzzle?LetHnbethenumberofmovestosolveaproblemwithndisks.-Wefirstmovethetopn-1diskstopeg2inH(n-1)moves.-Wethenmovethelargestdiskt

5、opeg3in1move.-Wethenmovethen-1disksontopofthelargestdiskinanotherH(n-1)moves:Total:Hn=2xH(n-1)+1-BasisStep:1disk=1move:H(1)=1.-Hn=2(2H(n-2)+1)+1=2^2H(n-2)+2^1+1....=2^(n-1)H1+2^(n-2)+2^(n-3)+...+2+1=2^n-1(bysumsofgeometricseries3.1).ExamplesHowmanybit-strin

6、gsoflengthnwithnoconsecutive0’s?anisnumberofbit-stringswithno2consecutive0’sinit.Howcanwegenerateabit-stringoflengthnfrombit-stringsoflengthn-1?Validbit-stringsfallinto2classes,onesthatendwitha“0”andonesthatendwitha“1”.Onesthatendina“1”couldbegeneratedbyadd

7、ingaonetoavalidbit-stringofanykind:a(n-1)ways.Onesthatendwitha“0”cameaboutbyappendingasmallerbit-stringoflengthn-1thatendedwitha“1”(otherwise2zerosappear),whichmusthavecomeaboutinturnbyappendinga“1”toanyvalidbit-stringoflengthn-2:a(n-2)ways.Total:an=a(n-1)+a

8、(n-2)n>2.a1=2,a2=3.Recognizeit?2,3,5,8,13.....?CatalanNumbersInhowmanywaysCncanweputparenthesesaroundn+1symbolstoindicateinwhichordertheyshouldbeprocessed?Eachstringx0x1x2...xnisdividedinto2sub