PATTERNSINSETPARTITIONSANDRESTRICTEDGROWTHFUNCTIONSBySamanthaDahlbergATHESISSubmittedtoMichiganStateUniversityinpartialentoftherequirementsforthedegreeofMathematics{DoctorofPhilosophy2016ABSTRACTPATTERNSINSETPARTITIONSANDRESTRICTEDGROWTHFUNCTIONSBySamanthaDahlbergInthisthesiswestudytworelatednotionsofpatternavoidance.Oneisinsetpartitions˙of[n]=f1;2:::;ngwhicharefamiliesofnonemptysubsetsB1;:::;Bkwhosedisjointunionis[n],written˙=B1=:::=Bk`S.Theotherisinrestrictedgrowthfunctions(RGFs)whicharewordsw=a1a2:::anofpositiveintegerssuchthata1=1andai1+maxfa1;:::;ai1gfori>1.TheconceptofpatternavoidanceisbuiltonastandardizationmapstonanobjectO,beitasetpartitionorRGF,wherest(O)isobtainedbyreplacingtheithsmallestintegerwithi.Asetpartition˙willcontainapatternˇif˙hasasubpartitionwhichstandardizestoˇ,andwhen˙doesnotcontainˇwesay˙avoidsˇ.PatternavoidanceinRGFsissimilarly.ThisworkisthestudyofthegeneratingfunctionsforWachsandWhite'sstatisticsonRGFsovertheavoidanceclassesofsetpartitionsandRGFs.Thehalfofthethesisconcentratesonsetpartitions.Wecharacterizemostofthesegeneratingfunctionsforavoidingsingleandmultiplesetpartitionsoflengththree,andwehighlightthelongerpattern14=2=3,apartitionof[4],asitsavoidanceclasshasaparticu-larlynicecharacterization.ThesecondhalfofthisthesiswillpresentourresultsaboutthegeneratingfunctionsforRGFpatterns,startingwiththoseoflengththree.Wemanyequidistributionpropertieswhichweproveusingintegerpartitionsandthehookdecompo-sitionofYoungdiagrams.Forcertainpatternsofanylengthweprovidearecursiveformulafortheirgeneratingfunctionsincludingthepattern12:::k.Wethispresentationbydiscussingthepatterns1212and1221whichhaveconnectionstononcrossingandnonnest-ingpartitions,respectfully.Weconnectionstotwo-coloredMotzkinpathsandexplicitbijectionsbetweenthesecombinatorialobjects.ACKNOWLEDGMENTSThroughoutallmyyearsofschooling,myfamilyhasbeenmycomfortandcheerleader.WithoutthemIwouldnotbehere.TomyfriendsIgivegreatthanks:TarahJensonandJohannaWeigandforwitandfun,myandrolemodelChristineLeeforbeingtrulymirthfulandthoughtful,CharlotteUreforsharingherintelligenceandmomentsofwhimsy,AkosNagyforbeingniceandpatientlyansweringallmyquestions,andAllisonGlassonwhoseindomitablespirithassupportedmethroughttryingstagesofthisjourney.AlsothankstoSamiMerhi,ReshmaMenon,andEylemYildiz.IwouldliketothankmyundergraduateinstructorsDr.PaulFishbackandDr.FeryalAlayontwhosememorablelessonshavestuckandinwhoseclassesIfeltlikeamathe-matician.IalsothankDr.AkaluTeferawhointroducedmetocombinatorics.Further,IwouldliketogiveagreatthankstoLindseyR.Campbell,RobertDorward,JonathanGerhard,ThomasGrubb,andCarlinPurcell,agroupofbrightundergraduates,andDr.BruceSagan,withwhomthisprojectwasdone.Wearenowcoauthorsofapublishedpaper[DDG+16]andhaveasecondpaperinprogress[DDG+].IwouldliketoexpressmygratitudetomydissertationcommitteeDr.MichaelShapiro,Dr.JonathanHall,Dr.PeterMagyar,andDr.RobertBellfromwhomIhavetakenenjoyableclasses.Lastly,IwouldliketogivespecialthankstomyadvisorDr.BruceSaganwhohasbeenmyteacher,sourceofinspiration,andmentor.iiiTABLEOFCONTENTSLISTOFTABLES....................................vLISTOFFIGURES...................................vi1Introduction......................................12Preliminaries.....................................42.1Setpartitionsandrestrictedgrowthfunctions.................42.2Patternavoidance.................................52.2.1PatternavoidanceinsetpartitionsandRGFs.............52.2.2Avoidanceclassesandcardinalitiesforpatternswiththreeelements.62.3Statisticsandgeneratingfunctions.......................83Setpartitions.....................................113.1Singlepatternsoflengththree..........................113.1.1Thepattern1=2=3............................113.1.2Thepattern1=23.............................143.1.3Thepattern13/2.............................153.1.4Thepattern12=3.............................173.1.5Thepattern123..............................213.2Multiplepatternavoidance............................283.3Thepattern14=2=3................................314Restrictedgrowthfunctions............................394.1Singlepatternsoflength3............................394.1.1Patternsrelatedtointegerpartitionsinarectangle..........394.1.2Patternsrelatedtointegerpartitionswithdistinctparts.......464.1.3Patternsnotrelatedtointegerpartitions................474.2RecursiveFormulaeandLongerWords.....................494.3Thepattern1212.................................544.3.1Noncrossingpartitions..........................544.3.2Combinationswithotherpatterns....................634.4Thepattern1221.................................674.4.1Nonnestingpartitions...........................674.4.2Thepattern1221byitself........................704.4.3Combinationswithotherpatterns....................784.4.4Moreaboutthepattern1212......................82REFERENCES......................................86ivLISTOFTABLESTable1Avoidanceclassesavoidingtwopartitionsof[3]andassociatedRGFs...27Table2AvoidanceclassesandassociatedRGFsavoidingthreeandfourpartitionsof[3].........................................30vLISTOFFIGURESFigure1TheYoungdiagramfor=(5;5;4;3;3)..................40Figure2TheYoungdiagramfor=(5;5;4;3;3)inthe65rectangle....41Figure3Thearcdiagramandleftarcdiagramforthepartition134=267=5.....69Figure4Two-coloredMotzkinpath..........................75vi1IntroductionTheworkinthisthesisitselfattheintersectionoftwolinesofresearch:oneonpatternavoidanceandtheotherongeneratingfunctions.Atthisintersection,mathematicianshavefoundmanyinterestingresultsandunexpectedconnectionsbetweenpreviouslyunrelatedobjects.Below,wewriteabouttheearlyresultswhichinspiredresearchinthesesummarizeourownresearch,andpresentsomeoftheunexpectedconnectionswefoundbetweencombinatorialobjects.Patternavoidancestartednotintheofmathematicsbutwithitsfounder,DonaldKnuth[Knu73],intheldofcomputerscience.Heinvestigatedstack-sortablepermutationsandfoundthatthepattern231wastheonlyobstruction.Forexample,thepermutation416325isnotstack-sortablebecauseitcontainsthesubword462whoseelementsareinthesamerelativeorderas231andsocountsasanoccurrenceofthatpattern.Whereas216354isstack-sortablesinceitavoids231inthatnothree-elementsubsequencehasitselementsinthisrelativeorder.Additionally,hefoundthatthenumberof231-avoidingpermutationslengthnisCn=1n+12nn,thenthCatalannumbernamedaftertheBelgianmathematicianEugeneCharlesCatalaninthe1800s.ThesearenumbersofgreatinterestandhaveovertwohundredcombinatorialinterpretationswhichcanbefoundinRichardStanley'sbook[Sta99]andhisaddendum[Sta].AmongthelistisanotherofKnuth'swhichisthatCnalsocountsthenumberoflengthnpermutationswhichavoidanysinglepatternoflengththree.Mathematiciansthenbegantocountandcharacterizepermutationswhichavoidlongerpatternsandmultiplepatterns.Inthe1980sRichardStanleyandHerbertWilfindependentlyformulatedwhatcametobeknownastheStanley-Wilfconjecture,whichproposedthatifSn(ˇ)isthecollectionoflengthnpermutationswhichavoidapermutationpatternˇthenlimn!1np#Sn(ˇ)isarealnumberdependingonˇ,where#Sn(ˇ)isthecardinalityoftheset.Thisisinstarkcontrasttothefullsymmetricgroupwhichhasamuchhighergrowthrate.Theconjecturehassincebeenprovedin2004byAdamMarcusandaborTardosin[MT04].Thesubjectgrewasmathematiciansconsideredsubclassesofpermutations1andvariouskindsofpatternavoidanceforothercombinatorialobjectsincluding,butnotrestrictedto,setpartitions,restrictedgrowthfunctions,even/oddpermutations,andinvolutions([Sag10],[Kla96],[JM08],[SS85]).Inourpreliminarychapter2,weallrelevanttermsforsetpartitionsandrestrictedgrowthfunctions.Thesecondlineofworkonwhichthisthesisbuildsisthestudyofgeneratingfunctions.Thoughnotthebeginningofthesubject,theearly1900ssawBritishMajorPercyMacMa-honprovearesultabouttheequalityoftwogeneratingfunctionsusingtwostatisticsonpermutations[Mac78].Oneofthesestatisticsisthemajorindex,ormajnamedafterhistitle,whichisonapermutationˇ=ˇ(1):::ˇ(n)tobemaj(ˇ)=Xˇ(i)>ˇ(i+1)iandtheotheristhenumberofinversions,orinv,asinv(ˇ)=#f(i;j):i<j;ˇ(i)>ˇ(j)g:Hefoundthatthegeneratingfunctionsoverallpermutationslengthnusinginvandmajwerethesame,Xˇ2Snqmaj(ˇ)=Xˇ2Snqinv(ˇ);andanyotherstatisticwithanequivalentdistribution(thatis,anequalgeneratingfunction)iscalledMahonian.ThisresultwaslaterprovenbijectivlybyDominiqueFoata[Foa68].ThesefunctionsareequaltotheGaussianq-analogueforn!,equation(10).SeeStanley'sbook[Sta97]fordetails.Onecancombinethesetwolinesofworkbyconsideringgeneratingfunctionsforvariousstatisticsoveranavoidanceclassofpermutationsratherthanoverthefullsymmetricgroup.Dokoset.al.[DDJ+12]werethetomakeacomprehensivestudyofthestatisticsmajandinvoveravoidanceclassesoflengththreepatternsandfoundconnectionstolattice2paths,integerpartitions,andFoata'ssecondfundamentalbijection.Thisthesisconsiderspatternavoidanceinsetpartitionsandrestrictedgrowthfunctionswhichwillbeshortly.Onthesetwosetsofobjects,whichareinbijectionwitheachother,wetwonotionsofpatternavoidance.ThegeneratingfunctionsweconsideruseWachsandWhite's[WW91]fourfundamentalstatisticsonrestrictedgrowthfunctions.ThroughoutthepaperweintroduceGaussianpolynomials,Youngdiagrams,integerparti-tions,andtwo-coloredMotzkinpathssincetheseobjectswillbeessentialforsomeproofs.Therestofthisthesisisstructuredasfollows.WestartbypresentingourresultsaboutsetpartitionsinChapter3.OurstudyfullycharacterizesthegeneratingfunctionsforallfourofWachsandWhite'sstatistics[WW91]overtheavoidanceclassesforsingleandmultiplepatternsoflengththreeexceptforthesinglepattern123whichweonlypartiallycharacterize.Thelongerpattern14=2=3,apartitionof[4],hasitsownsection3.3duetoitsparticularlynicecharacterization.WethenproceedtopresentingourresultsaboutRGFsinChapter4.Wenoteattheendofthepreliminarysection2.2.2thatpatternavoidanceforsetpartitionsandRGFsisthesameforsomepatterns.InSection4.1wecharacterizegeneratingfunctionfortheremaininglengththreepatternsv=112;122.WemanyequidistributionpropertieswhichweproveusingintegerpartitionsandthehookdecompositionofYoungdiagrams.InSection4.2weprovidearecursiveformulawhichcangeneratefunctionsforcertainRGFpatternsofanylengthincludingthepattern12:::k.Wethispresentationbydiscussingthepatterns1212and1221inSections4.3and4.4,whichhaveconnectionstononcrossingandnonnestingpartitions,respectfully.Wefurtherpresenttheirconnectiontotwo-coloredMotzkinpathsbyexplicitbijectionsbetweenthesecombinatorialobjects.32Preliminaries2.1SetpartitionsandrestrictedgrowthfunctionsLetusbeginbyourterms.ConsiderasetS.Asetpartition˙ofSisafamilyofnonemptysubsetsB1;:::;BkwhosedisjointunionisS,written˙=B1=:::=Bk`S.TheBiarecalledblocksandwewillusuallysuppressthesetbracesandcommasineachblockforreadability.Wewillbeparticularlyinterestedinsetpartitionsof[n]:=f1;2;:::;ngandwillusethenotationn=f˙:˙`[n]g:Toillustrate˙=145=2=3`[5].IfTSand˙=B1=:::=Bk`Sthenthereisacorrespondingsubpartition˙0`TwhoseblocksarethenonemptyintersectionsBi\T.Tocontinueourexample,ifT=f2;4;5gthenwegetthesubpartition˙0=2=45`T.Ourotherobjectsofinterestarerestrictedgrowthfunctions.Asequencew=a1a2:::anofpositiveintegersisarestrictedgrowthfunction(RGF)ifittheconditions1.a1=1,and2.fori2wehaveai1+maxfa1;:::;ai1g:(1)Forexample,w=11213224isanRGF,butw=11214322isnotsince4>1+maxf1;1;2;1g.Thenumberofelementsofwiscalleditslengthanddenotedjwj.Rn=fw:wisanRGFoflengthng:ThereisabijectionbetweenRGFsandsetpartitions.Todescribeit,wewillhenceforthwriteall˙=B1=B2=:::=Bk`[n]instandardformwhichmeansthatminB1<minB2<<minBk:4NotethatthisimpliesminB1=1.Given˙=B1=:::=Bk`[n]instandardform,weconstructanassociatedwordw(˙)=a1a2:::anwhereai=jifandonlyifi2Bj.Returningtoourrunningexample,wehavew(145=2=3)=12311.Moregenerally,foranysetPofsetpartitions,weletw(P)denotethesetofw(˙)for˙2P.Proposition2.1.Ifapartition˙`[n]iswritteninstandardform,thenw(˙)isanRGFandthemap˙7!w(˙)isabijectionn!Rn.2.2Patternavoidance2.2.1PatternavoidanceinsetpartitionsandRGFsTheconceptofpatternisbuiltonthestandardizationmap.LetObeanobjectwithlabelswhicharepositiveintegers.ThestandardizationofO,st(O),isobtainedbyreplacingalloccurrencesofthesmallestlabelinOby1,alloccurrencesofthenextsmallestby2,andsoon.Saythat˙`[n]containsˇasapatternifitcontainsasubpartition˙0suchthatst(˙0)=ˇ.Inthiscase˙0iscalledanoccurrenceorcopyofˇin˙.Otherwise,wesaythat˙avoidsˇandletn(ˇ)=f˙2n:˙avoidsˇg:Inourrunningexample,˙=145=2=3containsˇ=1=23sincest(2=45)=1=23.But˙avoids12=3becauseifonetakesanytwoelementsfromtheblockof˙thenitisimpossibletoanelementfromanotherblockbiggerthanbothofthem.Klazar[Kla96,Kla00a,Kla00b]wasthetostudythisapproachtosetpartitionpatterns.WecannowpatternsintermsofRGFs.GivenRGFsv;wwecallvapatterninwifthereisasubwordw0ofwwithst(w0)=v.Bysubwordwemeananysubsequenceai1ai2:::aikofw=a1:::anwheretheij'sareincreasingandnotnecessarilyconsecutive.5Theuseoftheterms\occurrence,"\copy,"and\avoids"inthissettingarethesameasforsetpartitions.GivenandRGFvweletRn(v)=fw2Rn:wavoidsvg:Asbefore,considerw=w(145=2=3)=12311.Thenwcontainsv=121becauseeitherofthesubwords121or131ofwstandardizetov.However,wavoidsv=122sincetheonlyrepeatedelementsofwareones.Notethatthisisincontrasttothefactthat145=2=3contains1=23wherew(1=23)=122.GivenasetSofsetpartitionswewritew(S)=fw(s):s2Sg:Thenextresultconnectsthesetwonotionsofpatternavoidance.Proposition2.2.Supposethatpartitionsˇand˙haveRGFsv=w(ˇ)andw=w(˙).Ifwcontainsvthen˙containsˇ,butnotnecessarilyconversely.Equivalently,wehaveRn(v)wn(ˇ)).2.2.2AvoidanceclassesandcardinalitiesforpatternswiththreeelementsSagan[Sag10]describedthesetpartitionsinn(ˇ)foreachˇ23.WeincludehisresulttranslatedintothelanguageofRGFs.Foraproofpleasesee[Sag10].Tostatehisresult,wewillneedsomeons.TheinitialrunofanRGFwisthelongestoftheform12:::m.Writealtoindicateastringoflcopiesoftheintegera.Callthewordwlayeredifithastheformw=1n12n2:::mnm,equivalently,ifitisweaklyincreasing.ForapartitionpatternˇwewillsometimeswriteRn(ˇ)forwn(ˇ)):Theorem2.3([Sag10]).Forn1,wehavethefollowingcharacterizations.1.Rn(1=2=3)=fw2Rn:wconsistsofonly1sand2sg.2.Rn(1=23)=fw2Rn:wisobtainedbyinsertingasingle1intoaword6oftheform1l23:::mforsomel;m1:3.Rn(13=2)=fw2Rn:wislayeredg.4.Rn(12=3)=fw2Rn:whasinitialrun1:::mandam+1==anmg.5.Rn(123)=fw2Rn:whasnoelementrepeatedmorethantwiceg.Usingthesecharacterizations,itisasimplemattertothecardinalitiesoftheavoid-anceclasses.Corollary2.4([Sag10]).Wehavethefollowingcardinalities.n(1=2=3)=n(13=2)=2n1;n(1=23)=n(12=3)=1+n2;n(123)=Xk0n2k(2k)!!where(2k)!!=(1)(3)(5):::(2k1).SaganalsodescribedthesetsRn(v)forallv2R3,andtheproofcanbefoundinhispaper[Sag10].Theorem2.5([Sag10]).Wehavethefollowingcharacterizations.1.Rn(111)=fw2Rn:everyelementofwappearsatmosttwiceg.2.Rn(112)=fw2Rn:whasinitialrun12:::mandmam+1am+2ang.3.Rn(121)=fw2Rn:wislayeredg.4.Rn(122)=fw2Rn:everyelementj2ofwappearsonlyonceg.5.Rn(123)=fw2Rn:wcontainsonly1sand2sg.Usingthisresult,itisnothardtocomputethecardinalitiesoftheclasses.7Corollary2.6([Sag10]).Wehave#Rn(112)=#Rn(121)=#Rn(122)=#Rn(123)=2n1and#Rn(111)=Xi0n2i(2i)!!where(2i)!!=135:::(2i1).AsnotedinProposition2.2,ifv=w(ˇ)thenwealwayshaveRn(v)wn(ˇ)).Butforcertainˇwehaveequality.Inparticular,asshownin[Sag10],thisistrueforˇ=123;13=2;1=2=3andthecorrespondingv=111;121;123.2.3StatisticsandgeneratingfunctionsOurobject,inpart,istoprovegeneralizationsoftheformulaeincorollaries2.4and2.6usingthestatisticsofWachsandWhiteandtheirgeneratingfunctions.TheyfourstatisticsonRGFsdenotedlb,ls,rb,andrswherethelettersl,r,b,andsstandforleft,right,bigger,andsmaller,respectively.Wewillexplicitlythelbstatisticandtheothersareanalogously.Givenawordw=a1a2:::an,letlb(aj)=#fai:i<jandai>ajg:Otherwiseput,lb(aj)countsthenumberofintegerswhicharetotheleftofajinwandbiggerthanaj.Notethatmultiplecopiesofthesameintegerwhichisleftofandbiggerthanajareonlycountedonce.Note,also,thatlb(aj)alsodependsonwandnotjustthevalueofaj.Butcontextwillensurethatthereisnoconfusion.Foranexample,ifw=12332412thenfora5=2wehavelb(a5)=1sincethreeistheonlylargerintegerwhichoccursbefore8thetwo.Forwitself,lb(w)=lb(a1)+lb(a2)++lb(an):Continuingourexample,lb(12332412)=0+0+0+0+1+0+3+2=6:Finally,givenanRGF,v,weconsiderthegeneratingfunctionLBn(v)=LBn(v;q)=Xw2Rn(w)qlb(w)andsimilarlyfortheotherthreestatistics.SometimeswewillbeabletoprovethingsaboutmultivariategeneratingfunctionssuchasFn(v)=Fn(v;q;r;s;t)=Xw2Rn(v)qlb(w)rls(w)srb(w)trs(w):Similarly,wecanWachsandWhite'sstatisticsforsetpartitionswhereforasetpartitionˇ`[n]welbofˇtobeequaltolb(w(ˇ)).Tosimplifynotation,wewillwritelb(ˇ)forthemorecumbersomelb(w(ˇ)).WesimilarlygeneratingfunctionsLBn(ˇ)=LBn(ˇ;q)=X˙2n(ˇ)qlb(˙)andanalogouslyfortheotherstatistics.Again,often,wewillevenbeabletocomputethemultivariategeneratingfunctionFn(ˇ)=Fn(ˇ;q;r;s;t)=X˙2n(ˇ)qlb(˙)rls(˙)srb(˙)trs(˙):ThoughweusesimilarnotationforbothsetpartitionsandRGFSthereshouldbenocon-9fusionsinceeitherˇorvwillbeinsidetheparentheseswhichwillindicatetheintendedfunction.103SetpartitionsInthischapterwepresentourresultsaboutsetpartitions.WecharacterizethegeneratingfunctionsforallfourWachsandWhitestatisticsonalllengththreepatternsexcept123wherewehaveonlypartialresults.WemanyequidistributionpropertiesoftheformLBn(ˇ)=RSn(ˇ)forˇ2f1=2=3;1=23;13=2;14=2=3gandLSn(ˇ)=RBn(ˇ)forˇ2f1=2=3;13=2g.Also,wedequidistributionbetweenavoidanceclassesusingtpatternssuchasLBn(1=23)=RSn(12=3)andLSn(1=23)=RBn(12=3).ThisisathemewealsowhenstudyingRGFsinChapter4.Thecharacterizationforpartitionsintheavoidanceclassof14=2=3haveaparticularlyniceformwhichaidsusinshowingthatLBn(14=2=3;ˇ)=RSn(14=2=3;ˇ)forˇ2f13=2=4;1=2=:::=tg.3.1Singlepatternsoflengththree3.1.1Thepattern1=2=3Weconsiderthesetpartition1=2=3.Webeginbypresentingthefour-variablegenerat-ingfunctionfromwhichwederivethegeneratingfunctionsassociatedwitheachindividualstatistic.Theorem3.1.WehaveFn(1=2=3)=1+n1Xl=1rnlsl+n1Xl=2nl1Xk=0Xi;j1nijk2lijqlirnlslk;0jtnlkwherek;0istheKroneckerdeltafunction.Proof.ByTheorem2.3,anywordw2Rn(1=2=3)iscomposedsolelyofonesandtwos.Letldenotethenumberofonesinw.Ifsuchawordisweaklyincreasing,itiseasytoseethatthesewordscontribute1+n1Xl=1rnlsl11tothegeneratingfunction.Otherwise,letwhaveatleastonedescentandlones.Wecanseethatthewordwhastheform1iw01j2k,wherei;j1,thesubwordw0beginsandendswithatwo,and0knl1.Forsuchwthelbstatisticisgivenbythenumberofonesafterthetwo,thatis,bythenumberofonesnotin1i.Thus,lb(w)=li.Thelsstatisticisgivenbythetotalnumberoftwosinw,namelynl.Fortherbstatistic,ifkisnon-zero,theneachoneinwcontributestothestatistic.Otherwise,onlytheonesthatarenotin1jcontribute.Combiningthetwocasesgivesrb(w)=lk;0j.Finally,thersstatisticisgivenbythenumberoftwosinw0,namelynlk.Puttingallfourstatisticstogetherproducesqlb(w)rls(w)srb(w)trs(w)=qlirnlslk;0jtnlk:Choosingthenumberofwaysofarrangingtheonesinw0givesacotofnijk2lij:Summingoveri;j;k;landcombiningthecasesgivesourdesiredpolynomial.Theequationsinthefollowingcorollarycanbederivedeitherbyspecializationofthefour-variablegeneratingfunctioninTheorem3.1andstandardhypergeometricseriestechniquesorbyusingtheideasintheproofofthepreviousresultandignoringtheotherthreestatistics.Corollary3.2.WehaveLBn(1=2=3)=RSn(1=2=3)=1+n2Xk=0n1k+1qk;andLSn(1=2=3)=RBn(1=2=3)=(r+1)n1:12Inviewoftheprecedingcorollary,itwouldbenicetoexplicitbijections˚:Rn(1=2=3)!Rn(1=2=3)and :Rn(1=2=3)!Rn(1=2=3)suchthat˚takeslbtorsand takeslstorb.Inthenexttwopropositions,wepresentsuchbijections.Proposition3.3.Thereexistsanexplicitbijection˚:Rn(1=2=3)!Rn(1=2=3)suchthatforv2Rn(1=2=3),lb(v)=rs(˚(v)):Proof.Letv=a1a2:::an2Rn(1=2=3).˚(v)=a1(3an)(3an1):::(3a3)(3a2):Becausev2Rn(1=2=3),byTheorem2.3,itmustbecomposedofonlyonesandtwosandbeginwithaone.Itisclearthat˚(v)hasthesameform,so˚iswellAlso,˚isitsowninverseandisthereforeabijection.Iflb(v)=k,thenvmustcontainasubwordv0=21kandnosubwordoftheform21l,withl>k.Infact,thisconditionisclearlyequivalenttolb(v)=k.Itfollowsthat˚(v0)=2k1isasubwordof˚(v)and˚(v)hasnosubword2l1withl>k.Therefore,rs(˚(v))=k=lb(v),asdesired.Proposition3.4.Thereexistsanexplicitbijection :Rn(1=2=3)!Rn(1=2=3)suchthatforv2Rn(1=2=3),ls(v)=rb( (v)):Proof.Letv2Rn(1=2=3).Ifv=1n,then (v)=v.Clearlyinthiscasels(v)=0=rb(v).Otherwise,letv=a1a2:::ai1ai1niwhereai=2andni0. (v)=(3ai)(3ai1):::(3a2)(3a1)1ni:TheproofisnowsimilartothatofProposition3.3,usingthefactthatthe1niattheend13ofvcontributestoneitherlsorrb.3.1.2Thepattern1=23InthissectionwewilldetermineFn(1=23),andthusthegeneratingfunctionsforallfourstatistics.Wewillthatlbandrsareequalforanyw2Rn(1=23).Theorem3.5.WehaveFn(1=23)=(rs)(n2)+n1Xm=1mXj=1(qt)j1r(m2)s(nm)(m1)+mj+(m12):Proof.If˙avoids1=23weknowfromTheorem2.3thattheassociatedRGFisobtainedbyinsertingasingle1intoawordoftheform1l23:::mforsomel0andm1.Ifl=0thentheinserted1mustbeatthebeginningofthewordinorderforwtobeaRGF,sow=12:::n.Ifl>0thentheinserted1canbeinsertedafterjforany1jm,andthemaximalletterm1mn1.Ifwhasmaximallettermandweinsertthe1afterjthenwiscompletelydeterminedtobe1nm23:::j1:::m.Insummary,eitherw=12:::norwisdeterminedbythechoiceof1jmand1mn1.Ifw=12:::nthenrb(w)=ls(w)=n2andlb(w)=rs(w)=0.Forallotherwwehavethefollowing:1.lb(w)=j1,2.ls(w)=m2,3.rb(w)=(nm)(m1)+mj+m12,and4.rs(w)=j1.1.Onlytheinserted1haselementswhichareleftandbiggerwhicharethenumbers2throughj.Solb(w)=j1.142.SincewisanRGFeverylettericontributesi1tothelsgivingatotalofls(w)=1++(m1)=m2.3.Therstnmonesofweachhavem1elementswhicharerightandbigger,sotheycontribute(nm)(m1)totherb.Theinserted1hasmjletterswhicharerightandbigger.Anyelementisuchthat2imappearsonlyonceandcontributesmitotherb.Thismeanswehaveanadditional(m2)++0=m12.Hencerb(w)=(nm)(m1)+mj+m12.4.Theonlyelementswhichhaveanumberrightandsmalleraretheelements2throughj,andtheonlynumberwhichisrightandsmalleroftheseelementsistheinserted1.Hencers(w)=j1.Summingoverallthevalidvaluesformandjgivesusourequality.ThefollowingresultcanbequicklyseenbyspecializingTheorem3.5oritsdemonstration,sowehaveomittedtheproofs.Corollary3.6.Wehavelb(w)=rs(w)forallwordsw2Rn(1=23)andLBn(1=23)=RSn(1=23)=1+n1Xj=1(nj)qj1:AlsoLSn(1=23)=r(n2)+n1Xm=1mr(m2);andRBn(1=23)=s(n2)+n1Xm=1mXj=1s(nm)(m1)+mj+(m12):3.1.3Thepattern13/2Inthissection,webeginbyevaluatingthefour-variablegeneratingfunctionFn(13=2).GoytandSagan[GS09]havepreviouslyprovenatheoremregardingthesingle-variablegeneratingfunctionsforthelsandrbstatistics,andwewilladapttheirmapandprooftoobtain15themulti-variategeneratingfunctionfor13=2.Thisgeneratingfunctioniscloselyrelatedtointegerpartitions.Areversepartition=(1;2;:::;k)ofanintegertisaweaklyincreasingsequenceofpositiveintegerssuchthatPki=1i=t.Theiarecalledparts.Additionally,wewillanintegerpartitionn=(nk;:::n2;n1).Letjj=Pki=1i.WewilldenotebyDn1thesetofreverseintegerpartitionswithdistinctpartsofsizeatmostn1.Theorem3.7.WehaveFn(13=2)=n1Yi=1(1+rnisi):Proof.Supposew2Rn(13=2).ByTheorem2.3,wislayeredandsolbandrsarezero,resultinginnocontributiontothegeneratingfunction.Fortheothertwostatistics,sincewislayeredithastheformw=1n12n2:::mnmwheremisthemaximumelementofw.˚:Rn(13=2)!Dn1by˚(w)=(1;2;:::;m1)wherej=Pji=1nifor1jm1.Notethatsincethenjarepositive,thejaredistinct,increasing,andlessthannsincethesumneverincludesnm.ThusthemapiswellWenowshowthat˚isabijectionbyconstructingitsinverse.Given=(1;2;:::;m1),considerfor1jm,thenj=jj1,wherewe0=0andm=n.Itiseasytoseethatsendingtow=1n12n2:::mnmisawellinversefor˚.Wenextclaimthatif˚(w)=thenrb(w)=jj.Indeed,fromtheformofwandweseethatrb(w)=m1Xi=1ni(mi)=m1Xj=1jXi=1ni=jj:Similarlyweobtainls(w)=jnj.ItfollowsthatFn(13=2)=X2Dn1rjnjsjj=n1Yi=1(1+rnisi)16asdesired.ThegeneratingfunctionofeachindividualstatisticiseasytoobtainbyspecializationofTheorem3.7sowehaveomittedtheproofs.Corollary3.8([GS09]).WehaveLBn(13=2)=2n1=RSn(13=2)andLSn(13=2)=n1Yi=1(1+qi)=RBn(13=2):3.1.4Thepattern12=3Inthissection,wedetermineFn(12=3).Theotherpolynomialsassociatedwith12=3areob-tainedascorollaries.Wethisavoidanceclassinterestingbecauseitleadstoaconnectionwithnumbertheory.Theorem3.9.WehaveFn(12=3)=(rs)(n2)+n1Xm=1mXi=1q(nm)(mi)r(m2)+(nm)(i1)s(m2)tmi:(2)Proof.ByTheorem2.3,theelementsofRn(12=3)arethewordsoftheformw=123:::minmwhereim.Ifw=123:::nthenls(w)=rb(w)=n2andlb(w)=rs(w)=0.Otherwisem<n.Inthiscase,wewillshowthefollowing:1.lb(w)=(nm)(mi),2.ls(w)=m2+(nm)(i1),173.rb(w)=m2,4.rs(w)=mi.1.Therearenmcopiesofiinwaftertheinitialrunandthesearetheonlyelementscontributingtolb.Eachofthesei'shastheelements(i+1)(i+2):::mtoitsleftthatarebiggerthanit.Solb(i)=miforallsuchiandlb(w)=(nm)(mi).2.Eachelementwjofwhasls(wj)=wj1bycondition(1).Usingthisandtheformofweasilyyieldsthedesiredequality.3.Thisissimilartothepreviouscase,notingthatonlytheinitialrunofwcontributestorb.4.Wecanseethattheonlyelementswjwithrs(wj)>0willbethoseintheinitialrunsuchthatwj>i.Thesearepreciselytheelements(i+1)(i+2):::mandeachelementhasexactlyoneelementtoitsrightthatissmallerthanit.Sors(w)=mi.Summingoverthevalidvaluesofmandi,wehave(2).Thenextcorollaryfollowseasilybyspecializationof(3.9).Corollary3.10.WehaveLSn(12=3)=r(n2)+n1Xm=1mXi=1r(m2)+(nm)(i1);andRBn(12=3)=s(n2)+n1Xm=1ms(m2);aswellasRSn(12=3)=1+n2Xk=0(nk1)tk:ThecotsofLBn(12=3)haveaninterestinginterpretation.18Proposition3.11.WehaveLBn(12=3)=b(n1)2=4cXk=0Dkqk;(3)whereDk=#fd1:djkandd+kd+1ng.Proof.Setr=s=t=1in(2).WebeginbyshowingthedegreeofLBn(12=3)isb(n1)2=4c.Ifw2Rn(12=3)then,byTheorem2.3,wehavew=12:::minmforsomemandim.Inordertomaximizethelb(w),wecanassumei=1.So,usingtheformulaforlb(w)derivedintheproofofTheorem3.9,wemustmaximize(nm)(m1).Wetakethederivativewithrespecttomandsettheequationequaltozerotoobtainn2m+1=0andm=n+12.Togetintegervaluesofm,weobtain8>><>>:m=n+12ifnisodd;m=n+12orn+12ifniseven.(4)Ineithercase,themaximumvalueoflbisb(n1)2=4c.WenowshowthecotofqkisDk.Asbefore,letw=123:::minmbeawordassociatedwithasetpartitionthatavoids12=3andletlb(w)=k.Ifweletd=nmbethenumberofi's,itisclearthatlb(w)=d(mi)=kandtherefore,mi=kd.Becausewmustbeoflengthn,wenowmustdeterminewhichdivisorsdofkarevalid.Eachofthedtrailingi'shaskdelementstoitsleftandbigger.Becausei1,theleadingonecannotbesuchanelement.Thusinorderforwtobeoflengthnwemusthaved+kd+1n.TheaboveformulationofLBn(12=3)leadstothefollowingcorollary,showingaconnectiontonumbertheory.Corollary3.12.Whenkn2,wehaveDk=˝(k),thenumber-theoreticfunctionwhichcountsthedivisorsofk.19Proof.Weshowthatifkn2thenallpositivedivisorsdofkarevalid.Weknowthatd+kdk+1becaused=1andd=karethedivisorsofkwhichmaximized+kd.Thus,wehaved+kd+1k+2n.ThereforeeverypositivedivisorofktheinequalityintheofDk,andthisimpliesDk=˝(k).Forourresultofthissection,weprovidetwointerestingrelationshipsbetweentheavoidanceclasses=23)and=3).Proposition3.13.Forn0,wehavethefollowingequalities:LBn(1=23)=RSn(12=3);LSn(1=23)=RBn(12=3):Proof.WewillprovethistheorembyprovidingabijectionthatmapsfromRn(1=23)toRn(12=3).Thisbijectionwillinterchangethelbandrsstatistics,aswellasthelsandrbstatistics.LetwbeanelementofRn(1=23).ByTheorem2.3,weknowthatwisoftheform1l23:::m,withpossiblyasingleoneinserted.Letjbethenumberofonesinw,andletibetheindexoftherightmostoneinw.We˚:Rn(1=23)7!Rn(12=3)as˚(w)=123:::(nj+1)(ni+1)j1:FromthecharacterizationofRn(12=3)providedinTheorem2.3,itfollowsthat˚(w)isindeedcontainedinRn(12=3).Furthermore,byCorollary2.4weknowthat#Rn(1=23)=#Rn(12=3).Itisalsoimmediatethat˚isinjective,whichthengivesthat˚isabijection.Nowweshowthat˚takesthelbstatistictothersstatistic.First,notethatifwisamemberofRn(1=23)withlb(w)=0,thenwmustbeoftheformw=1l23:::(nl+1);forsomelwith1ln.Inthiscasei=j=l.Thereforewhenweapply˚,weareleft20with˚(w)=123:::(nl+1)(nl+1)l1;anditfollowsthatrs(˚(w))=0.Nowconsiderthecasewherelb(w)=k,fork>0.Inthisinstance,wmustbeoftheformw=1l23:::(k+1)1(k+2):::(nl):Itfollowsthattherightmostoneinwhasindexl+k+1,andthattherearel+1onesinw.Thuswhenweapply˚,weget˚(w)=123:::(nl)(nlk)l;whichrs(˚(w))=k.Finally,weshowthat˚takesthelsstatistictotherbstatistic.FromtheproofofTheorem3.5,weknowthatifw2Rn(1=23)withmaximumvaluem,thenls(w)=m2.Similarly,fromtheproofofTheorem3.9,ifw02Rn(12=3)withmaximumvaluem0,thenrb(w)=m02.Since˚preservesmaximumvalues,itfollowsthatls(w)=rb(˚(w)).3.1.5Thepattern123Thereaderwillhavenoticedthatfortheotherfoursetpartitionsof[3],weprovideda4-variablegeneratingfunctiondescribingallfourstatisticsontheavoidanceclassofthosepartitions.Thepattern123,however,ismuchmoretodealwithandsowewillcontentourselveswithresultsabouttheindividualstatistics.NotethatTheorem4.18givesusanalternativemethodforcomputingLSn(123)andRSn(123)(usingthecorrespondingRGF111)viarecursion.Wewillstartwiththeleft-smallerstatistic.21Theorem3.14.WehaveLSn(123)=nXm=dn=2e"XL nmYg=1(m`g+g)!q(m2)+P`2L(`1)#(5)wheretheinnersumisoverallsubsetsL=f`1;`2;:::;`nmgof[m]with`1>>`nm.Proof.Westartbynotingthatifthemaximumvalueofanelementofawordism,thentheremustbenmrepeatedelementsintheword,i.e.,elementsithatappearaftertheinitialoccurrenceofi.Theboundsonouroutersumaregivenbythelargestpossiblevalueofmbeingn,andthesmallestpossiblevalueofmbeingdn=2e,sincewecanrepeateachelementamaximumoftwotimes.Wewillnowbuildourwordwbystartingwithabasesequence12:::mandaddinginrepeatedelements.Thebasesequencewillcontribute1+2++(m1)=m2tols(w).LetLbethesetofrepeatedelementswewanttoaddtow.ThenLmustcontainnmelementsfrom[m],andsincewcanhavenoelementappearmorethantwice,Lcanhavenoelementappearmorethanonce.Foreachelement`2Lthatweaddtoourbasesequence,wewillincreasels(w)by`1.Soforanywordwwithmaximummformedinthisway,wehavels(w)=m2+P`2L(`1).Tohowmanypossiblewordscanbesocreated,westartwithourbasesequence12:::m,andbuildupourwordbyplacingintherepeatedelementsfromLoneatatime.Therearem(`11)spotswherewecanplacethelargestrepeatedelement,`1:anywhereaftertheoriginaloccurrenceof`1.Thenwhenweplaceoursecondrepeatedelement,`2,wewillhavem(`21)+1spots,wheretheplusonecomesfromtheextraspacetherepeatedelementaddedinfrontof`2.Ingeneral,whenweplace`gwewillhavem(`g1)+(g1)=m`g+gplacestoputit.Thecondition`1>>`nmisusedsinceitimpliesthatregardlessofwhere`iisplaced,onewillhavethesamenumberofchoicesfortheplacementof`i+1.MultiplyingallthesetermstogetherandthensummingoverallpossiblesubsetsLof[m]givesusthecotofq.Finally,summingoverallpossiblemaximumsofthewordsintheavoidanceclassgivesusequation(5).22Forcomparison,weincludeheretherecursionobtainedbyspecializingTheorem4.18.Corollary3.15.WehaveLS0(123)=LS1(123)=1andforn>1LSn(123)=qn1LSn1(123)+(n1)qn2LSn2(123)Wewereonlyabletoexplicitexpressionsforcertaincotsofthepolynomialsgeneratedfromotherstatistics.Wewillnowlookattheleft-biggerstatistic.Theorem3.16.Wehavethefollowing.1.ThedegreeofLBn(123)isn(n1)6:2.TheleadingcoofLBn(123)is8>><>>:k!ifn=3kor3k+1;(k+2)k!ifn=3k+2;forsomenonnegativeintegerk.Proof.Wewillshowthatawordoftheformw=12:::iwi+1:::wnwithwi+1;:::;wnbeingapermutationoftheinterval[1;ni]willprovideamaximumlbwhichisb(n(n1))=6c.Firstwewillprovethattheelementsaftertheinitialrun12:::imustbelessthanorequaltoi.Notethat,bydeoftheinitialrun,wi+1i.Nowsuppose,towardsacontradiction,thatforsomej2[i+2;n],therewassomeelementwj>i.Then,sincewisanRGF,wemusthavewk=i+1forsomek2[i+2;j].Butbyswitchingwkandwi+1,wewouldincreaselbbyatleastonesincewi+1i.Soifanyelementaftertheinitialrunisgreaterthani,lbisnotmaximum.Nextwewillshowthattheelementsaftertheinitialrunhavetobeexactlythoseintheinterval[1;ni],uptoreordering.Supposetowardscontradictiontherewassomeelementt2[1;ni]thatdidnotappearinthesequenceaftertheinitialrun,andinsteadthere23appearedsomeelements2[ni+1;i].Thenlb(s)=is.Butlb(t)=it,andsinces>t,itfollowsthatlb(t)>lb(s).Therefore,ifwewanttomaximizelb,wemusthavethesequenceaftertheinitialrunbeingexactlytheinterval[1;ni],uptoreordering.Nowthatwe'veestablishedthatourwordisoftheformw=12:::iwi+1:::wnwithwi+1;:::;wnbeingexactlythoseelementsintheinterval[1;ni],wesimplyneedtomaximizelbusingsomeelementarycalculusasfollowslb(w)=(iwi+1)+(iwi+2)++(iwn)=(i1)+(i2)++(2in)=(4n+1)i3i2n2n2:(6)Consideringiasarealvariableandtiatinggivesusthemaximumvalueoflb(w)wheni=(4n+1)=6.Wemustmodifythisslightlysincewewantitobeintegral.Roundingitothenearestintegergivesi=8>>>>>><>>>>>>:4n+16ifn=3k;4n+16ifn=3k+1;4n+16or4n+16ifn=3k+2;forsomenonnegativeintegerk.Pluggingeachvalueofnandibackintoequation(6)givesusanlbofb(n(n1))=6cinallcases.Aswe'vementionedbefore,theelementswi+1;:::;wnmustbeexactlythoseintheinterval[1;ni],buttheorderingdoesn'tmatter.ThismeanstheleadingcotofLBn(123)willbepreciselythenumberofwaystopermutethenielementsaftertheinitialrun.Thisgivesusoursecondresult.SomeofthefollowingtheoremswillinvolveFibonaccinumbers.Recallthatthenth24FibonaccinumberFnisrecursivelyasFn=Fn1+Fn2withinitialconditionsF0=1andF1=1.Theorem3.17.Wehavethefollowingco1.TheconstanttermofLBn(123)isFn.2.ThecoofqinLBn(123)is(n2)Fn2.Proof.Iflb(˙)=0,thenw=w(˙)mustbelayered.LetL(n)bethesetoflayeredwordsw(˙)with˙2n(123).ItfollowsthattheconstanttermofLBn(123)is#L(n).Li(n)=fw2L(n)jwstartswithionesg.Then#L(n)=#L1(n)+#L2(n).But#Li(n)=#L(ni)fori=1;2,sinceifwbeginswithionesthentherestofthewordisessentiallyalayeredwordwithnielements.Therefore,#L(n)=#L(n1)+#L(n2).Since#L(0)=1and#L(1)=1,wehave#L(n)=Fn.Toprovethesecondclaim,letw2Rn(123)withlb(w)=1.Thentheremustbeexactlyonedescentinwanditmustbeoftheformwj+1=wj1forsome2jn1.Removingwjandwj+1fromwandthensubtractingonefromallwkwithk>j+1givesanelementw02Rn2whichislayered.So,fromthepreviousparagraph,thereareFn2choicesforw0.Further,thereweren2choicesforjandsothetotalnumberofwis(n2)Fn2.Wewillnowlookattheright-smallerstatistic.Theorem3.18.Wehavethefollowing.1.ThedegreeofRSn(123)is(n1)24:2.TheleadingcoofRSn(123)is1whennisodd,and2whenniseven.253.TheconstanttermofRSn(123)isFn.Proof.TheproofoftheresultisverysimilartotheproofofthedegreeofLBn(123).Whenlookingattheright-smallerstatistic,thewordthatmaximizesrsisoftheformw=12:::i(ni):::21,where12:::iistheinitialrun.Calculatingrs(w)givesrs(w)=(ni)(i1);(7)andtiatingwithrespecttotherealvariableiandmaximizinggivesi=(n+1)=2.Sincewewantitobeintegral,wehavei=8>><>>:n+12ifnisodd,n+12orn+12ifniseven.Pluggingeachvalueofiandninto(7)givesb(n1)2=4cinbothcases.Also,thenumberofchoicesforigivestheleadingcotofRSn(123).TheprooffortheconstanttermofRSn(123)isthesameasforLBn(123)sinceforanywwehavers(w)=0ifandonlyiflb(w)=0.Again,sincewn(123))=Rn(111)wehavethefollowingcorollaryforTheorem4.18wheretheGaussianq-analogue[n]qisinequation(9).Corollary3.19.WehaveRS0(123)=1andforn1RSn(123)=RSn1(123)+[n1]qRSn2(123):OurresultofthissectiongivesthedegreeofRBn(123).Itfollowsimmediatelyfromtheeasilyprovedfactthatthewordwhichmaximizesrbisw=12:::n.Theorem3.20.RBn(123)ismonicandhasdegreen2:26AvoidanceClassAssociatedRGFsn(1=2=3;1=23)1n;1n12;1n221n(1=2=3;13=2)1m2nmforall1mnn(1=2=3;12=3)1n;12n1;121n2n(1=23;13=2)1nm+123:::mforall1mnn(1=23;12=3)1n;12:::(n1)1;12:::nn(1=23;123)12:::n;12:::(n1)withanadditional1insertedn(13=2;12=3)12:::mnm+1forall1mnn(13=2;123)layeredRGFswithatmosttwoelementsineachlayern(12=3;123)12:::(n1)mforall1mnTable1Avoidanceclassesavoidingtwopartitionsof[3]andassociatedRGFs273.2MultiplepatternavoidanceRatherthanavoidingasinglepattern,onecanavoidmultiplepatterns.foranysetPofsetpartitionsn(P)=f˙2n:˙avoidseveryˇ2Pg:Similarlyadapttheothernotationswehavebeenusing.Goyt[Goy08]characterizedthatcardinalitiesofn(P)foranyPS3.OurgoalinthissectionistodothesameforFn(P).WewillnotincludethosePcontainingboth1=2=3and123sinceitiseasytoseefromTheorem2.3thattherearenosuchpartitionsforn5.Table1showstheavoidanceclassesandtheresultingrestrictedgrowthfunctionsthatarisefromavoidingtwopatternsoflength3.TheseaswellastheentriesinTable2alsoappearinGoyt'swork,butweincludethemhereforcompleteness.Foreaseofreferences,wegiveatotalorderto3asfollows1=2=3;1=23;13=2;12=3;123(8)andlisttheelementsofanysetPinlexicographicorderwithrespectto(8).Finally,foranyP3wehaven(P)=nforn<3.Soweassumefortherestofthissectionthatn3.Thenextresulttranslatesthistableintogeneratingfunctions.Thisisroutineandonlyusestechniqueswehaveseeninearliersectionssotheproofisomitted.ThefunctionFn(13=2;123)isduetoGoytandSagan[GS09]wheretheGaussianpolynomialnkp;qisanextensionoftheonenedinequation(11).Themultivariateversion[n]p;q=pn1+pn2q++qn1sothebinomialanalogueisnkp;q=[n]p;q![k]p;q![nk]p;q!:Wecanrecovertheone-variableversionbylettingp=1.28Theorem3.21.Forn3wehave1.Fn(1=2=3;1=23)=1+rsn1+qrsn2t;2.Fn(1=2=3;13=2)=1+n1Xi=1risni;3.Fn(1=2=3;12=3)=1+rsn1+qn2rst;4.Fn(1=23;13=2)=1+n1Xi=1r(ni+12)s(n2)(i2);5.Fn(1=23;12=3)=1+(qt)n2(rs)(n12)+(rs)(n2);6.Fn(1=23;123)=(rs)(n2)+r(n12)n2Xi=0(qt)is(n2)i1;7.Fn(13=2;12=3)=1+n1Xi=1r(n2)(i2)s(ni+12);8.Fn(13=2;123)=Xk0(rs)(n2)k(nk)nkkr;s;and9.Fn(12=3;123)=(rs)(n2)+s(n12)n2Xi=0(qt)ir(n2)i1:Notethatfromthistheoremweimmediatelygetthefollowingniceequidistributionre-sults.Corollary3.22.ConsiderthegeneratingfunctionFn(P)whereP3.1.WehaveFn(P)invariantunderswitchingqandtif13=22PorPisoneoff1=2=3;1=23g;f1=23;12=3g;f1=23;123g;f12=3;123g:2.WehaveFn(P)invariantunderswitchingrandsifPisoneoff1=2=3;13=2g;f1=23;12=3g:293.WehavethefollowingequalitiesbetweengeneratingfunctionsforentP:Fn(1=23;13=2;q;r;s;t)=Fn(13=2;12=3;q;s;r;t)andFn(1=23;123;q;r;s;t)=Fn(12=3;123;q;s;r;t):Next,wewillexaminetheoutcomeofavoidingthreeandfourpartitionsof[3].WecanseetheavoidanceclassesandtheresultingrestrictedgrowthfunctionsinTable2.Theentriesinthistablecaneasilybeturnedintoapolynomialbythereaderifdesired.Avoidingallepartitionsof[3]isnotincludedbecauseitwouldcontainboth1=2=3and123.AvoidanceClassAssociatedRGFsn(1=2=3;1=23;13=2)1n,1n12n(1=2=3;1=23;12=3)1n,121whenn=3n(1=2=3;13=2;12=3)1n,12n1n(1=23;13=2;12=3)1n;12:::nn(1=23;13=2;123)122:::(n1);12:::nn(1=23;12=3;123)12:::(n1)1;12:::nn(13=2;12=3;123)12:::(n2)(n1)2,12:::nn(1=2=3;1=23;13=2;12=3)1nn(1=23;13=2;12=3;123)12:::nTable2AvoidanceclassesandassociatedRGFsavoidingthreeandfourpartitionsof[3]303.3Thepattern14=2=3Inthissectionwestudythepattern14=2=3.Itsavoidanceclasshasaverynicecharacteri-zation,Lemma3.23below,whichfacilitatesprovingenumerativeresults.Ourtheoremconcernsapplyingthelbstatistic,fromwhichaconnectionarisesbetween14=2=3-avoidingsetpartitionsandintegercompositions.First,wecharacterizeRn(14=2=3).Wetheindexitobeadaleofheightainwifai=aandai=maxfa1;:::;ai1g1:Lemma3.23.ForanRGFw,wiscontainedinRn(14=2=3)ifandonlyifwmeetsthefollowingrestrictions:fori2wehaveaimaxfa1;:::;ai1g1,andifwhasadaleofheighta,thenwdoesnothaveadaleofheighta+1.Proof.Let˙avoid14=2=3.Assume,towardscontradiction,thatthereexistedanaiinw=w(˙)withai<maxfa1;:::;ai1g1andleta=ai.Bythestructureofrestrictedgrowthfunctions,thisimpliesthata(a+1)(a+2)aexistsasasubwordinw.Butthenthesefourelementsgiverisetoanoccurrenceof14=2=3in˙,whichisacontradiction.Thisshowstheinequality.Nowassumethatthereexisteddalesofheightaandheighta+1inw.Thiswouldrequirewtocontain(a+1)a(a+2)(a+1)asasubword,whichagainimpliesanoccurrenceof14=2=3in˙.Thisshowstheheightrequirementfordales.Nowassumethat˙isapartitionwithw=w(˙)meetingthelistedrequirements.If˙contained14=2=3asapattern,thenabcamustoccurasasubwordinw,witha6=b6=c.Ifawastheminimumvalueinthissubword,theneithera<b1ora<c1,whichcontradictstherestrictionputonwinviewofthesecondainthesubword.Further,ifawasthemaximumvalueinthissubword,theneitherb<a1orc<a1,raisingthesamecontradictioninviewofthea.Similarly,wecanruleoutc<a<b.Thusthe31onlyremainingpossibilityisthatb<a<c.Bytherstconditioninthelemma,itthenmustbethatthesubwordisexactlya(a1)(a+1)a,whichcontradictstherestrictionondales.Thus˙avoids14=2=3,showingthereverseimplication.Notethatadaleinawordwcontributesexactlyonetolb(w).Andbythepreviouslemma,dalesaretheonlysourceoflbforwordsinRn(14=2=3).FortheproofofourtheoremaboutLB(14=2=3)wewillalsoneedthefollowingnotion:callialeft-rightmaximumofvalueainwifai=aandai>maxfa1;:::;ai1g:BeinganRGFisequivalenttohavingleft-rightmaximaofvalues1;2;:::;mforsomem.Theorem3.24.Forn1,wehaveLBn(14=2=3)=2n1+n2Xk=1"Xm2n1k+m1Xj1k1j1mjj#qk:Proof.Itiseasytoseethattheconstantterminthispolynomialcomesfromthelayeredpartitionsof[n],allofwhichavoid14=2=3.Nowconsiderthecotofqkfork1.Fromthediscussionbeforethestatementofthetheorem,forawordinRn(14=2=3)tohaveanlbofk,itmusthavekdales.Further,weknowthati=1isalwaysaleft-rightmaximumofvalue1inanyRGF,andthati=1isneveradale.ItfollowsbyLemma3.23that,tocompletelycharacterizeanRGFoflbequaltokandmaximumvalueminRn(14=2=3),ittospecifytheremainingm1left-rightmaximaandthekdaleindices.Assuch,therearen1m+k1waystochooseasetIwhichistheunionofthesetwoindexsets.LetI=fi1<i2<<im+k1gbesuchaset.Wewillindicateindiceschosenfordalesbycoloringthemblue,andleft-rightmaximabycoloringthemred.Wearuntobeamaximalsequenceofindicesic;ic+1;:::;idwhichismonochromatic.Letjbethenumberofblueruns,andletbsbethenumberofindicesinthesthbluerun,for1sj.Asthese32numberscountthedalesinw,wemusthaveb1+b2++bj=k;orequivalentlythatb1;:::;bjformanintegercompositionofk.Thustherearek1j1waysofchoosingjblueruns.NownotethatImuststartwitharedrun,andcanendwitheitheraredorbluerun.Thustherearejorj+1redruns.Letrtbethelengthofthetthredrun,for1tj+1,wherewesetrj+1=0iftherearejredruns.Furthermore,bythedaleheightrestrictioninLemma3.23,wehavert2for2tj.Nowasbefore,wehaver1+r2++rj+1=m1;subjecttor11,r2;:::;rj2,andrj+10.Usingastandardcompositionmanipulation,wecanputthissumincorrespondencewithacompositionofmj+1intoj+1parts,whichgivesmjjwaystochoosetheredruns.PuttingeverythingtogetherandsummingoverthepossiblevaluesofmandjgivesthecoientofqkasXm2n1k+m1Xj1k1j1mjj:Allthatisleftistogiveappropriateboundsfork.ItfollowsbyLemma3.23thatw=121n2isinRn(14=2=3)andthatwgivesamaximizinglbofn2.Thisgives1kn2,andprovidesthecorrectparametersforthepolynomial.Fromtheprevioustheorem,andfromthecharacterizationofRn(14=2=3),severalcorol-lariesfollow.Corollary3.25.WehaveLBn(14=2=3)=RSn(14=2=3):33Proof.Weproceedbyabijection˚thattakesRn(14=2=3)toitself,andthattakesthelbstatistictothersstatistic.LetwbeamemberofRn(14=2=3).FromLemma3.23,wecanpartitionwintosectionsbasedonthedalesofw.Sp,letaibealetterinw,andleta=ai.Ifthereisnodaleofheightaora1inw,thenitfollowsthateverycopyofaisadjacentinw.Thatistosay,wecanbreakwintow=w1alw2;withaj<aforallajinw1,andak>aforallakinw2.Callsuchastringaplateauofw.Itfollowsthatplateausinwcontributenothingtolb(w)orrs(w).Wewilllet˚acttriviallyontheplateausofw.Ifthisisnotthecase,thenthereisadaleofheightaora1inw.ByLemma3.23again,bothaanda1cannotbedaleheights.Sosupposea1isadaleheight.Itfollowsthattheoccurrencesofaanda1inwareadjacentandwehavew=w1(a1)l0aj1(a1)l1:::ajt(a1)ltw2;withl0;:::;lt1>0,lt0,andj1;:::;jt>0.Further,wehaveaj<a1forallajinw1,andak>aforallakinw2.Suchastringwillbecalledadalesectionofw.Breakingupwinthismannershowsthatsuchadalesectioncontributesl1++lttolb(w),andeitherj1++jt1orj1++jttors(w),dependingonwhetherornotlt=0.Assuch,ifd=(a1)l0aj1(a1)l1:::ajt(a1)ltisadalesectioninw,welet˚(d)=8>><>>:(a1)l0al1(a1)j1:::alt(a1)jtiflt>0;(a1)l0al1(a1)j1:::alt1(a1)jt1ajtiflt=0:34Itfollowsthat˚exchangeslbandrsforadalesection.NowbythenatureofRn(14=2=3),weknowthatwismerelyaconcatenationofplateausanddalesections.Havingd˚onthesepartsofw,we˚(w)byapplying˚totheplateausanddalesectionsofwinapiecewisemanner.Itfollowsthat˚isabijection,sinceitisaninvolution.Finally,sincelb(w)andrs(˚(w))aresumsoverthedalesectionsofwand˚(w),andsince˚exchangesthetwostatisticsoneachdalesection,itfollowsthatwehavelb(w)=rs(˚(w)).Corollary3.26.Fort2,wehaveLBn(14=2=3;1=2=:::=t)=t2Xi=0ni+n2Xk=1"t1Xm=2n1k+m1Xj1k1j1mjj#qkandtheequalityLBn(14=2=3;1=2=:::=t)=RSn(14=2=3;1=2=:::=t):Proof.Avoiding1=2=:::=taswellas14=2=3addstherestrictionthatwordsmusthavemaximumvaluelessthanorequaltot1.FollowingtheproofofTheorem3.24withthisadditionalrestrictiongivesthegeneratingfunctionLBn(14=2=3;1=2=:::=t).Next,wenotethatthesamebijectionfromCorollary3.25alsoprovidesabijectionfromRn(14=2=3;1=2:::=t)toitself,since˚preservesmaximumvalues.Thesamemapthenensuresthesecondequality.Corollary3.27.ThepolynomialLBn(14=2=3;123)hasdegreebn=3candleadingcoequalto8>>>>>><>>>>>>:1ifn=3k;nifn=3k+1;3n27n+146ifn=3k+2;35forsomeintegerk.Proof.Avoidingthepattern123aswellas14=2=3addstherestrictionthatletterscanberepeatedatmosttwiceinaword.AdaptingthenotationusedintheproofofCorollary3.25,thisimpliesthat,forw2Rn(14=2=3;123),thedalesectionsofwmusthavelengthequalto3or4.Further,thesedalesectionscanonlycontribute1tolb(w).Thustomaximizelb(w),wemaximizethenumberofdalesectionscontainedinw.Itfollowsfromtherestrictionsonwthatthisleadstoamaximumofbn=3c.Wenowmovetotheleadingcocient.Ifn=3kforsomeintegerk,thenitisclearthattheonlyRGFwinRn(14=2=3;123)thatachievesthismaximumisw=121343:::(2k1)2k(2k1);givingaleadingcotof1.Nowletw2Rn(14=2=3;123)forn=3k+1.Itfollowsthatweitherhasonedalesectionoflength4,oroneplateauoflength1.Inthecase,wenotethatadalesectionoflength4hastheforma(a+1)(a+1)aora(a+1)a(a+1).Astherewillbektotaldalesinw,wehavekchoicesforwhichdalesectiontoextend,and2choicesforhowtoextendit.Thisgives2kpossiblewordsoftheform.Nowassumewhasaplateauoflength1.Notethat,oncetheindexofthisplateauhasbeenchosen,therestofthewordisuniquelydetermined.Assuch,wecanchoosetoplacetheplateaudirectlyinfrontofanyofthekdalesections,orafterthelastdalesectioninw.Thisgivesk+1possiblewordsofthesecondform.Summingoverbothpossibilitiesnowgivesaleadingcotofn=3k+1.Finally,wehavew2Rn(14=2=3;123)forn=3k+2.Therearefourdistinctpossibilitiesforwinthiscase.First,wcouldcontainoneplateauoflength2.Thisgivesk+1possibilitiesasinthepreviousparagraph.Thesecondpossibilityisthatwcontainstwoplateausoflength1.Iftheseplateausareadjacent,thenasinthepreviouscasewehavek+1possibilities.Otherwise,wechoose2distinctplacesfromtheseoptions,givingk+12morewords.Inthe36thirdcase,wcontainsoneplateauoflength1andonedalesectionoflength4.Wehavek+1choicesfortheplateau,and2kpossibilitiesforthedalesection,giving2k(k+1)wordsofthisform.Finally,wcouldcontaintwodalesectionsoflength4.Inthiscase,wechoosetwodalesectionstoextend.Astherearetwodistinctwaystoextendeachdalesection,thisgives4k2suchwords.Summingoverthesefourcasesandusingthesubstitutionn=3k+2givestheresult.Ourlastcorollaryregardingthepattern14=2=3involvesmultiplepatternavoidancewithtwopartitionsof[4].First,weneedalemma.Lemma3.28.ForanRGFw,wiscontainedinRn(14=2=3;13=2=4)ifandonlyifwmeetsthefollowingrestrictions:Fori2wehaveaimaxfa1;:::;ai1g1,andIfiisadaleofheighta,thenaj=aoraj=a+1forallj>i.Proof.First,let˙avoid14=2=3and13=2=4,andletw=w(˙).SinceRn(14=2=3;13=2=4)isasubsetofRn(14=2=3),theinequalityfollowsfromLemma3.23.Nowassumethatiisadaleofheightainw,andassumetowardsacontradictionthatthereexistsajinwwithj>i,aj6=a,andaj6=a+1.Fromtheinequality,itmustbethataj>a+1.BecausewisanRGF,itfollowsthata(a+1)a(a+2)existsasasubwordinw.Butnowthesefourelementswillcauseanoccurrenceof13=2=4in˙,whichisacontradiction.Forthereverseimplication,let˙beapartitionwithw=w(˙)satisfyingtheaboverestrictions.FromLemma3.23,itfollowsthat˙willavoid14=2=3.Toseethat˙willalsoavoid13=2=4,notethatif˙contained13=2=4,thenthesubwordabacwouldexistinw,witha6=b6=c.Usingtheinequality,wecanruleoutallcasesexceptb<a<c.But,asthisimpliesadaleofheightbinw,thiswouldleadtoacontradictionwithrespecttothesecondrestrictionputonwbythelemma.Thus˙mustalsoavoid13=2=4.37Corollary3.29.WehaveLBn(14=2=3;13=2=4)=2n1+n2Xk=1"Xm2n1k+m1#qkandLBn(14=2=3;13=2=4)=RSn(14=2=3;13=2=4):Proof.FollowingtheproofofTheorem3.24,wenotethattheconstantterminthispolyno-mialcomesfromthelayeredpartitionsof[n].NowconsiderawordwinRn(14=2=3;13=2=4)withlbequaltokandmaximumvaluem,fork1.Fromthepreviouslemma,itfollowsthatthekdalesinwmustcometotherightofthemlefttorightmaximainw.Astheleadingoneinwprovidesthelefttorightmaximum,ittochoosek+m1otherindiceswhereweplacetheremaininglefttorightmaximaintheleft-mostm1indices,andthekdalesafterwards.Thisgivesn1k+m1suchwords,andsummingoverallpossiblevaluesofmgivesthecontofqkfork1.Finally,wenotethatthebijectionfromCorollary3.25alsotakesRn(14=2=3;13=2=4)toitself.Thisgivesthesecondequality.384RestrictedgrowthfunctionsInthischapterwepresentourresultsaboutRGFs.InthepreliminarychapterwenotedthatthetwonotionsforpatternavoidancewerethesameforallRGFpatternsoflengththreeexcept112and122.InSection4.1wedetermineallfourgeneratingfunctionsforthesepatterns,andshowmanyequalitiesbetweentheirgeneratingfunctionsincludingLBn(112)=RSn(112)=LBn(122).ThisresultusesGaussianpolynomials,integerpartitions,andthehookdecompositionofYoungdiagrams.Thefollowingsectionpresentsrecursiveformulaeforgeneratingthefunctionsforcertainpatternsofanylengthincluding12:::kand1k.Thesectionsdiscussthepatterns1212and1221whicharerelatedtononcrossingandnonnestingpartition,respectfully.Wedetwobijectionsfromtheseavoidanceclassestotwo-coloredMotzkinpathsandproveRSn(1212)=LBn(1212)=LBn(1221).Wealsodeterminethefour-variategeneratingfunctionsforthesepatternspairedwithanylengththreepattern.4.1Singlepatternsoflength34.1.1PatternsrelatedtointegerpartitionsinarectangleInthissubsection,weshowbijectivelythatthreeofthegeneratingfunctionsunderconsidera-tionarethesame.Moreover,thecommonvaluecanbeexpressedintermsoftheq-binomialcotswhichcountintegerpartitionsinarectangle.Firstweneedsomeaboutq-analoguesandintegerpartitions.Welet[n]q=1+q+q2++qn1:(9)Wecannowaq-analogueofthefactorial,letting[n]q!=[1]q[2]q[n]q:(10)39Figure1TheYoungdiagramfor=(5;5;4;3;3)Finally,wetheq-binomialcoorGaussianpolynomialsasnkq=[n]q![k]q![nk]q!:(11)Byconvention,nkq=0ifk<0ork>n.Apartition=(1;2;:::;k)ofanintegertisaweaklydecreasingsequenceofpositiveintegerssuchthatPki=1i=t.Wecalltheipartsandletjj=Pki=1i.TheYoungdiagramofapartitionisanarrayofboxeswithkrows,wheretheithrowhasiboxes.Forexamplethepartition=(5;5;4;3;3)wouldcorrespondtotheYoungdiagraminFigure1.SometimeswewillneedtorefertoparticularboxesintheYoungdiagram.Welet(i;j)denotetheboxintheithrowandjthcolumnoftheYoungdiagram.Ifisanr`rectangleand=(1;2;:::;k)isapartition,wesaythattheYoungdiagramofinsideifkrand1`andwewilldenotethisby.When,wewilldrawandsotogethersothattheir(1;1)boxescoincide,ascanbeseeninFigure2.Foranr`rectangleitiswell-knownthatr+``q=Xqjj:Nowthatwehavetheproperterminology,wecanproveourequidistributiontheoremofthissection.40Figure2TheYoungdiagramfor=(5;5;4;3;3)inthe65rectangleTheorem4.1.WehaveLBn(112)=RSn(112)=LBn(122)=Xt0n1tq:Inotherwords,eachoftheabovepolynomialsisthegeneratingfunctionforintegerpartitionscountedwithmultiplicitygivenbythenumberofrectanglesintowhichtheyWewillestablishTheorem4.1throughfourpropositions.First,weneedafewAsequenceofintegersu1:::uniscalledunimodalifthereexistsanindexiwithu1u2uiui+1un:Wearootedunimodalcompositionu=u1:::um:::untobeasequenceofnonnegativeintegers,togetherwithadistinguishedelementcalledtherootanddisplayedinboldfacetype,havingthefollowingproperties:1.uisunimodal.2.u1=un=0.3.Ifuisrootedatum,thenum=max(u).4.Wehavejujuj+1j1forallj.41Wejuj=u1++unandletAn=fu:u=u1:::unisarootedunimodalcompositiong:Forexampleu=00012222110000isarootedunimodalcompositionwithrootu6=2andjuj=11.TherootedunimodalcompositionsareusefultoshowthatRSn(112)isasumofGaussianpolynomials.Proposition4.2.WehaveRSn(112)=Xu2Anqjuj:Proof.Wewillconstructabijection :Rn(112)!Ansuchthatrs(w)=j (w)j.Letw=a1:::an,wheremistheindexofthemaximumofw.Wewillconstruct (w)=u=u1:::um:::unbylettingui=rs(ai).Forexampleifw=1234553221then (w)=0123332110.Webeginbyshowing iswelldLetw2Rn(112)andu= (w).ByTheorem2.5,whassomeinitialrun12:::mwhichisfollowedbyaweaklydecreasingsequencewithtermsatmostm.Wewillshowuproperties1{4above.First,properties1and3followfromthefactthatwisunimodalwithmaximumm.Becausea1=1andanistheright-mostelement,wehavers(a1)=rs(an)=0andthus,property2.Thefourthpropertyholdsbecausebeforethemaximumindexm,adjacentelementsincreasebyone,andafterthatindexthesequenceisweaklydecreasing.Wenow 1.Letu=u1:::um:::un2An.Let`(j)betheindexofthelastoccurrenceofjinu1:::um.Weconstructw= 1(u)sothatw=123:::mam+1:::anwhereform+1inwehaveai=`(ui).Forexampleifu=001122221000thenw=123456774222.Toshow 1iswellittoshowaiai+1forim.42Butthisfollowssinceu1:::umisaweaklyincreasingsequenceandsouiui+1forimimplies`(ui)`(ui+1).Next,weshowthatthetwomapsareindeedinverses.First,assume (w)=uand 1(u)=v=v1:::vn.Letmbetheindexofthemaximuminwsothatumistherootinu.Wewillshowai=viforall1in.Weknowai=iforallim.Sinceumisrootedinuthen,byof 1,wehavethatvalsobeginswith12:::m.Fori>m,theremustbeanindexkmwithk=ak=aiIffollowsthatuk=rs(ak)=rs(ai)=ui.Furthermore,kmustbethelargestindexlessthanorequaltomwhichthelastequalitysinceak+1=ak+1sothatuk+1>ui.Itfollows,byitionof`,thatvi=`(ui)=k=ai.Theproofthat ( 1(u))=uissimilar.If (w)=uthenui=rs(ai)andsors(w)=juj.ThereforeRSn(112)=Xu2Anqjujasdesired.LetBn=[m1f():anintegerpartitionand,foran(m1)(nm)rectangleg:Asdiscussedabove,X()2Bnqjj=Xm1n1m1q=Xt0n1tq:Proposition4.3.WehaveXu2Anqjuj=Xt0n1tq:Proof.Fromthediscussionjustbeforethisproposition,ittoconstructabijection':An!Bnsuchthatifu2Anand'(u)=()thenjuj=jj.Letu=u1:::um:::un243An.Thenweconstruct'(u)=()asfollows.First,weusetheindexoftherootofutodeterminethatwillbea(m1)(nm)rectangle.Considerthediagonalinformedbycoordinates(1;1);(2;2);:::anddiagonalsaboveandbelowthisone.Then,goingfromsouthwesttonortheast,taketheuisquaresalongeachdiagonalasivariesfrom2ton1toformthediagramfor.Forexampletherootedunimodalcompositionu=001233332210willgive=(5;5;4;3;3)inthe65rectangleshowninFigure2.Properties1,2,and4ensurethat=(1;:::;k)isawYoungdiagramcorrespondingtoanintegerpartition.Nowwemustcheckthat.Usingtheorderinginwhichweconstructedthediagonalsof,observethatthenumberofdiagonalsuptoandincludingthemaindiagonalisk.Asthemaindiagonalofcorrespondstoelementumandwebegininourconstructionwithelementu2,wehavekm1.Similarly,wecanseethat1isequaltothenumberofdiagonalsafterandincludingthemaindiagonal.Thus1nm,asweendwithelementun1.Therefore.If()2Bn,whereisan(m1)(nm)rectangle,thentherootof'1()willbeatindexm.Theentriesof'1()areobtainedusingthediagonalsofsoastoreversetheaboveconstruction.As'1isverysimilarto',weleavetheprocessofcheckingthat'1iswellandtheinverseof'tothereader.Inaddition,itisclearfromthethatjuj=jj.ItshouldbementionedthatweoriginallyprovedProposition4.3usingabijectionin-volvinghookdecompositions,similartoSection3ofthepaperofBarnabeietal.[BBES14].Althoughtheaboveproofwasfoundtobesimpler,itmaybeinterestingtofurtherexploreconnectionsbetweenpatternsinRGFsandhookdecompositions.Proposition4.4.WehaveLBn(112)=Xt1n1tq:Proof.Wewillconstructabijectionˆ:Rn(112)!Bnsuchthatlb(w)=jj,wherew=a1:::an2Rn(112)andˆ(w)=().Lettheinitialrunofwbea1a2:::am=12:::mso44thatm=max(w).First,weletbean(nm)(m1)rectangle.Wethenlet=(man;man1;:::;mam+1);permittingpartsequaltozero.Forexample,w=123456633211wouldmapto()showninFigure2.Asmisthemaximumofw,wehave0maim1form+1in.Inaddition,am+1am+2anandthusthepartsofareweaklydecreasing.Thereforeiswellandinside.Constructingˆ1isasimplematterwhichweleavetothereader.Nownoticethatinw,lb(ai)=0forall1im.Form<in,wehavethatlb(ai)=mai=ni+1.Thuslb(w)=lb(am+1)+lb(am+2)++lb(an)=nm+nm1++1=jjasdesired.Proposition4.5.WehaveLBn(112)=LBn(122):Proof.Wewillconstructabijection:Rn(112)!Rn(122)suchthatlb(w)=lb((w)).Letw=a1:::an2Rn(112)withmaximumm.Toconstruct(w)westartwiththesequence12:::m.Foreveryai,whereaiisnotintheinitialrunofw,wewillinserta1justtotherightofelementmai+1in(w).Notethat1aimensuresthatthiselementalwaysexistsandthusiswellForexampleifw=12345664331then(w)=11231411561.Clearlyisinvertible.Tocheckthatlbispreserved,notethatinwtheinitialrundoesnotcontributetolbandin(w),noneofthetermsgreaterthan1contributetolb.Letaisuchthati>m.Thenlb(ai)=mai.Ifweexaminethe1placedinto(w)becauseofai,wenoticethat45ithasmaitermsgreaterthan1toitsleft.Thereforethelbofthis1ismai.Thus,lb(w)=lb((w)).CombiningtheabovepropositionsyieldsTheorem4.1.4.1.2PatternsrelatedtointegerpartitionswithdistinctpartsNext,wewillexploreaconnectiontointegerpartitionswithdistinctparts.Itiswell-knownthatthegeneratingfunctionforpartitionswithdistinctpartsofsizeatmostn1isn1Yi=1(1+qi):Asnotedintheintroduction,forthepattern121wehaveRn(121)=wn(13=2)).SowecanusethefollowingresultofGoytandSaganwhostudiedthelsstatisticonn(13=2).Proposition4.6([GS09]).WehaveLSn(121)=n1Yi=1(1+qi):Thefollowingresultestablishesthat,onceagain,threeofourgeneratingfunctionsarethesame.Theorem4.7.WehavetheequalitiesLSn(112)=LSn(121)=RBn(122)=n1Yi=1(1+qi):Asbefore,webreaktheproofofthisresultintopieces.Proposition4.8.WehaveLSn(112)=LSn(121):Proof.Wewillconstructabijection˘:Rn(112)!Rn(121)suchthatls(w)=ls(˘(w)).Givenw2Rn(112)wewillconstruct˘(w)byrearrangingtheelementsofwinweakly46increasingorder.Fortheinverse,ifwearegivenalayeredRGF,v,thenweusetheelementofeachlayertoformaninitialrunandrearrangetheremainingelementsinweaklydecreasingorder.ForanyRGFw=a1:::anwehavels(ai)=ai1.Sincewand˘(w)arerearrangementsofeachother,lsispreserved.Proposition4.9.WehaveLSn(112)=RBn(122):Proof.Let:Rn(112)!Rn(122)beasinProposition4.5.Toseethatls(w)=rb((w)),notethatls(ai)=ai1.Byconstructiontheinitialrunofwhaslsthatisequaltothetotalrboftheleading1andelementsgreaterthan1in(w).Inaddition,foreachainotintheinitialrunofw,weplacea1totherightofmai+1in(w),andthereforethereareai1elementstoitsrightthatarelargerthanit.Thusls(w)=rb((w)).Combiningtheabovepropositions,weobtainTheorem4.7.4.1.3PatternsnotrelatedtointegerpartitionsInthissection,wepresenttwomoreconnectionsbetweenthegeneratingfunctionsofpatternsoflength3.Theisasfollows.Theorem4.10.WehaveRSn(122)=LBn(123)=RSn(123)=1+n2Xk=0n1k+1qk:Proof.Itwasshownin[DDG+16]thatLBn(123)=RSn(123)=1+n2Xk=0n1k+1qk:Soitestoconstructabijectionf:Rn(122)!Rn(123)thatpreservesthersstatistic.First,recallthatbyTheorem2.5,wordsinRn(123)containonly1sand2sandthatfor47w2Rn(122),everyelementj2ofwappearsonlyonce.Givenw=a1:::an2Rn(122),wewillconstructf(w)=b1:::bnbyreplacingeachelementj2inwwitha2.Thisisabijection,asanywordinRn(122)isuniquelydeterminedbytheplacementofitsones.Inaddition,rs(ai)=rs(bi)byconstructionsothatrs(w)=rs(f(w)).ThesecondestablishesyetanotherconnectionbetweenstatisticsonRn(112)andRn(122).Theorem4.11.WehaveRBn(112)=LSn(122)=nXm=0n1nmq(m2):Proof.Fortheequality,let:Rn(112)!Rn(122)beasinPropositions4.5and4.9.Wewillshowthatforw2Rn(112),wehaverb(w)=ls((w)).Becausewisunimodal,onlytheinitialruncontributestorb.Ifmisthelargestelementintheinitialrunofw,thenrb(w)=1+2++(m1)=m2.Similarly,onlytheelementsgreaterthan1in(w)contributetols.Byconstruction,thelargestelementin(w)ismaswell.Thus,ls((w))=1+2++(m1)=m2.ToshowthatRBn(112)=Pmn1nmq(m2)itfromwhatwedidinthepreviousparagraph,tocountthenumberofw2Rn(112)withinitialrun12:::m.Noticethatoncetheelementsintheweaklydecreasingsequencefollowingtheinitialrunhavebeenselected,thereisonlyonewaytoorderthem.Forthatsequencewemustchoosenmelementsfromtheset[m],allowingrepetition,yieldingatotalofn1nmasdesired.ItisremarkablethatthemapconnectssomanyofthestatisticsonRn(112)andRn(122);seetheproofsofPropositions4.5,4.9,and4.11.Thefour-variablegeneratingfunctionsFn(v;q;r;s;t)canbeusedtosuccinctlysummarizethesedemonstrationsasfollows.Theorem4.12.WehaveFn(112;q;r;s;1)=Fn(122;q;s;r;1):484.2RecursiveFormulaeandLongerWordsInthissectionwewillinvestigategeneratingfunctionsforavoidanceclassesofvariousRGFsoflengthgreaterthanthree.Thisincludesarecursiveformulaforcomputingthegeneratingfunctionsforlongerwordsintermsofshorterones.Recallthatw+kdenotesthewordobtainedbyaddingthenonnegativeintegerktoeveryelementofw.NotethatifwisanRGFandkisnonzero,thenw+kwillnotbeanRGF.However,thewordw=12:::k(w+k)obtainedbyconcatenatingtheincreasingsequence12:::kwithw+k,willbeanRGF.Infact,thereisarelationshipbetweenthegeneratingfunctionsforwandwforcertainstatistics.Inthefollowingtheorem,weshowthatthisrelationshipholdsforthelsandrsstatistic.Wenotethatin[MS12,Propositions2.1and2.2],MansourandShattuckusethesamemethodtothecardinalityoftheavoidanceclassofthepairsofpatternsf1222;12332gandf1222;12323g.Theorem4.13.LetvbeanRGFandv=1(v+1):ThenLSn(v)=n1Xj=0n1jqjLSj(v)andRSn(v)=n1Xj=0jXk=0n+kj2kqkRSj(v):Proof.Westartbybuildingtheavoidanceclassofvoutoftheavoidanceclassofv.Wedosobytakingawordwintheavoidanceclassofv,forming1(w+1),andthenaddingatnumberofonesto1(w+1)toobtainawordwoflengthnwhichavoidsv.Wethencounthowaddingtheseonestherespectivestatistics.Weestablishthatavoidanceispreservedinthisprocess.Letw2Rj(v).Sincewavoidsv,weknow1(w+1)avoids1(v+1)=v.Nowweneedtoshowthatformingwbyaddingnj1onesto1(w+1)inanymannerwillresultinwavoidingv.Ifw62Rn(v),thenthereisasubwordw0ofwsuchthatst(w0)=v:Sincev=1(v+1),thesmallestelement49ofw0mustappearonlyatthebeginningofthesubword,andmustbea1since1(w+1)avoidedv.Butremovingtheunique1andstandardizingtheremainingelementsshowsthatthereisasubwordofwthatstandardizestov.Thisisacontradiction.Therefore,wemusthavew2Rn(v):Similarly,everywordinRn(v)withnjonescanbeturnedintoawordinRj(v)byremovingallonesandstandardizing.Ifthiswordwasn'tinRj(v),thenitwouldcontainasubwordthatstandardizedtov.Asbefore,thiswouldmeantheoriginalwordcontained1(v+1)=v,whichisacontradiction.Therefore,wecanconstructeverywordinRn(v)fromthewordsinRj(v)forj2[0;n1].Wenowtranslatethisprocessintothegeneratingfunctionidentities.FirstwewillfocusontheLSformula.Wecanchooseanyw2Rj(v),andplacetheelementsofw+1inourwordwinn1jtwayssincewemustleavethepositionfreetobeaone.Thenweintherestofthepositionswithones.Sinceweadded1toeachelementofw2Rj(v)andaddedaonetothebeginningoftheword,wehavels(w)=ls(w)+j.SoLSn(v)=Xw2Rn(v)qls(w)=n1Xj=0Xw2Rj(v)n1jqjqls(w)=n1Xj=0n1jqjLSj(v):FortheRSformula,insteadofalljelementsofw+1increasingthestatistic,onlythekelementsofw+1thataretotheleftoftherightmostoneinwwillcontribute.Ifwechoosewheretoplacetheseelements,theneverythingelseisforced.Westartwithn1positionsavailable,anddisregardjk+1fortherightmostoneandtheelementsofw+1thatappearafterit.Thuswehave(n1)(jk+1)=n+kj2positionstochoosefrom.SummingoverallvaluesofjandkgivestheRSformula.InthepaperofDokosetal.[DDJ+12],theauthorsintroducedthenotionofstatisticalWilfequivalence.Wewillconsiderhowthisideacanbeappliedtothefourstatisticswehavebeenstudying.WetwoRGFsvandwtobels-Wilf-equivalentifLSn(v)=LSn(w)foralln,anddenotethisbyvlsw:50Similarlyanequivalencerelationfortheotherthreestatistics.Letstdenoteanyofourfourstatistics.Givenanyequivalencevstw,wecanuseTheorem4.13togenerateannumberofrelatedequivalences.Corollary4.14.Supposevstw.Thenforanyk1wehave12:::k(v+k)st12:::k(w+k):Proof.Forst=ls;rsthisfollowsimmediatelyfromTheorem4.13andinductiononk.Fortheothertwostatistics,notethatthesameideasasintheproofofTheorem4.13canbeusedtoshowthatonecanwritedownthegeneratingfunctionforstoverRn(12:::k(v+k))intermsofthegeneratingfunctionsforstoverRj(v)forjnalthoughtheexpressionsaremorecomplicated.Thusinductioncanalsobeusedinthesecasesaswell.ApplyingthiscorollarytotheequivalencesinTheorem4.5,Proposition4.8,andTheo-rem4.10yieldsthefollowingresult.Corollary4.15.Forallk1,wehave12:::kk(k+1)lb12:::k(k+1)(k+1);12:::kk(k+1)ls12:::k(k+1)k;12:::k(k+1)(k+1)rs12:::k(k+1)(k+2):WewillnowdemonstratehowtheseformulaecanbeusedtothegeneratingfunctionsforafamilyofRGFsbyLSn(12:::k)forageneralk.WebeginbythedegreeofLSn(12:::k)throughapurelycombinatorialapproachbeforeusingTheorem4.13togiveaformulaforthegeneratingfunctionitself.Proposition4.16.ThegeneratingfunctionLSn(12:::k)ismonicanddegLSn(12:::k)=k22+(k2)(nk+2):51Proof.Considerw=w1:::wn2Rn(12:::k)withaninitialrunoflength`.Thatis,foralli2[1;`];wi=i.Thenls(w`+1)=w`+11.Soweseethatls(w`+1)islargestwhenw`+1=`+1.However,wecannothavewk=kwithoutcontaining12:::k.Therefore,wemusthave`=k1,andwik1foralli2[k;n].Further,sinceourinitialruncontainsallelementsbetween1andk1,wehavels(wi)=wi1foralli2[k;n].Thus,tomaximizels,wemusthavewi=k1foralli2[k;n].Thisgivesustheuniquewordw=12:::(k2)(k1):::(k1),andasmallcomputationshowsls(w)=0+1+2++(k2)+(nk+1)(k2)=k12+(k2)(nk+1):ToobtainaformulaforLn(12:::k)wewillusetheq-analoguesintroducedearlier,oftensuppressingthesubscriptqforreadability.LetKm;n=[m+1]n11[m]:WewillneedthefollowingfactsaboutKm;n.Writing[m+1]n1=(1+q[m])n1andexpandingbythebinomialtheoremgivesKm;n=n1Xj=1n1jqj[m]j1:(12)Wealsohave1[m](Km+1;nK1;n)=n1Xj=1n1jqjKm;j(13)whichcanbeobtainedbysubstitutingtheofKm;jintothesumandthenapplyingthepreviousequation.Finallywefork3,ck=1k3Xj=11[j]!ckj:Notethatwhenk=3thesumisemptyandsoc3=1.Whilethefollowingexpression52forLSn(12:::k)isasum,notethatthenumberoftermsdependsonlyonkandnotonnmakingitntforcomputation.Theorem4.17.Fork3,wehaveLSn(12:::k)=1+k2Xi=11[i1]!cki+1Ki;n:Proof.Weproceedwithaproofbyinduction.In[DDG+16],theauthorsshowthatLSn(1=2=3)=[2]n1forthesetpartition1=2=3.Recallthatasetpartitionavoids1=2=3ifandonlyifitscorrespondingRGFavoids123.ThereforeLSn(1=2=3)=LSn(123)=[2]n1forn1.RewritingthisasLSn(123)=1+K1;ngivesourbasecasefork=3.Supposetheequalityheldfork3.Then,usingTheorem4.13aswellasequations(12)and(13),LSn(12:::k+1)=1+n1Xj=1n1jqjLSj(12:::k)=1+n1Xj=1n1jqj 1+k2Xi=11[i1]!cki+1Ki;j!=1+n1Xj=1n1jqj+k2Xi=11[i1]!cki+1 n1Xj=1n1jqjKi;j!=1+K1;n+k2Xi=11[i]!cki+1(Ki+1;nK1;n)=1+K1;n 1k2Xi=11[i]!cki+1!+k2Xi=11[i]!cki+1Ki+1;n=1+ck+1K1;n+k2Xi=11[i]!cki+1Ki+1;n=1+k1Xi=11[i1]!cki+2Ki;nwhichcompletestheinduction.Let1mdenotetheRGFconsistingofmcopiesofone.TheideasintheproofofTheo-53rem4.13canbeusedtogiverecursiveformulaeforthispattern.Itwouldbeinterestingtootherpatternswherethisreasoningcouldbeapplied.Theorem4.18.Form0,wehaveLSn(1m)=m1Xj=1n1j1qnjLSnj(1m)andRSn(1m)=RSn1(1m)+m1Xj=2njXk=0j+k2kqkRSnj(1m):Proof.Letwavoid1m.Thenwcanbeuniquelyobtainedbytakingaw0avoiding1mandinsertingjonesinw0+1,where1jm1andaonemustbeinsertedatthebeginningoftheword.Theformulaforlsnowfollowssincethebinomialcotcountsthenumberofchoicesforthenon-initialones,LSnj(1m)isthecontributionfromw0+1,andqnjistheobtainedfromtheinteractionbetweentheinitialoneandw0+1.ThereadershouldnowhavenoproblemmodifyingtheproofofthersformulainTheorem4.13toapplytothiscase.4.3Thepattern12124.3.1NoncrossingpartitionsThesetpartitionswhichavoidthepattern13=24arecallednon-crossingandareofinterest,inpart,becauseoftheirconnectionwithCoxetergroupsandCatalannumbers.SeethememoirofArmstrong[Arm09]formoreinformation.InthiscasethesetcontainmentinProposition2.2canbeturnedintoanequalityaswewillshownext.Notethatw(13=24)=1212.54Proposition4.19.WehaveRn(1212)=wn(13=24)):Proof.Asjustnoted,ittoshowthatifˇcontains13=24,thenw(ˇ)contains1212.Byifˇcontains13=24,thenw(ˇ)containsasubwordababforsomea6=b.Ifa<b,thenthiswillstandardizeto1212asdesired.Ifa>bthen,becausew(ˇ)isarestrictedgrowthfunction,theremustbesomeoccurrenceofbbeforetheleftmostoccurrenceofainw(ˇ).Thusw(ˇ)alsocontainsasubwordbabawhichisacopyof1212inw(ˇ).Withthispropositioninhand,wenowfocusongaininginformationaboutthesepartitionsbystudyingRn(1212).WebeginbyapplyingthersstatistictoRn(1212),andindoingsoobtainaq-analogueofthestandardCatalanrecursion.Weneedthefollowinglemmaregarding1212-avoidingrestrictedgrowthfunctions.Lemma4.20.ForanRGFw=a1:::an,thefollowingareequivalent:(1)TheRGFwavoids1212.(2)Therearenoababsubwordsinw.(3)Ifai=ai`forsomei<i0then,forallj0>i0,eitheraj0ai0oraj0>maxfa1;:::;ai0g.Proof.TheequivalenceofthetwostatementsfollowsfromtheproofofProposition4.19.Itthustoshowthat(2)and(3)areequivalent.First,letw=a1:::anbeanRGFwithnoababsubword,andletai=ai0forsomei<i0.Assume,towardscontradiction,thatthereexistsaj0withj0>i0andai0<aj0maxfa1;:::ai0g.Thisimpliesthatthereexistsajwithj<i0andaj=aj0.Ifi<j<i0,thenaiajai0aj0formsanababsubwordinw,acontradiction.Ifthisisnotthecase,thensinceaj>aiandwisanRGF,theremustexistanotheroccurrenceoftheletteraiprecedingaj.Thisletter,combinedwithaj,ai0,andaj055stillcreatesanababsubword,whichisagainacontradiction.Thisshowsthat(2)implies(3).Nowweshowthatifwcontainsanababsubword,thenwcannotsatisfy(3).Indeed,bythediscussionintheproofofProposition4.19,ifwcontainsanababsubwordthen,withoutlossofgenerality,wemayassumea<b.Thusthesecondoccurrenceofbinthesubwordwillviolatecondition(3).Thiscompletestheproofoftheequivalenceofthestatements.WenowmovetoarecursivewayofproducingwordsinRn(1212).Giventwowordsuandv,wewriteuvtodenotetheconcatenationofuandv.Furthermore,ifu=a1:::akthenletu+1=(a1+1):::(ak+1).WiththisnotationwecanstatethefollowingcorollaryofLemma4.20.Corollary4.21.IfuisinRn1(1212)thenboth1uand1(u+1)areinRn(1212).Proof.LetubeanelementofRn1(1212).Bythepreviouslemma,weknowthatudoesnotcontainanyababsubwords.Prependinga1touwillnotcreateanysuchsubword,asotherwisethiswouldimplyanababsubwordinuusingitsleading1.Therefore1uiscontainedinRn(1212).Furthermore,addingonetoeachelementinutocreateu+1willnotintroduceanababsubword,andprependinga1tocreate1(u+1)willnotcreateanababsubwordasthereisonlyonecopyof1in1(u+1).Thus1(u+1)isalsocontainedinRn(1212).Withtheseresultsinhand,wemovetooneofthemainresultsofthissection.Fortwowordswandu,wewillusethesetnotationw\u=;todenotethatwanduhavenoelementsincommon.Thenexttheoremgivesaq-analogueoftheusualrecursionfortheCatalannumbers.ItwillalsobeusedtoestablishaconnectionbetweenRn(1212)andlatticepaths.56Theorem4.22.WehaveRS0(1212)=1;RS1(1212)=1;andforn2,RSn(1212)=2RSn1(1212)+n2Xk=1qkRSk(1212)RSnk1(1212):Proof.Toprovetherecursion,wepartitionRn(1212)intothreedisjointsubsetsS,T,andUasfollows:S=fw2Rn(1212):a1=1andtherearenoother1sinwg;T=fw2Rn(1212):a1a2=11g;U=fw2Rn(1212):a1a2=12andthereisatleastoneother1inwg:WeclaimthatwecanalsodescribeSasthesetofwordsnedbyS=fw=1(u+1):u2Rn1(1212)g:(14)Toseethis,letubeawordinRn1(1212).FromCorollary4.21,weknoww=1(u+1)isanelementofRn(1212),andbyofu+1,theonly1inwwillbea1.Thisgivesonecontainment.NowletwbeanelementofSasoriginallySincetheleadingoneinwisunique,letu+1denotethelastn1lettersinw.ByLemma4.20,wcontainsnoababsubword;inparticular,u+1containsnoababsubword.Standardizingu+1totheRGFuwillnotcreateanyababsubwords,andthusuwillbecontainedinRn1(1212).Thisgivesthereversecontainment,fromwhichweconcludethatthetwosetsareequal.Asimilar57proof,withoutstandardizationofthesubword,allowsustodescribeTasthesetT=fw=1u:u2Rn1(1212)g:(15)NownotethatforanyRGFu,wehavers(u)=rs(1(u+1))andrs(u)=rs(1u).Usingthisfact,andtheabovecharacterizationofthesets,wecanseethatSandTmustcontributeRSn1(1212)eachtothetotalRSn(1212)polynomial.Finally,weclaimthatwecancharacterizeUasU=fw=1(u+1)1v:u2Rk(1212)for1kn2;st(1v)2Rnk1(1212);v\(u+1)=;g:(16)First,letwbecontainedinUasedatthebeginningoftheproof.ByofU,whasanonemptysubwordoftheformu+1consistingofallentriesbetweentheandsecond1inw.Letthelengthofubek.AswiththesetS,u+1willstandardizetou,anRGFinRk(1212).Nowletvbethelastnk2lettersinw,sothatourwordisoftheformw=1(u+1)1v:Sincea1isrepeatedbeforev,wemusthavevi=1orvi>max(u+1)forallibyLemma4.20,whereviistheithletterofv.Thisgivesv\(u+1)=;.Furthermore,thereisnoababsubwordcontainedin1v,andstandardizingthesubwordwillnotcreateanababpattern.Thusst(1v)iscontainedinRnk1(1212).ThisshowsoneinclusionbetweenthetwoversionsofU.NowletubeanelementofRk(1212),andlet1v0beanelementofRnk1(1212).Corollary4.21givesthat1(u+1)avoids1212aswell.NowfromtheRGF1v0,wecreatetheword1vbysetting(1v)i=8>><>>:(1v0)iif(1v0)i=1(1v0)i+max(u)if(1v0)i6=1:58Weclaimthatw=1(u+1)1visamemberofRn(1212).Toseethis,notethatu+1containsnoababsubwords,andfurtheru+1sharesnointegersincommonwiththerestofw.Thereforeu+1cannotcontributetoanababsubwordinw.Thusifsuchasubwordexistedinw,itmustalsoexistin11v.Thisisimpossibleasitwouldimplyanababsubwordin1v0,contradictingourchoiceof1v0.Wehavenowshownthereversesetcontainment,whichimpliesthedesiredequalityofthetwosets.WiththischaracterizationofU,wecannowdecomposers(w)forwinUasrs(w)=rs(u+1)+k+rs(1v);wherethemiddletermcomesfromthecontributiontorscausedbycomparingtheelementsofu+1withthesecond1inw.Summingoverallpossibilitiesofk,u,andv,andnotingthatthersofawordisnotabystandardization,wecanseethatUwillcontributen2Xk=1qkRSk(1212)RSnk1(1212):AddingtheresultsobtainedfromS,T,andUnowgivesthedesiredtotal.Forthenextresult,werecalltheitionofaMotzkinpath.AMotzkinpathPoflengthnisalatticepathintheplanewhichstartsat(0;0),endsat(n;0),staysweaklyabovethex-axis,andwhichusesvectorstepsintheformofupsteps(1,1),horizontalsteps(1,0),anddownsteps(1,-1).LetMndenotethesetofallMotzkinpathsoflengthn.WewriteP=s1:::snforsuchapath,wheresi=8>>>>>><>>>>>>:Uiftheithstepisanupstep;Liftheithstepisahorizontalstep;Diftheithstepisadownstep:GivenastepsiinP,wecanrealizesigeometricallyasalinesegmentintheplaneconnecting59twolatticepointsintheobviousway.Withthisinmind,thelevelofsi,l(si),tobethelowesty-coordinateinsi.NotethatthelevelstatisticprovidesanaturalpairingofupstepswithdownstepsinaMotzkinpath.Namely,weassociateanupstepsiwiththedownstepsj,j>i,whichisatthesamelevelassi,i.e.l(si)=l(sj).Wewillcallsuchstepspaired.Wenowatwo-coloredMotzkinpathRoflengthntobeaMotzkinpathoflengthnwhoselevelstepsareindividuallycoloredusingoneofthecolorsaorb.Wewillcallana-coloredlevelstepana-stepandab-coloredlevelstepab-step.Foratwo-coloredMotzkinpathR=s1:::snwewillstillusesiequaltoUorDforupstepsanddownsteps,butwilluseaorbinsteadofLtoshowthecolorofthelevelsteps.LetM2ndenotethesetofalltwo-coloredMotzkinpathsoflengthn.FortwopathsP=s1:::snandQ=t1:::tmwewritePQ=s1:::snt1:::tmtoindicatetheirconcatenation.LettheareaofapathR,area(R),denotetheareaenclosedbetweenRandthex-axis.Mn(q)=XR2M2nqarea(R);(17)Drake[Dra09]provedthefollowingrecursion.Theorem4.23([Dra09]).WehaveM0(q)=1and,forn1,Mn(q)=2Mn1(q)+Pn2k=1qkMk(q)Mnk1(q):UsingTheorems4.22and4.23aswellasinductiononnimmediatelygivesthefollowingequality.Corollary4.24.WehaveRSn(1212)=Mn1(q)foralln1.Interestingly,itturnsoutthatwealsohaveLBn(1212)=LBn(1221)=Mn1(q)which60willbeprovedinSection4.4.Inournextresult,weprovethepreviouscorollarydirectlyviaabijectionbetweenM2n1andRn(1212).Theorem4.25.Thereisanexplicitbijection :M2n1!Rn(1212)suchthatarea(R)=rs( (R))forallR2M2n1.Proof.GivenR=s1:::sn12M2n1we (R)=w=a1a2:::anasfollows.Leta1=1andai+1=8>>>><>>>>:max(a1:::ai)+1ifsiequalsUorb;aiifsi=a;ajifsi=Dispairedwiththeupstepsj:Bywayofexample,wehave (UaUDbDUaD)=1223241551.Weshowthat iswellBywehavea1=1and,fori>1,aiiseitherequaltoajforsomej<iormax(a1:::ai1)+1.Thisimpliesthatthataiisapositiveintegerandaimax(a1:::ai1)+1foralli,sowisanRGF.Fortheavoidancecondition,notethatanumberinwwillappearmorethanonceforonlytworeasons.Theisbecauseofa-stepswhichwillgiveusaconsecutivestringofthisnumber.Thesecondisbecauseofapairedupstepanddownstep.Suppose,towardsacontradiction,thatwhasthepattern1212andsowillhaveasubsequenceijijwithi<j.Sincewehaverepeatedi'swhicharenotpartofaconsecutivestringwemusthaveapairedupanddownstepwhichgiveustwoi's.Similarlybecauseoftherepeatedj'swehaveapairedupanddownstepwhichgiveustwoj's.However,thismeansthats1:::sn1hasasubwordUUDD,butthestUandtheDarepairedandthesecondUandDarepairedwhichisnotpossible.Sowavoids1212.Tomotivatetheoftheinversenotethat,intheof ,ifsi=Uthenwehaveanincreaseai<ai+1.Sincetheupstepmusthaveapaireddownstepsjtheremustbesomej>iwithaj=ai.Ifinsteadsi=bwehaveanincreaseai<ai+1,butourmapwillnotfurtherrepeatai.Ifsi=athenai=ai+1.Finallyconsiderifsi=D.Weclaimthat61inthiscaseai>ai+1.Indeed,thisdownstephasapairedupstepskwithk<iand,sinceskisanupstep,wehaveak+1=max(a1:::ak)+1.Sincesiissk'spaireddownstepeveryj2[k+1;i]willhaveajequaltomax(a1:::aj1)+1orequaltoanumberwhoseindexisearlierintheinterval[k+1;i].Soforallj2[k+1;i]wehaveaj>ak=ai+1.Asresultai>ai+1asclaimed.Thisdiscussionleadsustoforw=a1a2:::an2Rn(1212),thelatticepath 1(w)=R=s1:::sn1wheresi=8>>>>>>><>>>>>>>:aifai=ai+1;bifai<ai+1and@j>i+1suchthataj=ai;Uifai<ai+1and9j>i+1suchthataj=ai;Difai>ai+1;Byourpreviousdiscussion,thismapisaninverseontheimageof .SinceitisknownthatjM2n1j=Cn=jRn(1212)j,whereCnisthenthCatalannumber, mustbeabijection.Lastlywewillshowthatarea(R)=rs(g(R)).Consideraletterai.Wewanttocountthenumberofdistinctelementstotherightandsmallerthanai.Wewillconsiderwhichstepsskwithkimakeak+1smallerthanai.Ifsk=athenak+1=akwhichiseitherequaltoaiordoesn'tbringaboutanewdistinctnumbersothesestepsneednotbeconsidered.IfskequalsborUthenak+1islargerthanallpreviousnumbers,soisnotsmallerthanai.Sotheonlystepswhichcouldresultinsomethingtotherightandsmallerthanaiaredownstepssk=D.Lets`=Ubeitspairedupstep.Firstwewillconsiderthecasewhen`=i.Inthiscase,ak+1=aisoak+1isnotsmallerthanai.Ifinstead`>i,wehaveak+1=a`andsincea`isrightofaithenumberak+1isnotadistinctnumberrightofai.Ourlastcaseisthat`<i.Weshowedearlierthatifs`isanupsteppairedwiththedownstepsk,thenforallj2[`+1;k]wehaveaj>ak+1=a`.Sincei2[`+1;k]itfollowsthatai>ak+1whichshowsthatak+1istotherightandsmallerthanai.Finally,wealsohavethatforalljin[i;k],aj>ak+1.Thusak+1istheoccurrenceofthisletterthatappearstotherightofai,andsoak+1iscountedbyrs.62Thismeansthatrs(ai)isequaltothenumberofdownstepsweaklytotherightofsisuchthatitspairedupstepisstrictlytotheleftofsi.Inthecaseofsiequaltoa,b,orUthiscalculationisequaltothelevelofthestep.Inthecaseofsi=Dthiscalculationisequaltolevelofthestepplusone.AlltogetherthisgivesthetotalareaunderthepathR.Sincethisalsocountsrs(w)wehavethatarea(R)=rs(w).4.3.2CombinationswithotherpatternsNextweexamineRGFsthatavoid1212andanotherpatternoflength3.Asthepatterns121,122,and112areallsubpatternsof1212,theonlyinterestingcasestolookatareRn(111;1212)andRn(123;1212).WestartbycalculatingRSn(111;1212).ItiseasytocombineTheorem2.5andLemma4.20tocharacterizeRn(111;1212).Lemma4.26.WehaveRn(111;1212)=fw2Rn(1212):everyelementofwappearsatmosttwiceg:foralln0.ThefollowingpropositionissimilartoTheorem4.22inseveralrespects.First,thispropositionprovidesaq-analogueofthestandardMotzkinrecursionandisprovedusingverysimilarrecursivetechniquesasbefore.Furthermore,itwillalsobeusedtoconnectRn(111;1212)tolatticepaths.Proposition4.27.WehaveRS0(111;1212)=1;RS1(111;1212)=1;63andforn2,RSn(111;1212)=RSn1(111;1212)+n2Xk=0qkRSk(111;1212)RSnk2(111;1212):Proof.WefollowtheproofofTheorem4.22bypartitioningRn(111;1212)intothesetsS=fw2Rn(111;1212):a1=1andtherearenoother1sinwg;T=fw2Rn(111;1212):a1a2=11g;U=fw2Rn(111;1212):a1a2=12andthereisasingleother1inwg:UsingthesamereasoningasinTheorem4.22andaddingtherestrictionsofavoiding111givestheequivalentcharacterizationsS=fw=1(u+1):u2Rn1(111;1212)gT=fw=11(u+1):u2Rn2(111;1212)gU=fw=1(u+1)1v:u2Rk(111;1212)for1kn2st(v)2Rnk2(111;1212);v\1(u+1)=;g:Fromthisthedesiredrecurrenceeasilyfollows.ThenextresultprovidesanexplicitbijectionbetweenRn(111;1212)andMn.Weextendthelevelstatisticintheprevioussectiontopaths.GivenaMotzkinpathP=s1:::sn,wedthelevelofthepath,l(P),tobel(P)=nXi=1l(si):Itshouldbenotedthatifweimposearectangulargridofunitsquaresonthequadrantoftheplane,thenl(P)simplycountsthetotalareaoftheunitsquarescontainedbelowP64andabovethex-axis.WewilluseourbijectiontocalculatethegeneratingfunctionforthelevelstatistictakenoverallMotzkinpathsoflengthn.Theorem4.28.Forn0,wehaveRSn(111;1212)=XP2Mnql(P):Proof.Westartbyabijection˚:Rn(111;1212)7!Mn.Foranyw=a1:::an,welet˚(w)=P,whereP=s1:::snandsi=8>>>>>><>>>>>>:Uifai=ajforsomej>i;Lifai6=ajforanyj6=i;Difai=ajforsomej<i:Toshowthat˚iswellnotethatsincewcontainsatmosttwocopiesofanyinteger,thethreecasesaredisjointandcoverallpossibilities.WealsoneedtoshowthatPisaMotzkinpath.Butthisistruebecausetheof˚inducesabijectionbetweentheupstepsanddownstepsof˚(w)inwhicheachupstepprecedesitscorrespondingdownstep.Wewillneedthefactthatthisbijectionbetweenupanddownstepsinducedbytheof˚isexactlythesameasthepairingrelationshipinthepath˚(w).Formally,wehavethati<jandai=ajifandonlyifsiistheupsteppairedwiththedownstepsj.Toseethis,assumei<jandai=aj.Considerthesubwordai:::aj.Aswavoids111and1212,wemusthaveak>aiforeachi<k<j.Furthermore,ifi<k<jandifak=ak0forsomeotherk0,weclearlymustalsohavei<k0<j.Thusthesubpathsi+1:::sj1isaMotzkinpathtranslatedtostartatthelevelofsi+1.Itfollowsthatsiandsjmustbepaired.Thisinfactprovestheequivalence,asthepairingrelationshiponaMotzkinpathisunique.65Beforeinverting˚,itwillbeusefultolookagainatitsRecallthatanysequencew=a1a2:::anofintegershasalefttorightmaximumatiifai>max(a1:::ai1).IfwisanRGFthenclearlythelefttorightmaximaoccurexactlywhenai=max(a1:::ai1)+1.AnothercharacterizationforRGFsisthatwhasalefttorightmaximumatiifandonlyifaiistherstoccurrenceofthatvalueinw.Soifw2Rn(111;1212),thelefttorightmaximaoccurpreciselyatthoseicorrespondingtothetwocasesintheof˚.Nowtoinvert˚,letP=s1:::snbeapathinMn.Wed˚1(P)=a1:::anbya1=1and,forj2,aj=8>><>>:max(a1:::aj1)+1ifsj=Uorsj=L;aiifsjisadownsteppairedwithsi:Theproofthatthisfunctioniswellissimilartotheonegivenfor˚andsoomitted.Andfromthedescriptionof˚intermsoflefttorightmaximaaswellasourremarksabout˚'srelationshiptothepairingbijection,itshouldbeclearthatthisistheinversefunction.Itnowtoshowthatrs(w)=l(˚(w))foranywinouravoidanceclass.Letw=a1:::anand˚(w)=s1:::sn.Wewillprovethestrongerstatementthatrs(ai)=l(si)for1in.Todothis,notethatifl(si)=k,thentherearepreciselykdownstepstotherightofsiwhosepairedupstepsprecedesiin˚(w).Nowassumers(ai)=k.Bytherearekintegersaj1;:::;ajktotherightandsmallerofai.AswisanRGF,eachoftheseintegersalsoappeartotheleftofaiinw.Bytheof˚,thesj1;:::;sjkaredownstepswhichfollowsiin˚(w)whosepairedupstepsprecedesi.Thisgivesl(si)k.Toseethatweactuallyhaveequality,assumethatthereisanotherdownstepslwhichfollowssiin˚(w).Weknowthatinw,aial,asaldoesnotcontributetors(ai).Ifai=al,theninfactsiandslmustbepairedvialevel,andthussldoesnotchangel(si).Finally,wedealwiththecaseai<al.Asslisadownstep,theremustexistanotherletteral0inwwithl0<landal0=al.InorderforwtobeanRGFandtoavoid1212,onecanseethatwe66mustalsohavei<l0.Henceslanditspairedupstepsl0bothfollowsiin˚(w),andthusslwillstillnotl(si).Thuswehavers(ai)=l(si)=kasdesired.WenowconcludethesectionwithasimplepropositioncharacterizingRn(123;1212).AstheresultfollowseasilyfromTheorem2.5,Proposition4.20,andstandardcountingtechniques,weleavetheprooftothereader.Proposition4.29.IfwiscontainedinRn(123;1212),thenw=1l2i1nilforsomel1,i0satisfyingl+in.Assuch,forn0wehaveLBn(123;1212)=RSn(123;1212)=1+n2Xk=0(nk1)qkandLSn(123;1212)=RBn(123;1212)=1+n1Xk=1(nk)qk:4.4Thepattern12214.4.1NonnestingpartitionsThetermnonnestinghasbeenintwaysintheliterature.Insomesourcesanonnestingpartitionisapartitionˇwherewecanneverndfourelementsa<x<y<bsuchthata;b2Aandx;y2BfortwodistinctblocksA;B.ThisisthesenseusedinKlazar'spaper[Kla96]andisequivalenttoapartitionavoiding14=23.Inotherpapers,includingKlazar'sarticle[Kla00b],apartitionˇisnonnestingif,when-evertherearefourelementsa<x<y<bsuchthata;b2Aandx;y2BfortwodistinctblocksA;B,thenthereexistsac2Asuchthatx<c<y.Thisisoftengivenusingarcdiagrams.Wedrawthearcdiagramofapartitionof[n]bywriting1throughnon67astraightlineanddrawingarcs(a;b)ifa<bareinablockandconsecutivewhenwritingtheblockinincreasingorder,seeFigure3.Anestingisapairofarcs(a;b)and(x;y)suchthata<x<y<b,andwewillsayinthiscasethatthepairofarcsnest.Forcompleteness,weprovetheequivalenceofthisconditionwiththesecondofanonnestingpartition.ItisknownthatthenumberofpartitionssatisfyingeitherofthesetwoequivalentconditionsistheCatalannumbers,Cn.Proposition4.30.Thefollowingconditionsareequivalentforapartitionˇ.1.Iftherearefourelementsa<x<y<bsuchthata;b2Aandx;y2BfortwodistinctblocksA;Bthenthereexistsac2Asuchthatx<c<y.2.Thearcdiagramforˇcontainsnonestings.Proof.Wewillshowthatifapartitionfailscondition1,thenitsarcdiagramhasanesting.Saythattherearefourelementsa<x<y<bsuchthata;b2Aandx;y2BfortwodistinctblocksA;Bbutthereisnoc2Asuchthatx<c<y.Sincethereisana2Awitha<xthereisalargestelementa2Awherea<x.Similarly,thereisasmallestb2Awithy<b.SincethereisnoelementofAbetweenxandy,(a;b)mustbeanarc.Alsothereisasmallestelementy2Bsuchthatx<ysothat(x;y)isanarc.Sincea<x<y<bthesearcsnestwhichisacontradiction.Conversely,assumethatthearcdiagramhastwoarcs(a;b)and(x;y)whichnestwitha<x<y<b.Byconstructionofthearcs,thisimpliesthataandbareconsecutiveelementsintheirblockA,sotheredoesnotexistac2Asuchthata<c<bandtheconditionisfalse.Thereisanothernotionofnonnestingwhichwewillcallleftnonnestingandcanbebyatcollectionofarcs.ForeachblockBwewilldrawallarcsoftheform(minB;b)withb2BnfminBg,andcallthediagramwiththesearcstheleftarcdiagram.AnexampleisdisplayedinFigure3.Ifapartition'sleftarcdiagramhasnopairofarcs6812345671234567Figure3Thearcdiagramandleftarcdiagramforthepartition134=267=5.whichnestthenwewillcallthispartitionleftnonnestingtodistinguishourtermfromtheprevioustwoofnonnesting.LetthissetbeLNNn.JelandMansourintheirpaper[JM08]nonnestingbyrequiringthatapar-tition'sassociatedRGFavoid1221,andtheyfoundthatjRn(1221)j=Cn,thenthCatalannumber.Forapartitionˇ,itturnsoutthatw(ˇ)avoids1221ifandonlyifitsleftarcdiagramcontainsnonestings.Asresult,thepartitionsinLNNnarealsocountedbythenthCatalannumber.Proposition4.31.WehaveRn(1221)=w(LNNn):Proof.Firstwewillshowthatifapartition'sleftarcdiagramcontainsanestingthenitsassociatedRGFhasthepattern1221.Letˇ=B1=:::=Bkbeapartitionof[n].Saythatitsleftarcdiagramhasanestingwhichmeansthatwehavearcs(a;b)and(x;y)suchthata<x<y<b.Sincethesearearcsfromtheleftarcdiagramweknowthata=minBiandx=minBjforsomedistinctblocksBiandBj,andsinceweordertheblocksofˇsothattheirminimumelementsincreaseweknowthati<j.Asresultw(ˇ)hasthesubwordijjiwhichisthepattern1221.Conversely,saythatwehaveanRGFwwiththepattern1221,soithasasubwordijjiwithi<j.Pickthesubwordsothattheiandjaretheoccurrencesoftheselettersinw.Thustheycorrespondtominimaintheirrespectiveblocksofthecorrespondingpartitionˇ.Itfollowsthatthetwoi'sandtwoj'sgiverisetonestingarcsintheleftarcdiagramofˇ.TherestofthissectionwilldescribeRn(1221),someofitsgeneratingfunctions,andsome69connectionstootherpatterns.WewillprovethatLBn(1221)=RSn(1212)byshowingthatthereexistsabijectionfromtwo-coloredMotzkinpathstoRn(1221)whichmapsareatolb,andthentheresultwillfollowfromTheorem4.25.WefurtherusethisbijectionandpreviousmethodstodeterminethegeneratingfunctionforsomepairsofRGFswhichinclude1221.WeendthesectionbyshowingLBn(1221)=LBn(1212)andsummarizingalltheequalitieswehaveproved.4.4.2Thepattern1221byitselfForanRGFw=w1w2:::wnwewillcallaletterwirepeatedifthereexistsaj<isuchthatwj=wi.Ifaletterisnotarepeatedletter,wewillcallitaoccurrence.SincewisanRGF,theoccurrencesareexactlytheleft-rightmaxima.Lemma4.32.Awordw2Rn(1221)ifandonlyifthesubwordofallrepeatedlettersinwisweaklyincreasing.Proof.Saythatwcontainsthepattern1221andsohasasubwordabbaforsomea<b.Thesecondbaarerepeatedlettersinw.Thisimpliesthatthereisadecreaseinthesubwordofallrepeatedletters.Conversely,saythatthesubwordofallrepeatedlettersofwhasandecreasebawitha<b.SincethesearerepeatedlettersinanRGFthebofwappearsearlier,andtheainwappearsearlierthantheb.Hencewehaveasubwordabbawitha<bandthepattern1221.Usingthepreviouslemmawecanasurjectioninc:Rn!Rn(1221).Themapwilltakeaw2Rnandwilloutputinc(w)=vwhichiswwithitssubwordofrepeatedlettersputinweaklyincreasingorder.Forexampleifw=1112221331theninc(w)=1112112323.ToseethismapiswellwemustshowthatvisanRGF.Butthesubwordofrepeatedlettersisrearrangedtobeweaklyincreasingwhichforcesthemaximumofanytoweaklydecrease.Sincetheleft-rightmaximaofwdonotmoveinthisprocess,70theydonotchangeinpassingtovsothatthelatterisstillanRGF.Also,vavoids1221byLemma4.32,showinginciswellInthenextlemmaweshowthatincpreserveslb.NotethatbecausewisanRGF,allthenumbersintheinterval[wi+1;maxfw1;:::;wi1g]appeartotheleftofwiandarelargerthanwi,solb(wi)=maxfw1;:::;wi1gwi:(18)Lemma4.33.Letvbearearrangementofwsuchthatbothhavethesameleft-rightmaximainthesameplaces.Thenlb(v)=lb(w).Inparticular,lb(w)=lb(inc(w)).Proof.Sincewandvonlyhavetheirrepeatedlettersrearrangedandtheirleft-rightmaximaweknowmaxfw1;:::;wig=maxfv1;:::;vigforalliandfv1;:::;vng=fw1;:::;wngasmultisets.Usingequation(18)lb(w)=nXi=1(maxfw1;:::;wi1gwi)=nXi=1(maxfv1;:::;vi1gvi)=lb(v):Thespecialcaseofv=inc(w)nowfollowsfromtheofthefunction.WewishtoshowthatthegeneratingfunctionRSn(1212)discussedinSection4.3isequaltoLBn(1221).TheproofwillbesimilartothatofTheorem4.25inthatwewillconstructabijectionfromtwo-coloredMotzkinpathslengthn1toRn(1221)whichmapsareatolb.Themapwillnotbetodescribe.However,provingthatisabijectionwillrequireadetailedargument.Weamap:Rk(1221)!Rk+2(1221)andprovidethefollowinglemmatoassistus.Thismapwillbeusefulwhendiscussingtwo-coloredMotzkinpathswhichareobtainedfromasmallerpathbyprependinganupstepandappendingadownstep.Givenanyv2Rk(1221)wev=v1v2:::vksuchthatvi=8>><>>:vi+1ifviisaoccurrence;vielse:(19)71Itisnothardtoseethatu=1v1isanRGF,butitmaynotavoid1221,sowe(v)=inc(u)whichisinRk+2(1221)byLemma4.32.Forexample,ifv=1212344willhaveu=1v1=123124541and(v)=123114524.Lemma4.34.Fork0themap:Rk(1221)!Rk+2(1221)isaninjection.Furthermore,theimageofispreciselythew2Rk+2(1221)satisfyingthefollowingthreeproperties.(i)Thewordwhasmorethanone1andendsinarepeatedletter.(ii)Ifwiisarepeatedletterthenwi<maxfw1;:::;wi1g.(iii)If,forij,wehavewi1andwj+1arerepeatedletterswithwiwi+1:::wjalloccurrencesthenwj+1<wi1.Proof.Wewillstartbyshowingthatisinjective.Givenav2Rk(1221),consideru=1v1.Wecaneasilyrecovervfromubyremovingtheandlast1,andcanfurtherrecovervbydecreasingallleft-rightmaximainvbyone.Weshowingthatisinjectivebyrecoveringufromw=inc(u).Notethatsincevavoids1221,itssubwordrofallrepeatedlettersisweaklyincreasing.Thesubwordofallrepeatedlettersinu=1v1isthenr1.Makingthissubwordincreasingresultsinthesubwordofallrepeatedlettersinwbeing1r.Wecanthusrecoverubyreplacing1rinwbyr1.Next,weshowthatwallthreeproperties.Sinceu=1v1hasmorethanone1andendsinarepeatedletter,theRGFw=inc(u)doesaswell.Property(i)isthusNextweshowproperty(ii)byshowingthatuproperty(ii).Ifviisarepeatedletterthenwealwayshavevimaxfv1;:::;vi1g.Sinceweincreasedalloccurrencestogetvandlefttherepeatedlettersthesamewehavevi<maxfv1;:::;vi1g.Andclearlythetwonewonesinudonotchangethisinequality.Aspreviouslynoted,thevalueintheplaceofagivenrepeatedlettercanonlygetweaklysmallerinpassingfromutow=inc(u).72Andsinceleft-rightmaximadon'tchange,walsoproperty(ii).Lastly,wewillshowproperty(iii).Considerthesituationwherewiwi+1:::wjarealloccurrencesbutwi1andwj+1arerepeatedletters.Butthenwj+1wasinpositioni1inuwhichisalsoapositioninv.Andtheelementinpositioniofuiswiwhichisaleft-rightmaximum.Sinceleft-rightmaximainvwereincreasedbyoneinpassingfromvtovwehavewj+1<wi1asdesired.Ourgoalistoamap:M2n1!Rn(1221)whichmapsareatolb.BeforewewewilldiscussapartitionoftheregionunderR=s1:::sn12M2n1whichwillaidusinshowingthatareaissenttolb.Figure4givesanexampleofthisprocesswheretshadingsindicatepartsofthepartition.Recallthatl(si)isthelevel,orsmallesty-value,ofsi.Ifsi=D,weA(si)tobeequaltotheareainthesamerowbetweensianditspairedupstepbutexcludingtheareaunderotherdownstepsora-steps.InFigure4,A(s5)=1,A(s8)=A(s12)=2andA(s9)=5.TheareaunderRcanbepartitionedasfollows.Therectangleunderana-stepsiwillbeapartwithareal(si).Forexample,inthewehavetheareal(s4)=2.Ourotherpartswillbeassociatedtodownsteps.Givenadownstepsi,itspartwillconsistofallareacountedbyA(si)togetherwiththeareaoftherectangleunderthedownstepwhichisgivenbyl(si)foratotalofA(si)+l(si).Returningtoourexample,stepss5;s8;s9;ands12contributetotalareas2;3;5;and2,respectively.SincethispartitionsalltheareaunderRwehavearea(R)=Xsi=al(si)+Xsi=D(A(si)+l(si)):(20)Nextwewilldamap:M2n1!Rn(1221)suchthatarea(R)=lb((R)).Before73we(R)wewillanRGF,v(R)=v1:::vn,bylettingv1=1andvi+1=8>>>><>>>>:maxfv1;:::;vig+1ifsiequalsUorb;maxfv1;:::;vigl(si)ifsi=a;maxfv1;:::;vigA(si)l(si)ifsi=D;fori0.Forthetwo-coloredMotzkinpathRinFigure4wehavev(R)=1234225631786.Acomparisonofthecaseintheofvwiththeothertwoshowsthattheleft-rightmaximaofvareconsecutiveintegersstartingat1.SotoshowthatvisanRGFweonlyhavetoprovethatvi+1>0forallsi2fa;Dg.Notethatforalli1wehavethatmaxfv1;:::;vigisequaltoonemorethanthenumberofb-stepsplusthenumberofupstepsinthei1steps.Thelevell(si)ofanyhorizontalstepisatmostthenumberofpreviousupsteps,soforsi=awehavevi+1=maxfv1;:::;vigl(si)>0.NotethattheareacountedbyA(si)betweensi=Danditscorrespondingupstepexcludingtheareaunderothera-stepsordownstepsisatmostthenumberofupstepsplusb-stepsbetweenandincludingthepairedupanddownstep.Also,thelevelofthedownstepisatmostthenumberofupstepsstrictlybeforeitspairedupstep.AlltogetherA(si)+l(si)isatmostthenumberofupstepsandb-stepsinthei1steps.Asresult,forsi=Dwehavevi+1=maxfv1;:::;vigA(si)l(si)>0.Hence,visanRGF.However,v(R)maynotavoid1221,sowe(R)=inc(v(R))whichavoids1221byLemma4.32.Forthetwo-coloredMotzkinpathRinFigure4wehave(R)=1234125623786.Nextweshowthatarea(R)=lb(v)whichwillimplythatarea(R)=lb((R))byLemma4.33.Itiseasytoseethatlb(v1)=0andifsiisborUthenlb(vi+1)=0.Nextconsidersi=asovi+1=maxfv1;:::;vigl(si).Byequation(18)wehavelb(vi+1)=l(si).Lastly,ifsi=Dthenvi+1=maxfv1;:::;vigA(si)l(si).Byequation(18)again,74babbFigure4Two-coloredMotzkinpathlb(vi+1)=A(si)+l(si).Asaresultlb(v)=Xsi=al(si)+Xsi=D(A(si)+l(si))=area(R)byequation(20).Wenowshowthatthemapbehavesnicelywithrespecttotwooftheusualdecompo-sitionsofMotzkinpaths.Lemma4.35.LetPandQbetwo-coloredMotzkinpathswith(P)=xand(Q)=1y.Themaphasthefollowingproperties.1.(PQ)=x(y+max(x)1).2.(UPD)=(x).Proof.Toprovestatement1,weclaimthatv(PQ)=v(P)(q+max(v(P))1)whereqisv(Q)withitsinitial1deleted.ItisclearfromtheofvthattherstjPjpositionsofv(PQ)arev(P).Alsobyofv,therstoccurrencesotherthantheinitial1areinbijectionwiththeunionoftheupstepsandb-steps.ItfollowsthatthesubwordofoccurrencesinthelastjQjpositionsofv(PQ)isthesameasthecorrespondingsubwordinqwithallelementsincreasedbymax(v(P))1.Thusthemaximumvalueinanyofv(PQ)endinginthesepositionsisincreasedoverthecorrespondingmaximum75inqbythisamount.Furthermore,theareasandlevelsofdownstepsanda-stepsinQinthatportionofPQarethesamesincePendsonthex-axis.So,usingtheofvforthesetypesofsteps,thelastjQjpositionsofv(PQ)areexactlyq0=q+max(v(P))1.Toprovetheequationfor,ittoshowthattheincoperatoronlypermuteselementswithinv(P)andwithinq0.Butthisistruebecauseallelementsofq0aregreaterthanorequaltothoseofv(P).Toprovethesecondstatement,considerv:=v(P)=v1:::vkandu:=v(UPD)=u1:::uk+2.Weclaimthatu=1v1wherevisvbutwithallitsoccurrencesincreasedbyone.Clearlyubeginswitha1.Toseeitmustalsoendwith1,notethatsincethelaststepofUPD=s1:::sk+1isdownstepandthispathdoesnottouchtheaxisbetweenitsinitialandpoints,wehavel(sk+1)=0andA(sk+1)isthetotalnumberofupstepsandb-stepsinUPD.Itnowfollowsfromtheofthemapvandourinterpretationofthemaximumofathatuk+2=1.Letu0beuwithitsinitialandl1'sremoved.Toseethatu0=v,notethateverystepofUPDexcepttheisprecededbyonemoreupstepthaninP.Itfollowseveryoccurrenceofvisincreasedbyoneinpassingtou0.Buttheareaundereacha-stepandundereachdownstepalsoincreasesbyoneduringthatpassage.Sothethev-mapinsuchcaseswillstaythesamefortheserepeatedentries.Itshouldnowbeclearthatu0=v.Itfollowsimmediatelythat(UPD)=inc(1v1)=(x).Beforeweshowthatisabijectionwewillneedamethodfordeterminingfromtheimageofapathwherethatpathreturnstothex-axis.Thefollowinglemmawillprovidethekey.Lemma4.36.GivenpathsP2M2k3andQwithk3,theword(UPDQ)=whaswkastheright-mostrepeatedlettersuchthatw1w2:::wkallthreepropertiesinLemma4.34.Proof.GivenapathR=UPDQ2M2n1asstated,byLemma4.35weknowthatifwe76write(Q)=1qthenw=(R)=((P))(q+m1)wherem=max(((P))).Lemma4.34impliesthatthew1:::wk=((P))allthreeproperties.Soittoshowthatifthereexistsanotherrepeatedletterwiafterwkthenw1:::wifailsproperty(ii)orproperty(iii).Inparticular,ittoshowsuchafailureforthewherewiisthenextrepeatedletterafterwksinceanyotherunderconsiderationcontainsw1:::wi.Ifi=k+1then,sinceeveryelementofqisincreasedbym1andwk+1isrepeated,wemusthavewk+1=m=maxfw1;:::;wkg,contradictingproperty(ii).Ifinsteadi>k+1thenwk+1isaoccurrenceandwk+1=maxfw1;:::;wkg+1=m+1.Byofwi,wehavethatwk+1;:::;wi1arealloccurrenceswithwkandwirepeatedletters.Notethatallelementsinqwereatleast1andthenincreasedbym1,sowemusthavewim=wk+11whichcontradictsproperty(iii).Itwillbehelpfulforustobeabletorefertothespecialrepeatedlettermentionedinthelemmaabove.So,givenanRGFw=w1:::wn,ifthereexistsaright-mostrepeatedletterwksuchthatw1w2:::wkallthreepropertiesinLemma4.34thenwewillsaythatwkbreaksthewordw.Notethatifsucharepeatedletterexists,itsindexkisunique.Theorem4.37.Themap:M2n1!Rn(1221)isabijectionandarea(R)=lb((R)).Proof.Wehavealreadyshownthatisawmapandthatarea(R)=lb((R)).SincejM2n1j=Cn=jRn(1221)j,toshowisabijectionittoshowisinjective.Weprovethisbyinductiononn.Itiseasytoseethatisaninjectionforn2.Wenowassumethatn>2and:M2k1!Rk(1221)isinjectiveforallk<n.WewilldiscussthreecasesforpathsR2M2n1andineachcasewewillshowthatRmapstoaworddistinctfromtheotherwordsinthatcaseandalsofromthewordsinpreviouscases.77FirstconsiderallpathsRwhichstartwithana-stepsothatR=aQforsomepathQ.ByLemma4.35,wehave(R)=11ywhere(Q)=1y.Injectivityofthemapnowfollowsfromthefactthat,byinduction,itisinjectiveonpathsQoflengthn2.OursecondcaseconsistsofpathsRoftheformR=bQ.Now(R)=12(y+1)withyasabove.Clearlythesearedistinctfromthewordsinthepreviousparagraphandinjectivitywithinthiscasefollowsbyinductionasbefore.Forthelastcase,considerallpathsRwhichstartwithanupstepsowecanwriteR=UPDQforpathsP2M2k3andQwherek3.ByLemma4.35wehavew:=(R)=((P))(y+max(((P)))1),andbyLemma4.36therepeatedletterwkbreaksthewordw.Notethatbecause((P))=w1:::wkproperty(i)inLemma4.34,whasmorethanone1andsocannotagreewithawordfromthesecondcaseabove.ButsinceRstartswithanupstep,wstartswiththe12andsocannotbeawordfromthecase.Finally,byuniquenessoftheindexofwk,theinjectivityofthemap,andinductionthewordwisuniquelydeterminedamongallwordsinthiscase.Thistheproofthatisinjective.CombiningthepreviousresultandtheofMn(q)inequation(17)wehavethefollowingCorollary.Corollary4.38.WehaveLBn(1221)=Mn1(q):4.4.3CombinationswithotherpatternsNextweconsidertheRGFswhichavoid1221andanotherlengththreepattern.Since121and122aresubwordsof1221thesecasesarenotinteresting,sowewillfocuson111,112,and123.78Theorem4.39.WehaveforLn:=LBn(111;1221)thatL0=L1=1and,forn2,andLn=Ln1+Ln2+n2Xk=1qkLk1Lnk1Proof.LetNnbethecollectionoftwo-coloredMotzkinpathsR2M2nsuchthat(R)avoids111.N1(q)=1and,forn0,Nn(q)=XR2N2nqarea(R):ByTheorem4.37weonlyneedtoshowthatNn(q)=Rn+1(111;1221)anequivalentrecurrenceandinitialconditions.ByN1(q)=1andN0(q)=1becauseoftheemptypath.Sowewishtoshowthatforn1Nn(q)=Nn1(q)+Nn2(q)+n2Xk=0qk+1Nk1(q)Nnk2(q):(21)WepartitionM2nasintheproofofTheorem4.37:S=fR=aQ:Q2M2n1g;T=fR=bQ:Q2M2n1g;U=fR=UPDQ:P2M2k;Q2M2nk2andk2[0;n2]g;WeclaimthatwhenwerestrictthispartitiontopathsinNnwehaveSN=fR=abQ:Q2Nn2g;TN=fR=bQ:Q2Nn1g;U1=fR=UDQ:Q2Nn2g;U2=fR=UbPDQ:P2Nk1;Q2Nnk2andk2[n2]g;79wherethesetUbreaksintotwosubsets.Fromthesecondpartitionwewillbeabletodeducethedesiredrecursion.ConsiderapathR=aQ2S.Weclaimthat(R)avoids111ifandonlyifQ=bQ0forQ02Nn2whichwillshowthatSrestrictstoSN.Ifwewrite(Q)=1ywehave(R)=11y.Theword(R)avoids111ifandonlyifthewordyhasno1'sandatmosttwocopiesofeveryothernumber.NotethatthesecondcaseconsideredinTheorem4.37containedallpathswhichstartedwithab-stepandthatthesepathsweremappedbijectivelytowordswithexactlyone1.Itisalsoclearthaty=(Q0)+1hasatmosttwocopiesofeverynumbergreaterthanoneifandonlyifthesameistrueof(R).Theclaimnowfollows.Becausearea(R)=area(Q0)summingoverallpathsinthiscasegivesusthetermNn2(q).IfinsteadR=bQ2Tthen,usingthatnotationofLemma4.35(R)=12(y+1)=1((Q)+1).So(R)avoids111ifandonlyif(Q)does.ItfollowsthatTrestrictstoTN.Becausearea(R)=area(Q)summingoverallpathsinthiscasegivesusthetermNn1(q).Next,weconsiderpathsR=UPDQfromthethirdpartU.FirstconsiderthecasewherePhaslength0soR=UDQ.Wewanttoprovethat(R)avoids111ifandonlyif(Q)avoids111sincethiswillshowthatthecollectionofpathsinUwithjPj=0restrictstoU1.Ifwewrite(Q)=1ywehave(R)=121(y+1).Thus(Q)avoids111ifandonlyif(R)doesandtherestrictionisasclaimed.Becausearea(R)=1+area(Q)summingoverallpathsinthiscasegivesusthetermqNn2(q)whichisthek=0terminequation(21).Lastly,considerapathR=UPDQwithjPj=k2[n2]whicharetheremainingpathsinU.Wewillshowthat(R)avoids111ifandonlyifP=bP0andboththewords(P0)and(Q)avoid111.ThiswillshowthattheremainingpathsinUrestricttoU2inthesecondpartition.Firstwemakeanobservationabout((P)).Letm=max((P))andf1s1;:::;msmgbethemultisetofalllettersin(P).Themapincreasesalloccurrencesbyoneandaddstwo1'sbutotherwisedoesn'tthecollectionofletters.Sothemultisetoflettersin((P))isf1s1+1;:::;msm;m+1g.Ifwewrite(Q)=1ywehave(R)=((P))(y+m)sincem=max(((P)))1.Iff1t1;:::;mtmgisthemultisetofletters80in(Q)thenthemultisetoflettersin(R)isf1s1+1;:::;msm;(m+1)t1;:::;(m+m)tmg.So(R)avoids111ifandonlyifthereareatmosttwoofanyelementinthissetwhichisequivalenttos1=1,si2fori>1,andti2foralli1.Furtherthisimpliesthat(R)avoids111ifandonlyifQ2Nnk2and(P)hasexactlyone1andavoids111.Justasinourcase,(P)hasexactlyone1andavoids111ifandonlyifP=bP0forsomeP02Nk1.Becausearea(R)=area(P0)+area(Q)+k+1summingoverallpathsinthiscasegivesusthetermqk+1Nk1(q)Nnk2(q)fork>0.Thiscompletestheproofofthetheorem.ThenexttwoavoidanceclassescanbecharacterizedbyacombinationofTheorem2.5andLemma4.32.Theproofsarestraightforwardandsonotincluded.Proposition4.40.WehaveRn(112;1221)=f12:::mknm:k2[m]g:Assuch,forn0wehave1.Fn(112;1221)=nXm=1mXk=1q(nm)(mk)r(m2)+(nm)(k1)s(m2)tmk;2.LBn(112;1221)=nXm=1mXk=1q(nm)(mk);3.LSn(112;1221)=nXm=1mXk=1q(m2)+(nm)(k1);4.RBn(112;1221)=nXm=1mq(m2);and5.RSn(112;1221)=nXi=1iqni:Proposition4.41.WehaveRn(123;1221)=f1n;11i21j2k:i+j+k=n2;andi;j;k0g:81Assuch,forn0wehave,usingtheKroneckerdeltafunction,1.Fn(123;1221)=1+Xi+j+k=n2i;j;k0qjrk+1si+1+j(10;k)t10;j;2.LBn(123;1221)=1+n2Xj=0(nj1)qj;3.LSn(123;1221)=1+n2Xk=0(nk1)qk+1;4.RBn(123;1221)=1+qn1+n2Xk=1(k+1)qk;and5.RSn(123;1221)=n+n12q:4.4.4Moreaboutthepattern1212ItturnsoutthatthegeneratingfunctionLBn(1212)isalsoequaltoMn1(q).Insteadofshowingthisdirectly,weprovethatLBn(1212)=LBn(1221)andthenCorollary4.38completestheproof.IntheprocesswealsoshowLSn(1212)=LSn(1221).Proposition4.42.Therestrictioninc:Rn(1212)!Rn(1221)isabijectionwhichpreserveslbandls.Proof.ByLemma4.32wehavelb(w)=lb(inc(w)).Thismapalsopreserveslsbecausewandinc(w)arerearrangementsofeachotherandls(wi)=wi1foranyRGFw.Nowweonlyneedtoshowthatinc:Rn(1212)!Rn(1221)isbijective.SincejRn(1212)j=Cn=jRn(1221)jittoshowthemapisinjective.Assumethatv=v1v2:::vnandw=w1w2:::wnaretwodistinctwordswhichavoid1212,butinc(v)=inc(w).Thismeansthatvandwsharethesamepositionsofoccurrences,andthesamemultisetofrepeatedletters.Butsincev6=wthereisthenasmallestindexi1suchthatv1:::vi1=w1:::wi1butvi6=wi.Withoutlossofgeneralityletvi=a,wi=b,anda<b.Wehavenotedthatvandwhavetheiroccurrencesatthesameindices,soviandwimustberepeatedletters.82SincewisanRGF,theoccurrenceofaandbmustoccurbeforewi,sovalsohasthesubwordabbeforevi.However,becausevandwhavethesamecollectionofrepeatedlettersthebwhichiswiinwmustoccursometimeafterviinv.ThismeansthatvhasthesubwordababcontradictingLemma4.20.Corollary4.43.Fork0wehaveFn(1212;q;r;1;1)=Fn(1221;q;r;1;1);Fn(1k;1212;q;r;1;1)=Fn(1k;1221;q;r;1;1);andFn(12:::k;1212;q;r;1;1)=Fn(12:::k;1221;q;r;1;1):Proof.ThebijectionfinProposition4.42preservesthenumberoftimesanyletterappearsandpreservesthemaximalletter.Theequalitiesfollowfromthisfact.UsingCorollary4.24,Propositions4.29and4.41,andCorollaries4.38and4.43wehavethefollowingequalitieswhichsummarizemanyoftheequationswehavefromresultsinthissection.Corollary4.44.Wehave,foralln0,LBn(1212)=RSn(1212)=LBn(1221)=Mn(q);LBn(111;1212)=LBn(111;1221);LSn(111;1212)=LSn(111;1221);LBn(123;1212)=RSn(123;1212)=LBn(123;1221);and83LSn(123;1212)=RBn(123;1212)=LSn(123;1221):84REFERENCES85REFERENCES[Arm09]DrewArmstrong.GeneralizednoncrossingpartitionsandcombinatoricsofCox-etergroups.Mem.Amer.Math.Soc.,202(949):x+159,2009.[BBES14]MarilenaBarnabei,FlavioBonetti,SergiElizalde,andMatteoSilimbani.Descentsetson321-avoidinginvolutionsandhookdecompositionsofintegerpartitions.J.Combin.TheorySer.A,128(1):132{148,November2014.[CDD+13]WilliamY.C.Chen,AlvinY.L.Dai,TheodoreDokos,TimDwyer,andBruceE.Sagan.On021-avoidingascentsequences.Electron.J.Combin.,20(1):Paper76,6,2013.[CEKS13]Szu-EnCheng,SergiElizalde,AnisseKasraoui,andBruceE.Sagan.Inversionpolynomialsfor321-avoidingpermutations.DiscreteMath.,313(22):2552{2565,2013.[DDG+]SamanthaDahlberg,RobertDorward,JonathanGerhard,ThomasGrubb,CarlinPurcell,LindseyReppuhn,andBruceE.Sagan.Restrictedgrowthfunctionpatternsandstatistics.Inpreparation.[DDG+16]SamanthaDahlberg,RobertDorward,JonathanGerhard,ThomasGrubb,Car-linPurcell,LindseyReppuhn,andBruceE.Sagan.Setpartitionpatternsandstatistics.DiscreteMath.,339,2016.[DDJ+12]TheodoreDokos,TimDwyer,BryanP.Johnson,BruceE.Sagan,andKimberlySelsor.Permutationpatternsandstatistics.DiscreteMath.,312(18):2760{2775,2012.[Dra09]BrianDrake.Limitsofareasunderlatticepaths.DiscreteMath.,309(12):3936{3953,2009.[DS11]PaulDuncanandEinarSteingrsson.Patternavoidanceinascentsequences.Electron.J.Combin.,18(1):Paper226,17,2011.[Foa68]DominiqueFoata.OntheNettoinversionnumberofasequence.Proc.Amer.Math.Soc.,19:236{240,1968.[GM09]AdamM.GoytandDavidMathisen.Permutationstatisticsandq-Fibonaccinumbers.Electron.J.Combin.,16(1):ResearchPaper101,15pp.,2009.[Goy08]AdamM.Goyt.Avoidanceofpartitionsofathree-elementset.Adv.inAppl.Math.,41(1):95{114,2008.[GS09]AdamM.GoytandBruceE.Sagan.Setpartitionstatisticsandq-Fibonaccinumbers.EuropeanJ.Combin.,30(1):230{245,2009.86[HR01]J.HaglundandJ.B.Remmel.Rooktheoryforperfectmatchings.Adv.inAppl.Math.,27(2-3):438{481,2001.SpecialissueinhonorofDominiqueFoata's65thbirthday(Philadelphia,PA,2000).[JM08]VJelandTMansour.Onpattern-avoidingpartitions.ElectronJ.Combin.,15(R39):1{52,2008.[Kil]KendraKillpatrick.Wilfequivalenceforthechargestatistic.PreprintarXiv:1204.3121.[Kla96]MartinKlazar.Onabab-freeandabba-freesetpartitions.EuropeanJ.Combin.,17(1):53{68,1996.[Kla00a]MartinKlazar.Countingpattern-freesetpartitions.I.AgeneralizationofStirlingnumbersofthesecondkind.EuropeanJ.Combin.,21(3):367{378,2000.[Kla00b]MartinKlazar.Countingpattern-freesetpartitions.II.Noncrossingandotherhypergraphs.Electron.J.Combin.,7:ResearchPaper34,25pp.,2000.[Knu73]DonaldE.Knuth.Theartofcomputerprogramming.Volume3.Addison-WesleyPublishingCo.,Reading,Mass.-London-DonMills,Ont.,1973.Sortingandsearching,Addison-WesleySeriesinComputerScienceandInformationProcess-ing.[Kre72]G.Kreweras.Surlespartitionsnoncroiseesd'uncycle.DiscreteMath.,1(4):333{350,1972.[Mac78]PercyAlexanderMacMahon.Collectedpapers.Vol.I.MITPress,Cambridge,Mass.,1978.Combinatorics,MathematiciansofOurTime,EditedandwithaprefacebyGeorgeE.Andrews,WithanintroductionbyGian-CarloRota.[MS12]TMansourandMarkShattuck.Pattern-avoidingsetpartitionsandcatalannumbers.Electron.J.Combin.,18:1{18,2012.[MT04]AdamMarcusandGaborTardos.ExcludedpermutationmatricesandtheStanley-Wilfconjecture.J.Combin.TheorySer.A,107(1):153{160,2004.[Sag10]BruceE.Sagan.Patternavoidanceinsetpartitions.ArsCombin.,94:79{96,2010.[SS85]RodicaSimionandFrankW.Schmidt.Restrictedpermutations.EuropeanJ.Combin.,6(4):383{406,1985.[SS12]BruceE.SaganandCarlaD.Savage.Mahonianpairs.J.Combin.TheorySer.A,119(3):526{545,2012.[Sta]RichardStanley.Catalanaddendum.NewproblemsforEnumerativeCombina-torics.Vol.2,availableathttp://math.mit.edu/~rstan/ec/catadd.pdf.87[Sta97]RichardP.Stanley.EnumerativeCombinatorics.Vol.1,volume49ofCambridgeStudiesinAdvancedMathematics.CambridgeUniversityPress,Cambridge,1997.WithaforewordbyGian-CarloRota,Correctedreprintofthe1986original.[Sta99]RichardP.Stanley.EnumerativeCombinatorics.Vol.2,volume62ofCambridgeStudiesinAdvancedMathematics.CambridgeUniversityPress,Cambridge,1999.WithaforewordbyGian-CarloRotaandappendix1bySergeyFomin.[WW91]MichelleWachsandDennisWhite.p;q-Stirlingnumbersandsetpartitionstatis-tics.J.Combin.TheorySer.A,56(1):27{46,1991.88