关闭

关闭

封号提示

内容

首页 concrete mathematics 2nd【具体数学 第二版 清晰】.pdf

concrete mathematics 2nd【具体数学 第二版 清晰】.pdf

concrete mathematics 2nd【具体数学 第…

上传者: 至尊小寳 2013-10-11 评分 4.5 0 75 10 343 暂无简介 简介 举报

简介:本文档为《concrete mathematics 2nd【具体数学 第二版 清晰】pdf》,可适用于高等教育领域,主题内容包含CONCRETEMATHEMATICSSecondEditionDedicatedtoLeonhardEuler({)AFoundationforC符等。

CONCRETEMATHEMATICSSecondEditionDedicatedtoLeonhardEuler({)AFoundationforComputerScienceCONCRETEMATHEMATICSSecondEditionRonaldLGrahamATTBellLaboratoriesDonaldEKnuthStanfordUniversityOrenPatashnikCenterforCommunicationsResearchADDISONWESLEYPUBLISHINGCOMPANYReading,MassachusettsMenloPark,CaliforniaNewYorkDonMills,OntarioWokingham,EnglandAmsterdamBonnSydneySingaporeTokyoMadridSanJuanMilanParisLibraryofCongressCataloginginPublicationDataGraham,RonaldLewis,Concretemathematics:afoundationforcomputerscienceRonaldLGraham,DonaldEKnuth,OrenPatashnikndedxiii,pcmBibliography:pIncludesindexISBNMathematicsComputerscienceMathematicsIKnuth,DonaldErvin,IIPatashnik,Oren,IIITitleQAGdcCIPReproducedbyAddisonWesleyfromcamerareadycopysuppliedbytheauthorsCopyrightc,byAddisonWesleyPublishingCompany,IncAllrightsreservedNopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmitted,inanyformorbyanymeans,electronic,mechanical,photocopying,recording,orotherwise,withoutthepriorwrittenpermissionofthepublisherPrintedintheUnitedStatesofAmerica{MA{PrefaceTHISBOOKISBASEDonacourseofthesamenamethathasbeentaughtAudience,level,andtreatment|adescriptionofsuchmattersiswhatprefacesaresupposedtobeabout"|PRHalmosannuallyatStanfordUniversitysinceAboutftystudentshavetakeniteachyear|juniorsandseniors,butmostlygraduatestudents|andalumnioftheseclasseshavebeguntospawnsimilarcourseselsewhereThusthetimeseemsripetopresentthematerialtoawideraudience(includingsophomores)ItwasadarkandstormydecadewhenConcreteMathematicswasbornLongheldvalueswereconstantlybeingquestionedduringthoseturbulentyearscollegecampuseswerehotbedsofcontroversyThecollegecurriculumitselfwaschallenged,andmathematicsdidnotescapescrutinyJohnHammersleyhadjustwrittenathoughtprovokingarticleOntheenfeeblementofmathematicalskillsby`ModernMathematics'andbysimilarsoftintellectualtrashinschoolsanduniversities"otherworriedmathematiciansevenasked,Canmathematicsbesaved"OneofthepresentauthorshadPeopledoacquirealittlebriefauthoritybyequippingthemselveswithjargon:theycanponticateandairasupercialexpertiseButwhatweshouldaskofeducatedmathematiciansisnotwhattheycanspeechifyabout,norevenwhattheyknowabouttheexistingcorpusofmathematicalknowledge,butratherwhatcantheynowdowiththeirlearningandwhethertheycanactuallysolvemathematicalproblemsarisinginpracticeInshort,welookfordeedsnotwords"|JHammersleyembarkedonaseriesofbookscalledTheArtofComputerProgramming,andinwritingtherstvolumehe(DEK)hadfoundthatthereweremathematicaltoolsmissingfromhisrepertoirethemathematicsheneededforathorough,wellgroundedunderstandingofcomputerprogramswasquitedierentfromwhathe'dlearnedasamathematicsmajorincollegeSoheintroducedanewcourse,teachingwhathewishedsomebodyhadtaughthimThecoursetitleConcreteMathematics"wasoriginallyintendedasanantidotetoAbstractMathematics,"sinceconcreteclassicalresultswererapidlybeingsweptoutofthemodernmathematicalcurriculumbyanewwaveofabstractideaspopularlycalledtheNewMath"Abstractmathematicsisawonderfulsubject,andthere'snothingwrongwithit:It'sbeautiful,general,andusefulButitsadherentshadbecomedeludedthattherestofmathematicswasinferiorandnolongerworthyofattentionThegoalofgeneralizationhadbecomesofashionablethatagenerationofmathematicianshadbecomeunabletorelishbeautyintheparticular,toenjoythechallengeofsolvingquantitativeproblems,ortoappreciatethevalueoftechniqueAbstractmathematicswasbecominginbredandlosingtouchwithrealitymathematicaleducationneededaconcretecounterweightinordertorestoreahealthybalanceWhenDEKtaughtConcreteMathematicsatStanfordforthersttime,heexplainedthesomewhatstrangetitlebysayingthatitwashisattemptvviPREFACEtoteachamathcoursethatwashardinsteadofsoftHeannouncedthat,contrarytotheexpectationsofsomeofhiscolleagues,hewasnotgoingtoteachtheTheoryofAggregates,norStone'sEmbeddingTheorem,noreventheStone{Cechcompactication(SeveralstudentsfromthecivilengineeringTheheartofmathematicsconsistsofconcreteexamplesandconcreteproblems"|PRHalmosdepartmentgotupandquietlylefttheroom)AlthoughConcreteMathematicsbeganasareactionagainstothertrends,themainreasonsforitsexistencewerepositiveinsteadofnegativeAndasthecoursecontinueditspopularplaceinthecurriculum,itssubjectmattersolidied"andprovedtobevaluableinavarietyofnewapplicationsMeanwhile,independentconrmationfortheappropriatenessofthenamecamefromanotherdirection,whenZAMelzakpublishedtwovolumesentitledItisdownrightsinfultoteachtheabstractbeforetheconcrete"|ZAMelzakCompaniontoConcreteMathematicsThematerialofconcretemathematicsmayseematrsttobeadisparatebagoftricks,butpracticemakesitintoadisciplinedsetoftoolsIndeed,thetechniqueshaveanunderlyingunityandastrongappealformanypeopleWhenanotheroneoftheauthors(RLG)rsttaughtthecoursein,thestudentshadsuchfunthattheydecidedtoholdaclassreunionayearlaterButwhatexactlyisConcreteMathematicsItisablendofcontinuousConcreteMathematicsisabridgetoabstractmathematicsanddiscretemathematicsMoreconcretely,itisthecontrolledmanipulationofmathematicalformulas,usingacollectionoftechniquesforsolvingproblemsOnceyou,thereader,havelearnedthematerialinthisbook,allyouwillneedisacoolhead,alargesheetofpaper,andfairlydecenthandwritinginordertoevaluatehorrendouslookingsums,tosolvecomplexrecurrencerelations,andtodiscoversubtlepatternsindataYouwillbesouentinalgebraictechniquesthatyouwilloftennditeasiertoobtainexactresultsthantosettleforapproximateanswersthatarevalidonlyinalimitingsenseThemajortopicstreatedinthisbookincludesums,recurrences,eleTheadvancedreaderwhoskipspartsthatappeartooelementarymaymissmorethanthelessadvancedreaderwhoskipspartsthatappeartoocomplex"|GPolyamentarynumbertheory,binomialcoecients,generatingfunctions,discreteprobability,andasymptoticmethodsTheemphasisisonmanipulativetechniqueratherthanonexistencetheoremsorcombinatorialreasoningthegoalisforeachreadertobecomeasfamiliarwithdiscreteoperations(likethegreatestintegerfunctionandnitesummation)asastudentofcalculusisfamiliarwithcontinuousoperations(liketheabsolutevaluefunctionandinniteintegration)NoticethatthislistoftopicsisquitedierentfromwhatisusuallytaughtnowadaysinundergraduatecoursesentitledDiscreteMathematics"Thereforethesubjectneedsadistinctivename,andConcreteMathematics"hasprovedtobeassuitableasanyother(We'renotboldenoughtotryDistinuousMathematics)TheoriginaltextbookforStanford'scourseonconcretemathematicswastheMathematicalPreliminaries"sectioninTheArtofComputerProgrammingButthepresentationinthosepagesisquiteterse,soanotherauthor(OP)wasinspiredtodraftalengthysetofsupplementarynotesThePREFACEviipresentbookisanoutgrowthofthosenotesitisanexpansionof,andamoreleisurelyintroductionto,thematerialofMathematicalPreliminariesSomeofthemoreadvancedpartshavebeenomittedontheotherhand,severaltopicsnotfoundtherehavebeenincludedheresothatthestorywillbecompleteTheauthorshaveenjoyedputtingthisbooktogetherbecausethesubjectbegantojellandtotakeonalifeofitsownbeforeoureyesthisbookalmostaconcretelifepreserverthrowntostudentssinkinginaseaofabstraction"|WGottschalkseemedtowriteitselfMoreover,thesomewhatunconventionalapproacheswehaveadoptedinseveralplaceshaveseemedtottogethersowell,aftertheseyearsofexperience,thatwecan'thelpfeelingthatthisbookisakindofmanifestoaboutourfavoritewaytodomathematicsSowethinkthebookhasturnedouttobeataleofmathematicalbeautyandsurprise,andwehopethatourreaderswillshareatleastofthepleasurewehadwhilewritingitSincethisbookwasborninauniversitysetting,wehavetriedtocapturethespiritofacontemporaryclassroombyadoptinganinformalstyleSomepeoplethinkthatmathematicsisaseriousbusinessthatmustalwaysbecoldanddrybutwethinkmathematicsisfun,andwearen'tashamedtoadmitthefactWhyshouldastrictboundarylinebedrawnbetweenworkandplayConcretemathematicsisfullofappealingpatternsthemanipulationsarenotalwayseasy,buttheanswerscanbeastonishinglyattractiveThejoysandsorrowsofmathematicalworkarereectedexplicitlyinthisbookbecausetheyarepartofourlivesStudentsalwaysknowbetterthantheirteachers,sowehaveaskedtherststudentsofthismaterialtocontributetheirfrankopinions,asgrati"Mathgrati:Kilroywasn'tHaarFreethegroupNukethekernelPowertothenN=P=NPinthemarginsSomeofthesemarginalmarkingsaremerelycorny,someareprofoundsomeofthemwarnaboutambiguitiesorobscurities,othersaretypicalcommentsmadebywiseguysinthebackrowsomearepositive,somearenegative,somearezeroButtheyallarerealindicationsoffeelingsthatshouldmakethetextmaterialeasiertoassimilate(TheinspirationforsuchmarginalnotescomesfromastudenthandbookentitledApproachingStanford,wheretheocialuniversitylineiscounterbalancedbytheremarksofoutgoingstudentsForexample,Stanfordsays,ThereareafewthingsIhaveonlyamarginalinterestinthissubjectyoucannotmissinthisamorphousshapewhichisStanford"themarginsays,Amorphouswhattheh***doesthatmeanTypicalofthepseudointellectualismaroundhere"Stanford:Thereisnoendtothepotentialofagroupofstudentslivingtogether"Grato:Stanforddormsarelikezooswithoutakeeper")ThemarginsalsoincludedirectquotationsfromfamousmathematiciansThiswasthemostenjoyablecourseI'veeverhadButitmightbenicetosummarizethematerialasyougoalongofpastgenerations,givingtheactualwordsinwhichtheyannouncedsomeoftheirfundamentaldiscoveriesSomehowitseemsappropriatetomixthewordsofLeibniz,Euler,Gauss,andotherswiththoseofthepeoplewhowillbecontinuingtheworkMathematicsisanongoingendeavorforpeopleeverywheremanystrandsarebeingwovenintoonerichfabricviiiPREFACEThisbookcontainsmorethanexercises,dividedintosixcategories:Isee:Concretemathematicsmeansdrilling•Warmupsareexercisesthateveryreadershouldtrytodowhenrstreadingthematerial•Basicsareexercisestodevelopfactsthatarebestlearnedbytryingone'sownderivationratherthanbyreadingsomebodyelse'sThehomeworkwastoughbutIlearnedalotItwaswortheveryhour•Homeworkexercisesareproblemsintendedtodeepenanunderstandingofmaterialinthecurrentchapter•ExamproblemstypicallyinvolveideasfromtwoormorechapterssimultaneouslytheyaregenerallyintendedforuseintakehomeexamsTakehomeexamsarevital|keepthem(notforinclassexamsundertimepressure)•BonusproblemsgobeyondwhatanaveragestudentofconcretemathematicsisexpectedtohandlewhiletakingacoursebasedonthisbookExamswereharderthanthehomeworkledmetoexpecttheyextendthetextininterestingways•Researchproblemsmayormaynotbehumanlysolvable,buttheonespresentedhereseemtobeworthatry(withouttimepressure)AnswerstoalltheexercisesappearinAppendixA,oftenwithadditionalinformationaboutrelatedresults(Ofcourse,theanswers"toresearchproblemsareincompletebuteveninthesecases,partialresultsorhintsaregiventhatmightprovetobehelpful)Readersareencouragedtolookattheanswers,especiallytheanswerstothewarmupproblems,butonlyaftermakingaseriousattempttosolvetheproblemwithoutpeekingCheatersmaypassthiscoursebyjustcopyingtheanswers,butthey'reonlycheatingthemselvesWehavetriedinAppendixCtogivepropercredittothesourcesofeachexercise,sinceagreatdealofcreativityandorluckoftengoesintothedesignofaninstructiveproblemMathematicianshaveunfortunatelydevelopedatraditionofborrowingexerciseswithoutanyacknowledgmentwebelievethattheoppositetradition,practicedforexamplebybooksandmagazinesaboutchess(wherenames,dates,andlocationsoforiginalchessproblemsareroutinelyspecied)isfarsuperiorHowever,wehavenotbeenDicultexamsdon'ttakeintoaccountstudentswhohaveotherclassestoprepareforabletopindownthesourcesofmanyproblemsthathavebecomepartofthefolkloreIfanyreaderknowstheoriginofanexerciseforwhichourcitationismissingorinaccurate,wewouldbegladtolearnthedetailssothatwecancorrecttheomissioninsubsequenteditionsofthisbookThetypefaceusedformathematicsthroughoutthisbookisanewdesignbyHermannZapf,commissionedbytheAmericanMathematicalSocietyanddevelopedwiththehelpofacommitteethatincludedBBeeton,RPBoas,LKDurst,DEKnuth,PMurdock,RSPalais,PRenz,ESwanson,SBWhidden,andWBWoolfTheunderlyingphilosophyofZapf'sdesignistocapturetheavorofmathematicsasitmightbewrittenbyamathematicianwithexcellenthandwritingAhandwrittenratherthanmechanicalstyleisappropriatebecausepeoplegenerallycreatemathematicswithpen,pencil,PREFACEixorchalk(Forexample,oneofthetrademarksofthenewdesignisthesymbolforzero,`',whichisslightlypointedatthetopbecauseahandwrittenzerorarelyclosestogethersmoothlywhenthecurvereturnstoitsstartingpoint)I'munaccustomedtothisfaceThelettersareupright,notitalic,sothatsubscripts,superscripts,andaccentsaremoreeasilyttedwithordinarysymbolsThisnewtypefamilyhasbeennamedAMSEuler,afterthegreatSwissmathematicianLeonhardEuler({)whodiscoveredsomuchofmathematicsasweknowittodayThealphabetsincludeEulerText(AaBbCcthroughXxYyZz),EulerFraktur(AaBbCcthroughXxYyZz),andEulerScriptCapitals(ABCthroughXYZ),aswellasEulerGreek(AαBβΓγthroughXχΨψΩω)andspecialsymbolssuchasandWeareespeciallypleasedtobeabletoinauguratetheEulerfamilyoftypefacesinthisbook,becauseLeonhardEuler'sspirittrulylivesoneverypage:ConcretemathematicsisEulerianmathematicsTheauthorsareextremelygratefultoAndreiBroder,ErnstMayr,AnDearprof:Thanksfor()thepuns,()thesubjectmatterdrewYao,andFrancesYao,whocontributedgreatlytothisbookduringtheyearsthattheytaughtConcreteMathematicsatStanfordFurthermoreweoerthankstotheteachingassistantswhocreativelytranscribedwhattookplaceinclasseachyearandwhohelpedtodesigntheexaminationquestionstheirnamesarelistedinAppendixCThisbook,whichisessentiallyacompendiumofsixteenyears'worthoflecturenotes,wouldhavebeenimpossiblewithouttheirrstrateworkManyotherpeoplehavehelpedtomakethisbookarealityForexample,wewishtocommendthestudentsatBrown,Columbia,CUNY,Princeton,Idon'tseehowwhatI'velearnedwilleverhelpmeRice,andStanfordwhocontributedthechoicegratiandhelpedtodebugourrstdraftsOurcontactsatAddisonWesleywereespeciallyecientandhelpfulinparticular,wewishtothankourpublisher(PeterGordon),productionsupervisor(BetteAaronson),designer(RoyBrown),andcopyeditor(LynDupre)TheNationalScienceFoundationandtheOceofNavalResearchhavegiveninvaluablesupportCherylGrahamwastremendouslyhelpfulaswepreparedtheindexAndaboveall,wewishtothankourwives(Fan,Jill,andAmy)fortheirpatience,support,encouragement,andideasIhadalotoftroubleinthisclass,butIknowitsharpenedmymathskillsandmythinkingskillsThissecondeditionfeaturesanewSection,whichdescribessomeimportantideasthatDoronZeilbergerdiscoveredshortlyafterthersteditionwenttopressAdditionalimprovementstotherstprintingcanalsobefoundonalmosteverypageWehavetriedtoproduceaperfectbook,butweareimperfectauthorsThereforewesolicithelpincorrectinganymistakesthatwe'vemadeArewardof$willgratefullybepaidtotherstnderofanyerror,whetheritismathematical,historical,ortypographicalIwouldadvisethecasualstudenttostayawayfromthiscourseMurrayHill,NewJersey|RLGandStanford,CaliforniaDEKMayandOctoberOPANoteonNotationSOMEOFTHESYMBOLISMinthisbookhasnot(yet)becomestandardHereisalistofnotationsthatmightbeunfamiliartoreaderswhohavelearnedsimilarmaterialfromotherbooks,togetherwiththepagenumberswherethesenotationsareexplained(Seethegeneralindex,attheendofthebook,forreferencestomorestandardnotations)NotationNamePagelnxnaturallogarithm:logexlgxbinarylogarithm:logxlogxcommonlogarithm:logxbxcoor:maxfn|nx,integerngdxeceiling:minfn|nx,integerngxmodyremainder:xybxycfxgfractionalpart:xmodf(x)δxindenitesummationbaf(x)δxdenitesummationxnfallingfactorialpower:x!(xn)!,xnrisingfactorialpower:Γ(xn)Γ(x),n<subfactorial:n!!n!!()nn!n!<zrealpart:x,ifz=xiyIfyoudon'tunderstandwhatthexdenotesatthebottomofthispage,tryaskingyourLatinprofessorinsteadofyourmathprofessor=zimaginarypart:y,ifz=xiyHnharmonicnumber:nH(x)ngeneralizedharmonicnumber:xnxxANOTEONNOTATIONxif(m)(z)mthderivativeoffatznmStirlingcyclenumber(therstkind"){nm}Stirlingsubsetnumber(thesecondkind")nmEuleriannumbernmSecondorderEuleriannumberPrestressedconcretemathematicsisconcretemathematicsthat'sprecededbyabewilderinglistofnotations(ama)bradixnotationformk=akbkK(a,,an)continuantpolynomialF(a,bcz)hypergeometricfunction#Acardinality:numberofelementsinthesetAznf(z)coecientofzninf(z)αβclosedinterval:thesetfx|αxβgm=nifm=n,otherwise*mnnifmd

职业精品

精彩专题

上传我的资料

热门资料

资料评价:

/ 670
所需积分:1 立即下载

意见
反馈

返回
顶部

Q