https://ebookmass.com/product/enumerative-combinatorics-
Instant digital products (PDF, ePub, MOBI) ready for you
Download now and discover formats that fit your needs...
Enumerative Combinatorics: Volume 2: Second Edition
Richard P. Stanley
https://ebookmass.com/product/enumerative-combinatoricsvolume-2-second-edition-richard-p-stanley-3/
ebookmass.com
Enumerative Combinatorics: Volume 2: Second Edition
Richard P. Stanley
https://ebookmass.com/product/enumerative-combinatoricsvolume-2-second-edition-richard-p-stanley-2/
ebookmass.com
Fetal and Neonatal Physiology, 2-Volume Set 6th Edition
Richard A. Polin
https://ebookmass.com/product/fetal-and-neonatal-physiology-2-volumeset-6th-edition-richard-a-polin/
ebookmass.com
Signing Naturally Units 7-12 eBook https://ebookmass.com/product/signing-naturally-units-7-12-ebook/
ebookmass.com
https://ebookmass.com/product/stop-think-invest-a-behavioral-financeframework-for-optimizing-investment-portfolios-michael-bailey/
ebookmass.com
Nanotechnology in Modern Animal Biotechnology: Concepts and Applications Pawan Kumar Maurya
https://ebookmass.com/product/nanotechnology-in-modern-animalbiotechnology-concepts-and-applications-pawan-kumar-maurya/
ebookmass.com
Gabbe’s Obstetrics Essentials: Normal & Problem Pregnancies 1st Edition Mark B Landon Et Al.
https://ebookmass.com/product/gabbes-obstetrics-essentials-normalproblem-pregnancies-1st-edition-mark-b-landon-et-al/
ebookmass.com
Fundamentals of Voice and Articulation 15th Edition, (Ebook PDF)
https://ebookmass.com/product/fundamentals-of-voice-andarticulation-15th-edition-ebook-pdf/
ebookmass.com
Data analytics Anil Maheshwari
https://ebookmass.com/product/data-analytics-anil-maheshwari/
ebookmass.com
Cardiovascular and Pulmonary Physical Therapy E Book: Evidence to Practice 5th Edition, (Ebook PDF)
https://ebookmass.com/product/cardiovascular-and-pulmonary-physicaltherapy-e-book-evidence-to-practice-5th-edition-ebook-pdf/
ebookmass.com
Volume 2
Second Edition
RICHARD STANLEY Enumerative Combinatorics CAMBRIDGESTUDIESINADVANCEDMATHEMATICS208
EditorialBoard
J.BERTOIN,B.BOLLOB ´ AS,W.FULTON,B.KRA,I.MOERDIJK, C.PRAEGER,P.SARNAK,B.SIMON,B.TOTARO
ENUMERATIVECOMBINATORICS Volume2 RichardStanley’stwo-volumebasicintroductiontoenumerativecombinatoricshas becomethestandardguidetothetopicforstudentsandexpertsalike.Thisthoroughly revisedsecondeditionofvolumetwocoversthecompositionofgeneratingfunctions, inparticulartheexponentialformulaandtheLagrangeinversionformula,labelledand unlabelledtrees,algebraic,D-finite,andnoncommutativegeneratingfunctions,and symmetricfunctions.Thechapteronsymmetricfunctionsprovidestheonlyavailabletreatmentofthissubjectsuitableforanintroductorygraduatecourseandfocusing oncombinatorics,especiallytheRobinson–Schensted–Knuthalgorithm.Anappendix bySergeyFomincoverssomedeeperaspectsofsymmetricfunctions,includingjeude taquinandtheLittlewood–Richardsonrule.Theexercisesinthebookplayavitalrolein developingthematerial,andthissecondeditionfeaturesover400exercises,including 159newexercisesonsymmetricfunctions,allwithsolutionsorreferencestosolutions.
RichardP.Stanley isEmeritusProfessorofMathematicsattheMassachusettsInstitute ofTechnologyandanArtsandSciencesDistinguishedProfessorattheUniversityof Miami.Hehaswrittenover180researcharticlesandsixbooks.AmongStanley’smany distinctionsaremembershipintheNationalAcademyofSciences(electedin1995)and the2001LeroyP.SteelePrizeforMathematicalExposition.
CAMBRIDGESTUDIESINADVANCEDMATHEMATICS
EditorialBoard
J.BERTOIN,B.BOLLOB ´ AS,W.FULTON,B.KRA,I.MOERDIJK, C.PRAEGER,P.SARNAK,B.SIMON,B.TOTARO
AllthetitleslistedbelowcanbeobtainedfromgoodbooksellersorfromCambridgeUniversity Press.Foracompleteserieslisting,visit www.cambridge.org/mathematics.
AlreadyPublished
171J.Gough&J.Kupsch QuantumFieldsandProcesses
172T.Ceccherini-Silberstein,F.Scarabotti&F.Tolli DiscreteHarmonicAnalysis
173P.Garrett ModernAnalysisofAutomorphicFormsbyExample,I
174P.Garrett ModernAnalysisofAutomorphicFormsbyExample,II
175G.Navarro CharacterTheoryandtheMcKayConjecture
176P.Fleig,H.P.A.Gustafsson,A.Kleinschmidt&D.Persson EisensteinSeriesand AutomorphicRepresentations
177E.Peterson FormalGeometryandBordismOperators
178A.Ogus LecturesonLogarithmicAlgebraicGeometry
179N.Nikolski HardySpaces
180D.-C.Cisinski HigherCategoriesandHomotopicalAlgebra
181A.Agrachev,D.Barilari&U.Boscain AComprehensiveIntroductiontoSub-Riemannian Geometry
182N.Nikolski ToeplitzMatricesandOperators
183A.Yekutieli DerivedCategories
184C.Demeter FourierRestriction,DecouplingandApplications
185D.Barnes&C.Roitzheim FoundationsofStableHomotopyTheory
186V.Vasyunin&A.Volberg TheBellmanFunctionTechniqueinHarmonicAnalysis
187M.Geck&G.Malle TheCharacterTheoryofFiniteGroupsofLieType
188B.Richter CategoryTheoryforHomotopyTheory
189R.Willett&G.Yu HigherIndexTheory
190A.Bobrowski GeneratorsofMarkovChains
191D.Cao,S.Peng&S.Yan SingularlyPerturbedMethodsforNonlinearEllipticProblems
192E.Kowalski AnIntroductiontoProbabilisticNumberTheory
193V.Gorin LecturesonRandomLozengeTilings
194E.Riehl&D.Verity Elementsof ∞-CategoryTheory
195 H.Krause HomologicalTheoryofRepresentations
196F.Durand&D.Perrin DimensionGroupsandDynamicalSystems
197A.Sheffer PolynomialMethodsandIncidenceTheory
198T.Dobson,A.Malniˇc&D.Maruˇsiˇc SymmetryinGraphs
199K.S.Kedlaya p-adicDifferentialEquations
200R.L.Frank,A.Laptev&T.Weidl Schr¨odingerOperators:EigenvaluesandLieb–Thirring Inequalities
201J.vanNeerven FunctionalAnalysis
202A.Schmeding AnIntroductiontoInfinite-DimensionalDifferentialGeometry
203F.CabelloS´anchez&J.M.F.Castillo HomologicalMethodsinBanachSpaceTheory
204G.P.Paternain,M.Salo&G.Uhlmann GeometricInverseProblems
205V.Platonov,A.Rapinchuk&I.Rapinchuk AlgebraicGroupsandNumberTheory,I(2nd Edition)
206D.Huybrechts TheGeometryofCubicHypersurfaces
207F.Maggi OptimalMassTransportonEuclideanSpaces
208R.P.Stanley EnumerativeCombinatorics,II(2ndedition)
209M.Kawakita ComplexAlgebraicThreefolds
210D.Anderson&W.Fulton EquivariantCohomologyinAlgebraicGeometry
“Thisisoneofthegreatbooks;readable,deepandfullofgems.Itbrings algebraiccombinatoricstolife.IteachoutofitandfeelthatifIcangetmy studentsto‘touchStanley’Ihavegiventhemagiftforlife.”
–PersiDiaconis,StanfordUniversity
“ItiswonderfultocelebratethecompletionofthesecondeditionofRichard Stanley’s EnumerativeCombinatorics,oneofthefinestmathematicalworks ofalltime.Hehasaddednearly200exercises,togetherwiththeiranswers,to whatwasalreadyauniquelymasterfulsummaryofavastandbeautifultheory. WhenpairedwiththesecondeditionofVolume1,histwoclassicvolumeswill surelybeatimelesstreasureforgenerationstocome.”
–DonaldE.Knuth,StanfordUniversity
“Anupdatedclassicwithamesmerizingarrayofinterconnectedexamples. ThroughStanley’smasterfulexposition,thecurrentandfuturegenerationsof mathematicianswilllearntheinherentbeautyandpleasuresofenumeration.”
–JuneHuh,PrincetonUniversity
“IhaveusedRichardStanley’sbooksonEnumerativeCombinatoricsnumerous timesforthecombinatoricsclassesIhavetaught.Thisneweditioncontains manynewexercises,whichwillnodoubtbeextremelyusefulforthenext generationofcombinatorialists.”
–AnneSchilling,UniversityofCalifornia,Davis
“RichardStanley’sEnumerativeCombinatorics,intwovolumes,isanessentialreferenceforresearchersandgraduatestudentsinthefieldofenumeration. Volume2,newlyrevised,includescomprehensivecoverageofcomposition andinversionofgeneratingfunctions,exponentialandalgebraicgenerating functions,andsymmetricfunctions.Thetreatmentofsymmetricfunctionsis especiallynoteworthyforitsthoroughnessandaccessibility.Engagingproblemsandsolutions,anddetailedhistoricalnotes,addtothevalueofthisbook. Itprovidesanexcellentintroductiontothesubjectforbeginnerswhilealso offeringadvancedresearchersnewinsightsandperspectives.”
–IraGessel,BrandeisUniversity
EnumerativeCombinatorics Volume2 SecondEdition RICHARDP.STANLEY MassachusettsInstituteofTechnology
WithanAppendixby
SERGEYFOMIN UniversityofMichigan
ShaftesburyRoad,CambridgeCB28EA,UnitedKingdom OneLibertyPlaza,20thFloor,NewYork,NY10006,USA
477WilliamstownRoad,PortMelbourne,VIC3207,Australia
314–321,3rdFloor,Plot3,SplendorForum,JasolaDistrictCentre, NewDelhi–110025,India
103PenangRoad,#05–06/07,VisioncrestCommercial,Singapore238467
CambridgeUniversityPressispartofCambridgeUniversityPress&Assessment, adepartmentoftheUniversityofCambridge.
WesharetheUniversity’smissiontocontributetosocietythroughthepursuitof education,learningandresearchatthehighestinternationallevelsofexcellence.
www.cambridge.org
Informationonthistitle: www.cambridge.org/9781009262491 DOI: 10.1017/9781009262538
©CambridgeUniversityPress1997,2012
©RichardP.Stanley2024
Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithoutthewritten permissionofCambridgeUniversityPress&Assessment.
FirsteditionpublishedbyWadsworth1986
FirstCambridgeedition1997
Secondedition(Volume1)published2012
PrintedintheUnitedKingdombyTJBooksLimited,PadstowCornwall
AcataloguerecordforthispublicationisavailablefromtheBritishLibrary. ACataloging-in-PublicationdatarecordforthisbookisavailablefromtheLibraryof Congress.
ISBN978-1-009-26249-1Hardback ISBN978-1-009-26248-4Paperback
CambridgeUniversityPress&Assessmenthasnoresponsibilityforthepersistence oraccuracyofURLsforexternalorthird-partyinternetwebsitesreferredtointhis publicationanddoesnotguaranteethatanycontentonsuchwebsitesis,orwill remain,accurateorappropriate.
toAtsuko,Kenneth,Sharon,Beth,Bennett,andCole
5TreesandtheCompositionofGeneratingFunctions
5.1TheExponentialFormula
5.4TheLagrangeinversionformula
6Algebraic,D-finite,andNoncommutativeGenerating
6.4 D-finitegeneratingfunctions
7.5Completehomogeneoussymmetricfunctions
7.6Aninvolution
7.7Powersumsymmetricfunctions
7.8Specializations
7.9Ascalarproduct
7.10ThecombinatorialdefinitionofSchurfunctions
7.11TheRSKalgorithm
7.12SomeconsequencesoftheRSKalgorithm
7.16TheJacobi–Trudiidentity
7.17TheMurnaghan–Nakayamarule
7.18Thecharactersofthesymmetricgroup
7.19Quasisymmetricfunctions
7.20PlanepartitionsandtheRSKalgorithm
7.21Planepartitionswithboundedpartsize
7.22ReverseplanepartitionsandtheHillman–Grassl correspondence
A1.1KnuthequivalenceandGreene’stheorem
A1.2ProofsofTheorems
A1.3Jeudetaquin
A1.4TheSch¨utzenbergerinvolution
A1.5TheLittlewood–RichardsonRule
A1.6VariationsoftheLittlewood–Richardsonrule
A1.7Notes
PrefacetoSecondEdition Theprimarydifferencebetweenthissecondeditionandthefirstistheadditionof159newproblemsforChapter 7 (symmetricfunctions),almostall withsolutions.TheyappearintheChapter 7 sectionsentitled“Supplementary Exercises”and“SupplementarySolutions.”Thesenewproblemsarefurther evidenceoftheamazingfecundityofthetheoryofsymmetricfunctions.Philip Hallwaswellawareofthefuturepotentialofsymmetricfunctionswhenhe wroteina1955letter:∗
... wheneverinmathematicsyoumeetwithpartitions,youhaveonlytoturnoverthe stoneorliftupthebark,andyouwill,almostinfallibly,findsymmetricfunctionsunderneath.Moreprecisely,ifwehaveaclassofmathematicalobjectswhichinanaturaland significantwaycanbeplacedinone-to-onecorrespondencewiththepartitions,wemust expecttheinternalstructureoftheseobjectsandtheirrelationstooneanothertoinvolve soonerorlater thealgebraofsymmetricfunctions.
Withahandfulofexceptions,allthenewproblemsonsymmetricfunctions canbesolved(inprinciple,atanyrate)directlyfromthematerialofChapter 7. WedonotventureintoimportantextensionsoftheChapter 7 materialsuchas Macdonaldpolynomials, k-Schurfunctions,LLTpolynomials,cylindricSchur functions,etc.
Wehavealsocorrectedallknownerrorsinthefirsteditionandchangedall referencestomaterialinVolume1sothattheyconformtothesecondedition ofVolume1.AfewnewproblemshavebeenaddedoutsideChapter 7,asparts of otherproblems(soasnottoupsettheproblemnumbering),andreferences havebeenupdatedandslightlyexpanded.Theseparatelistofreferencesin eachchapterhavebeenmergedintoasinglelistappearingjustbeforetheindex. Thenumberingoftheorems,definitions,exercises,etc.,hasremainedthesame
∗ See mathshistory.st-andrews.ac.uk/Biographies/Hall. xiii
asinthefirstedition.However,someequationnumbersandfigurenumbers,as wellasalmostallthecitationnumbers,havebeenchanged.Theindexhasbeen upgraded;inparticular,everyreferencetoapersonisaseparatesubentry.
InnumerablepersonshavecontributedtothenewChapter 7 problems.They areacknowledgedintheproblemsolutions.IwouldalsoliketothankKaitlin LeachatCambridgeUniversityPressforherexcellenteditorialassistanceand toSureshKumarforhisTEXsupport.
Preface Thisisthesecond(andfinal)volumeofagraduate-levelintroductiontoenumerativecombinatorics.Tothosewhohavebeenpatientlywaitingtwelveyears sincethepublicationofVolume1,Icanonlysaythatnooneismorepleased toseeVolume2finallycompletedthanmyself.IhavetriedtocoverwhatIfeel arethefundamentaltopicsinenumerativecombinatotics,andtheonesthat arethemostusefulinapplicationsoutsideofcombinatorics.Thoughthebook isprimarilyintendedtobeatextbookforgraduatestudentsandaresource forprofessionalmathematicians,Ihopethatundergraduatesandevenbright highschoolstudentswillfindsomethingofinterest.Forinstance,manyof the66combinatorialinterpretationsofCatalannumbersprovidedbyExercise 6.19 shouldbeaccessibletoundergraduateswithalittleknowledgeof combinatorics.
Muchofthematerialinthisbookhasneverappearedbeforeintextbook form.ThisisespeciallytrueofthetreatmentofsymmetricfunctionsinChapter 7.Althoughthetheoryofsymmetricfunctionsanditsconnectionswith combinatoricsisinmyopiniononeofthemostbeautifultopicsinallofmathematics,itisadifficultsubjectforbeginnerstolearn.Thesuperbbookby Macdonaldonsymmetricfunctionsishighlyalgebraicandeschewsthefundamentalcombinatorialtoolinthissubject,viz.,theRobinson-Schensted-Knuth algorithm.IhopethatChapter 7 adequatelyfillsthisgapinthemathematical literature.Chapter 7 shouldberegardedasonlyanintroductiontothetheory ofsymmetricfunctions,andnotasacomprehensivetreatment.
AsinVolume1theexercisesplayavitalroleindevelopingthesubject.Ifin readingthetextthereaderisleftwiththefeelingof“what’sitgoodfor?”andis notsatisfiedwiththeapplicationspresentedthere,then(s)heshouldturntothe exerciseshopefullytodispelsuchdoubts.Thankstothewondersofelectronic word-processingIfounditmucheasierthanforVolume1toassembleawide varietyofexercisesandsolutions.
Iamgratefultothemanypersonswhohavecontributedinanumberof waystotheimprovementofthisbook.SpecialthanksgoestoSergeyFomin forhismanysuggestionsrelatedtoChapter 7,andespeciallyforhismasterfulexpositionofthedifficultmaterialofAppendix 1.Otherpersonswhohave carefullyreadportionsofearlierversionsofthebookandwhohaveoffered valuablesuggestionsareChristineBessenrodt,FrancescoBrenti,PersiDiaconis,WungkumFong,PhilHanlon,andMichelleWachs.RobertBeckertyped mostofChapter 5,andTomRobyandBonnieFriedmanprovidedinvaluable TEX assistance.Thefollowingadditionalpersonshavemadeatleastonesignificantcontributionthatisnotexplicitlymentionedinthetext,andIregret ifIhaveinadvertentlyomittedanyoneelsewhobelongsonthislist:ChristosAthanasiadis,AndersBjorner,MireilleBousquet-M´elou,BradleyBrock, DavidBuchsbaum,EmericDeutsch,KimmoEriksson,DominiqueFoata,Ira Gessel,CurtisGreene,PatriciaHersh,MartinIsaacs,BenjaminJoseph,Martin Klazar,DonaldKnuth,DarlaKremer,PeterLittelmann,ValeryLiskovets,Ian Macdonald,AlexanderMednykh,ThomasM¨uller,AndrewOdlyzko,AlexanderPostnikov,RobertProctor,DouglasRogers,LouShapiro,RodicaSimion, MarkSkandera,LouisSolomon,DennisStanton,RobertSulanke,Sheila Sundaram,Jean-YvesThibon,andAndreiZelevinsky.
5 TreesandtheCompositionofGenerating Functions 5.1TheExponentialFormula If F(x)and G(x)areformalpowerserieswith G(0) = 0, thenwehaveseen (afterProposition1.1.9)thatthecomposition F(G(x))isawell-definedformal powerseries.Inthischapterwewillinvestigatethecombinatorialramifications ofpowerseriescomposition.Inthissectionwewillbeconcernedwiththecase where F(x)and G(x)areexponentialgeneratingfunctions,andespeciallythe case F(x) = ex .
Let usfirstconsiderthecombinatorialsignificanceoftheproduct F(x)G(x) of twoexponentialgeneratingfunctions
Throughoutthischapter K denotesafieldofcharacteristic0(suchas C withsomeindeterminatesadjoined).Wealsodenoteby Ef (x)theexponential generating functionofthefunction f : N → K,thatis,
(n) xn n! .
5.1.1Proposition. Givenfunctionsf , g : N → K,defineanewfunctionh : N → Kbytherule
whereXisafiniteset,andwhere(S,T)rangesoverallweakorderedpartitions ofXintotwoblocks,thatis,S ∩ T =∅ andS ∪ T = X . Then
Proof. Let#X = n.Thereare(n k ) pairs(S, T )with#S = k and#T = n k,so
Fromthisequation(5.2)follows.
OnecouldalsoproveProposition 5.1.1 byusingTheorem3.18.41 appliedto thebinomialposet B ofExample3.18.3.
WehavestatedProposition 5.1.1 intermsofacertainrelationship(5.1) amongfunctions f , g and h,butitisimportanttounderstanditscombinatorialsignificance.Supposewehavetwotypesofstructures,say α and β,which canbeputonafiniteset X .Weassumethattheallowedstructuresdependonly onthecardinalityof X .Anew“combined”typeofstructure,denoted α ∪ β, canbeputon X byplacingstructuresoftype α and β onsubsets S and T , respectively,of X suchthat S ∪ T = X , S ∩ T =∅.If f (k) (respectively g(k)) are thenumberofpossiblestructuresona k-setoftype α (respectively, β), thentheright-handsideof(5.1)countsthenumberofstructuresoftype α ∪ β on X .Moregenerally,wecanassignaweight w( ) toanystructure oftype α or β.Acombinedstructureoftype α ∪ β isdefinedtohaveweightequal totheproductoftheweightsofeachpart.If f (k) and g(k) denotethesumof theweightsofallstructuresona k-setoftypes α and β,respectively,thenthe right-handsideof(5.1)countsthesumoftheweightsofallstructuresoftype α ∪ β on X .
5.1.2Example. Givenan n-elementset X , let h(n)bethenumberofwaysto split X into twosubsets S and T with S ∪T = X , S ∩T =∅;andthentolinearly ordertheelementsof S andtochooseasubsetof T .Thereare f (k) = k! ways tolinearlyordera k-elementset,and g(k) = 2k waystochooseasubsetofa k-elementset.Hence
Proposition 5.1.1 canbeiteratedtoyieldthefollowingresult.
5.1.3Proposition. Fixk ∈ P andfunctionsf1, f2, ... , fk : N → K Definea newfunctionh : N → Kby
where (T1, . .. , Tk ) rangesoverallweakorderedpartitionsofSintokblocks, thatis,T1, ... , Tk aresubsetsofSsatisfying:(i)Ti ∩ Tj =∅ ifi = j,and(ii) T1 ∪···∪ Tk = S.Then
Eh(x) = k i=1 Efi (x).
Wearenowabletogivethemainresultofthissection,whichexplains thecombinatorialsignificanceofthecompositionofexponentialgenerating functions.
5.1.4Theorem (theCompositionalFormula). Given functionsf : P → K andg : N → Kwithg(0) = 1,defineanewfunctionh : N → K by h(#S) =
h(0) = 1,
wherethesumrangesoverallpartitions(asdefinedinSection1.9) π = {B1, , Bk } ofthefinitesetS.Then
Eh(x) = Eg (Ef (x)).
(HereEf (x) = n≥1 f (n) xn n! ,sincefisonlydefinedonpositiveintegers.)
Proof. Suppose#S = n,andlet hk (n)denotetheright-handsideof(5.3)for fixed k.Since B1, ... , Bk arenonemptytheyarealldistinct,sothereare k! ways oflinearlyorderingthem.ThusbyProposition 5.1.3,
Summing (5.3)overall k ≥ 1yieldsthedesiredresult.
Theorem 5.1.4 hasthefollowingcombinatorialsignificance.Manystructuresonaset,suchasgraphsorposets,mayberegardedasdisjointunions oftheirconnectedcomponents.Inaddition,someadditionalstructuremaybe placedonthecomponentsthemselves,forexample,thecomponentscouldbe linearlyordered.Ifthereare f ( j)connectedstructuresona j-setand g(k) ways
Figure5.1Acirculararrangementoflines toplaceanadditionalstructureon k components,then h(n)isthetotalnumber ofstructuresonan n-set.Thereisanobviousgeneralizationtoweighted structures,suchaswasdiscussedafterProposition 5.1.1 Thefollowingexampleshouldhelptoelucidatethecombinatorialmeaning ofTheorem 5.1.4;moresubstantialapplicationsaregiveninSection 5.2
5.1.5 Example. Let h(n)bethenumberofwaysfor n persons toforminto nonemptylines,andthentoarrangetheselinesinacircularorder.Figure 5.1 showsonesucharrangementofninepersons.Thereare f ( j) = j! waysto linearlyorder j persons,and g(k) = (k 1)! waystocircularlyorder k ≥ 1 lines.Thus
whence h(n) = (2n 1)(n 1)!.Naturallysuchasimpleanswerdemandsa simple combinatorialproof.Namely,arrangethe n personsinacirclein(n 1)!
Figure5.2AnequivalentformofFigure 5.1
ways.Ineachofthe n spacesbetweentwopersons,eitherdoordonotdrawa bar,exceptthatatleastonebarmustbedrawn.Therearethus2n 1choices forthebars.Betweentwoconsecutivebars(orabaranditselfifthereisonly onebar)readthepersonsinclockwiseordertoobtaintheirorderinline.See Figure 5.2 forthismethodofrepresentingFigure 5.1.
The mostcommonuseofTheorem 5.1.4 isthecasewhere g(k) = 1 for all k.Incombinatorialterms,astructureisputtogetherfrom“connected”components,butnoadditionalstructureisplacedonthecomponents themselves.
5.1.6Corollary (theExponentialFormula). Given afunctionf : P → K, defineanewfunctionh : N → Kby
(0) = 1.
Then
Let ussayabriefwordaboutthecomputationalaspectsofequation(5.5). Ifthefunction f (n)isgiven,thenonecanuse(5.4)tocompute h(n).However, there isamuchmoreefficientwaytocompute h(n)from f (n)(andconversely).
5.1.7 Proposition. Letf : P → Kandh : N → KberelatedbyEh(x) = exp Ef (x) (so inparticularh(0) = 1).Thenwehaveforn ≥ 0 the recurrences
Proof. Differentiate E
)toobtain
Nowequatecoefficientsof xn/n! on bothsidesof(5.8)toobtain(5.6).(It is alsoeasytogiveacombinatorialproofof(5.6).)Equation(5.7)isjusta rearrangementof(5.6).
Thecompositionalandexponentialformulasareconcernedwithstructures onaset S obtainedbychoosingapartitionof S andthenimposingsome“connected”structureoneachblock.Insomesituationsitismorenaturaltochoose a permutation of S andthenimposea“connected”structureoneachcycle. Thesetwosituationsareclearlyequivalent,sinceapermutationisnothingmore thanapartitionwithacyclicorderingofeachblock.However,permutations ariseoftenenoughtowarrantaseparatestatement.Recallthat S(S)denotes theset(orgroup)ofallpermutationsoftheset S
5.1.8Corollary (theCompositionalFormula,permutationversion). Given functions f : P → Kandg : N → Kwithg(0) = 1,defineanewfunction h : P → K by
(#S) =
h(0) = 1, whereC1, C2, , Ck arethecyclesinthedisjointcycledecompositionof π Then
Proof. Sincethereare(j 1)! waystocyclicallyordera j-set,equation(5.9) maybewritten
(#S) =
sobyTheorem 5.1.4, Eh(x) = Eg
.
= Eg
n≥1 (n 1)!f (n) xn n!
n≥1 f (n) xn n
5.1.9Corollary (theExponentialFormula,permutationversion). Given a functionf : P → K,defineanewfunctionh : N → Kby h(#S) = π ∈S(S) f (#C1)f (#C2) · ·· f (#Ck ), #S > 0, h(0) = 1,
wherethenotationisthesameasinCorollary 5.1.8.Then
Eh(x) = exp n≥1 f (n) xn n .
InChapter3.18(seeExample3.18.3(b))werelatedadditionandmultiplicationofexponentialgeneratingfunctionstotheincidencealgebraofthelattice offinitesubsetsof N.Thereisasimilarrelationbetween composition ofexponentialgeneratingfunctionsandtheincidencealgebraofthelattice n of partitionsof[n](orany n-set).Moreprecisely,weneedtoconsidersimultaneouslyall n for n ∈ P.RecallfromSection3.10thatif σ ≤ π in n,then wehaveanaturaldecomposition [σ
where |σ | = iai and |π | = ai.Let = ( 1, 2, . .. ).Foreach n ∈ P, let fn ∈ I( n, K), theincidencealgebraof n.Supposethatthesequence f = ( f1, f2, ... )satisfiesthefollowingproperty:Thereisafunction(alsodenoted f ) f : P → K suchthatif σ ≤ π in n and[σ , π ]satisfies(5.10),then
Wethencall f a multiplicativefunction on .
Forinstance,if ζn isthezetafunctionof n,then ζ = (ζ1, ζ2, . .. )ismultiplicativewith ζ (n) = 1 forall n ∈ P.If µn istheM¨obiusfunctionof n, thenbyProposition3.8.2andequation(3.37)weseethat µ = (µ1, µ2, . .. )is multiplicativewith µ(n) = ( 1)n 1(n 1)!.
Let f = ( f1, f2, ... )and g = (g1, g2, . .. ),where fn, gn ∈ I( n, K). Wecan definethe convolutionfg = (( fg)1,( fg)2, ... )by
( fg)n = fngn (convolutionin I( n, K)). (5.12)
5.1.10Lemma. Iffandgaremultiplicativeon ,thensoisfg.
Proof. Let P and Q belocallyfiniteposets,andlet u ∈ I(P, K), v ∈ I(Q, K).
Define u × v ∈ I(P × Q, K)by
u × v((x, x ),(y, y )) = u(x, y)v(x , y ).
ThenastraightforwardargumentasintheproofofProposition3.8.2shows that(u × v)(u × v ) = uu × vv . Thusfrom(5.10)wehave ( fg)n(σ , π ) = f1g1( ˆ 0, ˆ 1)a1 · ·· fngn( ˆ 0, ˆ 1)an = fg(1)a1 ··· fg(n)an .
ItfollowsfromLemma 5.1.10 thattheset M ( ) = M ( , K) ofmultiplicativefunctionson formsasemigroupunderconvolution.Infact, M ( ) is evenamonoid(=semigroupwithidentity),sincetheidentityfunction δ = (δ1, δ2, . .. )ismultiplicativewith δ(n) = δ1n. (CAVEAT: M ( )is not closed underaddition!)
5.1.11Theorem. Defineamap φ : M ( ) → xK[[x]] (the monoidofpower serieswithzeroconstanttermundercomposition)by φ( f ) = Ef (x) = n≥1 f (n) xn n!
Then φ isananti-isomorphismofmonoids,thatis, φ isabijectionand φ( fg) = Eg (Ef (x)).
Proof. Clearly φ isabijection.Since fg ismultiplicativebyLemma 5.1.10,it sufficestoshowthat n≥1 fg(n) xn n! = Eg (Ef (x)).
