; TeX output 2003.04.24:0953 KE&:9color push Blackhtml:color push gray 0 color pop html:KXQ cmr121G color pop3ڍ:9|&html: html:.MTvkcolor push Black color popZVg5PSfile=logo129.eps llx=0 lly=0 urx=99 ury=16 rwi=28807獍&{<color push Black color pop,[8N q cmbx12A
NoteonRationalSuccessionRules.s獒 WXQ ff cmr12Enrica/Duchi 5E}Dipartimento/diSistemieInformatica,ViaLombroso6/17 |50134/Firenze,Italy 0)html:color push cmyk 0 1 0 0߆T ff cmtt12duchi@dsi.unifi.it html: color pop Andrea/F4rosiniNDipartimento/diMatematica,ViadelCapitano,15 53100/Siena,Italy 'html:color push cmyk 0 1 0 0frosini@unisi.it html: color pop m'Renzo/Pinzani5E}Dipartimento/diSistemieInformatica,ViaLombroso6/17 |50134/Firenze,Italy +html:color push cmyk 0 1 0 0pinzani@dsi.unifi.it html: color pop Simone/RinaldiNDipartimento/diMatematica,ViadelCapitano,15 53100/Siena,Italy 'html:color push cmyk 0 1 0 0rinaldi@unisi.it html: color pop(Ӎ vcolor push Black color pop r"V
3
cmbx10AbstractMƍlcolor push Black color pop-̻K`y
3
cmr10SuccessionVrulesha!vingarationalgeneratingfunctionareusuallycalled ':
3
cmti10rpational
_sucpcessionrules.Injthisnotew!ediscusssomeproblemsconcerningrationalsuccession_rules,and~determineasimplemethoMdtopassfromarationalgeneratingfunctiontoa_rationalfsuccessionrule,bMothdeningthesamen!umberfsequence. :9color push BlackG color pop *KE&:9color push Blackhtml:color push gray 0 color pop html:K2G color pop3ڍ:9|&html: html: N G cmbx121(Inutro =ductionb# AG] @ cmti12sucffcessiont
ruleGisaformalsystemdenedbryanaxiom-g(#g cmmi12a),au&!",
cmsy102/
msbm10N2!|{Y cmr8+x,andGasetofprffoductionsyf(k$2 cmmi8tʹ)UR,
msam10 (e1(kt))(e2(kt))(ek %; cmmi6tI}(kt))UR:t2Ng;wherepei,:URN2+
q #!N2+x,HwhicrhexplainshowtoderivethesucffcessorsM(e1(kg));(e2(k));:::ʜ;(ek tI}(k))ofanrygivenlabSel(kg),cko2URN2+x. Ingeneral,forasuccessionrule
,wreusethemorecompactnotation:8 html: html: $
UR:q)u
cmex10dUS(a)US(kg) (e1(k))(e2(k))(ek#(k)):ƽù(1)The1labffels(a),C=(kg),(eidڹ(k))1of
areassumedtoconrtainonlypSositiveintegers.
zTherule
canbSerepresenrtedbymeansofagenerffatingWtree,Kthatis,aroSotedtreewhosevrerticesarelabSelled8qwiththelabelsof
:q(a)isthelabeloftheroot,Kandeacrhnodelabelled(kg)haskcrhildrenlabSelledbye1(kg);:::ʜ;ek#(k)respSectivelyV,accordingtotheproSductionof(kg)denedinjq(html:color push cmyk 0 1 0 01 html: color pop).:AjPsuccessionrule
denesasequenceofpSositivreintegers(fnP)n'K cmsy80̹,cwherefn
isthenrumbSerKofthenodesatlevrelninthegeneratingtreedenedby
.ByconventiontheroSotisatxklevrel0,Dsof0V=UR1.Thefunctionf
(x)=Pn0"fnPx2n isthegenerffating4functiondeterminedbry
.SuccessionxrulesarecloselyrelatedtoamethoSdfortheenrumerationandgenerationofcomrbinatorialstructures,LcalledtheECO˽methoffd.+7FVorfurtherdetailsandexamplesabSoutsuccessionGrulesandtheECOmethoSdwrereferto[html:color push cmyk 0 1 0 0BDLPP html: color pop(];in[html:color push cmyk 0 1 0 0FPPR html: color pop M]theauthorsstudysuccessionrulesfromanalgebraicpSoinrtofview.Twro3rulesareeffquivalentiftheyhavethesamegeneratingfunction.A+successionruleisniteifithasanitenrumbSeroflabelsandproductions;forexample,theruleUThtml: html:*fX 8
ԍ < :fd ƞ?(2) ƞ?(2)UR (2)(3) ƞ?(3)UR (2)(3)(3);ƽù(2)!deningz,oSdd-indexFibonaccinrumbersz,1;2;5;13;34;89;233;:::Dʹ(sequenceA001519in[html:color push cmyk 0 1 0 0SL html: color pop
ދ])isniteanditisequivXalenrttohtml: html:* zqd z(2) z(kg)UR (2)2k6 1 (kŹ+2);ƽù(3)ewhicrhisnotnite.Figurehtml:color push cmyk 0 1 0 01 html: color popdepictstherstlevrelsofthegeneratingtreesassoSciatedwiththerulesin(html:color push cmyk 0 1 0 02 html: color pop)and(html:color push cmyk 0 1 0 03 html: color pop).AccordingDtoourdenition, trwoDlabSelsconrtainingthesameintegerkaareallowedtoharveQadierenrtproSduction.mIfthishappenswredistinguishthoselabelsusingsomeindices(orncffolors,seeExamplehtml:color push cmyk 0 1 0 01 html: color pop).2A2successionruleiscalledrational,algebraicortrascendentalaccordingtothegeneratingfunctiontrypSe.Rationalsuccessionrulesarethesub jectofthisnote(seealso[html:color push cmyk 0 1 0 0GFrGT html: color pop"D/],[html:color push cmyk 0 1 0 0FPPR html: color pop M]).Belorwwelistsomeclassesofgeneratingfunctions: :9color push BlackG color pop SKE&:9color push Blackhtml:color push gray 0 color pop html:K3G color pop3ڍ:95color push Blackz:ˍ*ZVg?ps::[begin] 18945146 6251895 0 0 29470228 9801482 startTexFig
ps:: doclip ps: plotfile array.eps ps::[end] endTexFig _ew Q"xcolor push BlackFigure1:8html:color push gray 0 color pop html:TherstlevrelsoftwoequivXalentgeneratingtrees. color pop color pop Z=color push Black5N cmbx12- color pop5R isthesetofrationalgeneratingfunctionsofinrtegersequences(Z ܞ-rationalfunctions, $%usingthenotationin[html:color push cmyk 0 1 0 0SS html: color pop
0]); Z=color push Black- color pop5R2+ isthesetofrationalgeneratingfunctionsofpSositivreintegersequences;Z=color push Black- color pop5RJE Gisthesetofgeneratingfunctionsofregularlanguages;Z=color push Black- color pop5S
isthesetofrationalgeneratingfunctionsofsuccessionrules;Z=color push Black- color pop5Fisthesetofgeneratingfunctionsofnitesuccessionrules. -Summarizingtheresultsin[html:color push cmyk 0 1 0 0SS html: color pop
0],[html:color push cmyk 0 1 0 0FPPR html: color pop M]wreobtainthefollowingscheme: c֟RJE G +%Xps: gsave currentpoint currentpoint translate -45 neg rotate neg exch neg exch translate UW ps: currentpoint grestore moveto ȟ*EF )-Wps: gsave currentpoint currentpoint translate 45 neg rotate neg exch neg exch translate UW ps: currentpoint grestore moveto 90Xps: gsave currentpoint currentpoint translate -45 neg rotate neg exch neg exch translate UW ps: currentpoint grestore moveto+IR2+%֟(7b*ER )Q|S @Wps: gsave currentpoint currentpoint translate 45 neg rotate neg exch neg exch translate UW ps: currentpoint grestore movetoj-TheclassesR,jaRJE G,andFNaredecidable,jawhileR2+:isnotdecidable.In[html:color push cmyk 0 1 0 0FPPR html: color pop M]is:9conjecturedthatFc=URS b,i.e.,evreryrationalruleisequivXalenttoaniteone.-ThisLnotepropSosesasimpletooltopassfromarationalgeneratingfunction(i.e.,l|alinear:9recurrencerelation)deninganon-decreasingsequenceofpSositivreintegerstoasuccession:9ruledeningthesamesequence.8Theresultsextendthosein[GFrGT].-FVurthermoreourtecrhniqueprovidesinterestingcombinatorialinterpretations(interms:9of9generatingtrees)forsequencesthataredenedbryalinearrecurrencerelation,MWusingan:9approacrhdierentfromthatin[html:color push cmyk 0 1 0 0BDFR html: color pop!]and[html:color push cmyk 0 1 0 0BR html: color pop].-AsanapplicationofourmethoSd,wregiveasimplesolutiontoaproblempropSosedby:9JimˣPropponthemailinglist\domino"(1999),whereheaskredforthecombinatorialinter-:9pretationBofthesequence1;1;1;2;3;7;11;26;:::(sequenceBA005246in[html:color push cmyk 0 1 0 0SL html: color pop
ދ])denedbrythe:9linearrecurrencerelation:
Xqd
Yf0V=UR1;
f1=1;
f2=1;
f3=2
Yfn=UR4fn 2/t fn 4: :9color push BlackG color pop KE&:9color push Blackhtml:color push gray 0 color pop html:K4G color pop3ڍ:9|&html: html: 2(Twuoztermlinearrecurrences.b# WVestartbryconsideringtwo-termlinearrecurrences:\ TAfn=URh1fn 1/t+h2fn 2;h1;h2V2Zwitheinitialconditionsf0˹=&1,zf1=s02N2+x.TheepSositivitryofthesequenceisensuredbytheadditionalconditionsh1V2URN2+x,andh1j+h2>UR0.UThtml: html:ݿ color push BlackProp` osition 1 color popUThe35sucffcessionrule u
UR=qdUS(s0)US(kg)2Tq
lasy10;(1)2k6 1 ((k))3;!/with35(kg)UR=(h1j 1)kŹ+h2+1,35denestheseffquence35(fnP)n0.3Pro` of.6WVeharvef0V=UR1andf1=URs0.6Letk1;k2;:::ʜ;kfqn(q% cmsy6 "Aa cmr62 HbSethelabelsatlevreln 2ofthegeneratingtreeof
.8Then,fornUR2,pfn=URk1j+k2+UN+kfqn 2 fn 2/t+(h1 1)(k1+k2+UN+kfqn 2%O)+fn 2̹(h2+1):Consequenrtlywehave$P)fn=URfn 1/t fn 2+(h1j 1)fn 1+fn 2̹(h2j+1)UR=h1fn 1/t+h2fn 2DnUR2:ꨄ * * uAVtsuccessionVruledeningthesequence(fnP)n0\canhorweverVhaveamoregeneralform,sucrhas: a
2V=URqdUS(s0)US(kg)UR;(c)2k6 1 ((k))Lwhere_Ac;s02N2+x,|g(kg)=(h1 c)ka(+h2+c,|gand_AthepSositivitryofthelabelsisensuredbrythefollorwingconditions:3color push Black
L(i) color pop_ifcURs0then1ch1and((h1j c)c+h2+c)UR>0;,čcolor push Black(ii) color pop_ifcUR>s0thens0Vch1and((h1j c)s0+h2+c)UR>0.Uhtml: html: 3(Linearzrecurrenceswithmorethantuwozterms.b#InNMthissectionwreconsiderthegeneralcaseoflinearrecurrencesdeningnon-decreasingsequencesofpSositivreintegers,handwegivetheexplicitformofsuccessionrulesdeningsuchsequences.FVor*DthesakreofsimplicityV,:*letusstartbystudyingthecaseofthreetermrecurrencesoftheform hfn=URh1fn 1/t+h2fn 2+h3fn 3;'withf 1ι=UR0,f0V=1,f1V=s02N2+x,whereh1V2N2+ andh2;h3V2Z. :9color push BlackG color pop -KE&:9color push Blackhtml:color push gray 0 color pop html:K5G color pop3ڍ&:9Ontheotherhand,letusconsidertherule *
3V=fXUR8
ԍUR<UR:)9(s0)*(kg)UR;(c)i*k6 1#u((920(k)) ko=URs0
7;c(kg)UR;(c)i*k6 1#u((921(k))$O:9wherecUR2N2+x,andfd Q20(kg)UR=(h1j c)kŹ+h2+c; Q21(kg)UR=(h1j c)kŹ+h2+h3+c:(R:9ThefollorwingconditionseasilyensurethatthelabSelsof
3{arepositivreand,,asaconsequence,:9thesequencedenedbry
3ispSositiveandnon-decreasing. :9color push Black(i) color pop$%IfcURs0then1ch1,(|l20(c))*I>UR0and21(Q20(c))-5>UR0. :9color push BlackP(ii) color pop$%IfcUR>s0thens0Vch1,(|l20(s0))/1>UR0and21(Q20(s0))2Y>UR0.:9 html: html: color push BlackProp` osition 2 color popUThe35sucffcessionrule
39denesthesequence(fnP)n0.Pro` of.*WVecaneasilyvrerifythatf0V=UR1,f1=s0andf2=h1s0
+Uh2.*FVorn3thenrumbSer ofoSccurrencesofthelabelcatlevreln 3isequaltofn 2/t fn 3̹,soweobtain fn=URcfn 1u cfn 3+(h1I c)fn 1+(h2I+h3+c)fn 3u cUR(fn 2 fn 3̹)+(h2I+c)(fn 2 fn 3̹);whicrhsimpliestofn=URh1fn 1/t+h2fn 2+h3fn 3otfornUR3.8 * *$html: html:܍ color push BlackExample 1 color popDUQThesequence(fnP)n0otsatisfyingtherecurrencerelation bfn=UR3fn 1/t 2fn 2+fn 3;withf1V=UR0;f0=1;f1=2;isdenedbrythesuccessionrule/UR3 8
ԍ > > < > > :&e