Analytisk kombinatorik
Analytic Combinatorics är en bok om matematiken för kombinatorisk uppräkning , med hjälp av genererande funktioner och komplex analys för att förstå tillväxthastigheten för antalet kombinatoriska objekt. Den skrevs av Philippe Flajolet och Robert Sedgewick och publicerades av Cambridge University Press 2009. Den vann Leroy P. Steele-priset 2019.
Ämnen
Huvuddelen av boken är organiserad i tre delar. Den första delen, som omfattar tre kapitel och ungefär den första fjärdedelen av boken, handlar om den symboliska metoden i kombinatorik , där klasser av kombinatoriska objekt associeras med formler som beskriver deras strukturer, och sedan omtolkas dessa formler för att producera de genererande funktionerna eller exponentiellt genererande funktioner för klasserna, i vissa fall med hjälp av verktyg som Lagranges inversionssats som en del av omtolkningsprocessen. Kapitlen i denna del delar upp materialet i uppräkning av omärkta objekt, uppräkning av märkta objekt och multivariata genererande funktioner.
De fem kapitlen i bokens andra del, ungefär hälften av texten och "bokens hjärta", handlar om tillämpningen av verktyg från komplex analys till den genererande funktionen, för att förstå asymptotiken hos antalet objekt i en kombinatorisk klass. I synnerhet, för tillräckligt väluppförda genererande funktioner, Cauchys integralformel användas för att återvinna effektseriekoefficienterna (det verkliga studieobjektet) från genereringsfunktionen, och kunskap om funktionens singulariteter kan användas för att härleda korrekta uppskattningar av de resulterande integralerna. Efter ett inledande kapitel och ett kapitel som ger exempel på möjliga beteenden hos rationella funktioner och meromorfa funktioner diskuterar de återstående kapitlen i denna del hur en funktions singulariteter kan användas för att analysera det asymptotiska beteendet hos dess potensserier, tillämpa denna metod till ett stort antal kombinatoriska exempel, och studera sadelpunktsmetoden för konturintegrering för att hantera några knepigare exempel.
Den sista delen undersöker beteendet hos slumpmässiga kombinatoriska strukturer, snarare än det totala antalet strukturer, med samma verktygslåda. Utöver förväntade värden för kombinatoriska kvantiteter av intresse, studerar den också gränssatser och teori för stora avvikelser för dessa kvantiteter. Tre bilagor ger bakgrund om kombinatorik och asymptotik, i komplex analys och i sannolikhetsteori.
De kombinatoriska strukturerna som undersöks genom hela boken sträcker sig brett över sekvenser , formella språk , partitioner och kompositioner , permutationer , grafer och banor i grafer , och gitterbanor . Med dessa ämnen kopplar analysen i boken till tillämpningar inom andra områden, inklusive abstrakt algebra , talteori och analys av algoritmer .
Publik och mottagning
Analytisk kombinatorik är inte i första hand en lärobok; den har till exempel inga övningar. Ändå kan den användas som lärobok för ett valfritt grundutbildningsämne, forskarkurs eller seminarium, även om recensenten Miklós Bóna skriver att det behövs ett visst urval, eftersom den "har tillräckligt med material för tre eller fler terminer". Det kan också vara en referens för forskare inom detta ämne.
Recensenten Toufik Mansour kallar det inte bara "en omfattande teoretisk behandling" utan "intressant läsning". Recensenten Christopher Hanusa skriver att "skrivstilen är inbjudande, ämnesmaterialet är samtida och medryckande", och han rekommenderar boken till alla som "lär sig eller arbetar i kombinatorik".
Analytic Combinatorics vann Leroy P. Steele Prize for Mathematical Exposition of the American Mathematical Society 2019 (postumt för Flajolet). Priscitatet kallade boken "ett auktoritativt och mycket tillgängligt kompendium av dess ämne, som visar det djupa gränssnittet mellan kombinatorisk matematik och klassisk analys". GH Hardys och Srinivasa Ramanujans arbete med partitionsfunktionen , citerade citatet också en recension av Robin Pemantle som säger att "Detta är en av de böcker som markerar uppkomsten av en subfield," underområdet för analytisk kombinatorik . På samma sätt, avslutar Bóna, "Analytisk kombinatorik är nu definierad. Författarna skrev boken om det."
externa länkar
- för Analytic Combinatorics , inklusive en nedladdningsbar fulltext av boken