Enumeration of The Number of Dyck Paths of Semi-Length n obeying various restrictions By Shalosh B. Ekhad The number of Dyck paths with semi-length n is famously the Catalan numbers\ . In this article we will explicitly enumerate Dyck paths with four kinds of \ restictions where one of more of the conditions below are forbidden (i) the heights of the peaks are not allowed to to be of the from, 5 r + 1 (ii) the heights of the valleys are not allowed to take certain values, 5 r + 1 (iii) the upward runs can't have certain values, 5 r + 1 (iv) the downward runs can't have certain values, 5 r + 1 ------------------------------------------------------------ Theorem Number, 1 Let a(n) be the number of Dyck paths of semi-length n To make it crystal clear here is such a path of semi-length 8 5+ H H + HH H H HH + H HH HH H + HH H H HH 4+ H H H H H + HHH H HH HH H + HH H HH H H HH + H HH H HH H H 3+ H H H H + HH HH + H H + HH HH 2+ H H + H H + HH HH + H H 1+ H H + HH HH + H H +HH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (2 n - 1) a(n - 1) a(n) = -------------------- n + 1 subject to the initial conditions [a(1) = 1] Just for fun, a(1000), equals 2046105521468021692642519982997827217179245642339057975844538099572176010191\ 891863964968026156453752449015750569428595097318163634370154637380666882\ 886375203359653243390929717431080443509007504772912973142253209352126946\ 839844796747697638537600100637918819326569730982083021538057087711176285\ 777909275869648636874856805956580057673173655666887003493944650164153396\ 910927037406301799052584663611016897272893305532116292143271037140718751\ 625839812072682464343153792956281748582435751481498598087586998603921577\ 523657477775758899987954012641033870640665444651660246024318184109046864\ 244732001962029120 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364, 176733862787006701400, 680425371729975800390, 2622127042276492108820, 10113918591637898134020, 39044429911904443959240, 150853479205085351660700, 583300119592996693088040, 2257117854077248073253720, 8740328711533173390046320, 33868773757191046886429490, 131327898242169365477991900, 509552245179617138054608572, 1978261657756160653623774456, 7684785670514316385230816156, 29869166945772625950142417512, 116157871455782434250553845880, 451959718027953471447609509424, 1759414616608818870992479875972, 6852456927844873497549658464312, 26700952856774851904245220912664, 104088460289122304033498318812080, 405944995127576985730643443367112, 1583850964596120042686772779038896, 6182127958584855650487080847216336, 24139737743045626825711458546273312, 94295850558771979787935384946380125, 368479169875816659479009042713546950, 1440418573150919668872489894243865350, 5632681584560312734993915705849145100, 22033725021956517463358552614056949950, 86218923998960285726185640663701108500, 337485502510215975556783793455058624700, 1321422108420282270489942177190229544600, 5175569924646105559418940193995065716350, 20276890389709399862928998568254641025700, 79463489365077377841208237632349268884500, 311496878311103321137536291518809134027240, 1221395654430378811828760722007962130791020, 4790408930363303911328386208394864461024520, 18793142726809884575211361279087545193250040, 73745243611532458459690151854647329239335600, 289450081175264899454283846029490767264392230, 1136359577947336271931632877004667456667613940, 4462290049988320482463241297506133183499654740, 17526585015616776834735140517915655636396234280, 68854441132780194707888052034668647142985206100, 270557451039395118028642463289168566420671280440, 1063353702922273835973036658043476458723103404520, 4180080073556524734514695828170907458428751314320, 16435314834665426797069144960762886143367590394940, 64633260585762914370496637486146181462681535261000, 254224158304000796523953440778841647086547372026600, 1000134600800354781929399250536541864362461089950800, 3935312233584004685417853572763349509774031680023800, 15487357822491889407128326963778343232013931127835600, 60960876535340415751462563580829648891969728907438000, 239993345518077005168915776623476723006280827488229600, 944973797977428207852605870454939596837230758234904050, 3721443204405954385563870541379246659709506697378694300, 14657929356129575437016877846657032761712954950899755100, 57743358069601357782187700608042856334020731624756611000, 227508830794229349661819540395688853956041682601541047340, 896519947090131496687170070074100632420837521538745909320, 3533343320884635898708258511468514257188006702535057407320, 13927547459020991989083038404429289207944958458536245702640, 54906677482678910726192747555923159377475316999998660943100, 216489185503133990863274261791925599831188392742851863147080, 853702637172735926234421145556838686126761775155774328259240, 3366939372774715522158184331074634818182181954352680060985040, 13280705303722489004068393750349948449496384375502238018329880, 52391773216519910749994580850004383791591241114366627044787600, 206709359781542193322705891717290023323187260396682873976707440, 815663960219058384462569194343901173113117297781505394610791520, 3218959557293069695825496284821467129607123621602012360874730820, 12704920022590345879098861442746675573493602966676969141151592440, 50151000089172417943811295168736877263790538026356457136124707000, 197987426438993719534698504405274280676181776208398535128701017200, 781708976802233823680102715669100177152510806064194216284009188600, 3086748267372923303762456877257472494397093952150920751480446539600, 12190039767760866606383939871203238833805472726290924323643119385200, 48145535217206784075634048230802707999063631776107012034556858076000, 190174864107966797098754490511670696596301345515622697536499589400200, 751269297881058917464501210451062751843240026086509499359064493663600] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 2 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 5+ H + HH H + H HH + HH H 4+ H H H + H HH HHH + HH H HH H + H HH H HH 3+ H H H H + HH H H HH + H H HH H + HH HHH HH 2+ H H H H + H H HHH + HH HH H HH + H H HH H 1+ H H H + HH HH + H H +HH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 6 5 4 4 3 3 2 2 P(x) x + P(x) x + P(x) x + P(x) x - P(x) + 1 = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 3, 6, 14, 36, 83, 223, 548, 1463, 3789, 10102, 26960, 72427, 196354, 533155, 1459158, 4001154, 11029269, 30484089, 84548379, 235156302, 655735953, 1833153601, 5135741405, 14419261231, 40560371101, 114302565563, 322652846665, 912224361889, 2582916247215, 7323553321242, 20792332104091, 59104440656111, 168207251185140, 479235235944032, 1366809001163170, 3902101297480081, 11150634603133038, 31892687728409840, 91296611679112514, 261561064685027234, 749946664368204571, 2151848024846342016, 6178780264862793632, 17753777112020362358, 51046191915990272562, 146861843711635625042, 422782302640197395313, 1217801785473016272860, 3509770915032834282703, 10120785157703841139493, 29199426960206832426669, 84285141338238483522146, 243408977641033645940392, 703272705354424548358166, 2032851337438649345736952, 5878622923826844749366840, 17006990922032516878568291, 49221553693571655579253018, 142512669234844557419716074, 412778027454392734660353808, 1196022865619530838795184503, 3466708434000241788498335176, 10051836242320537794909094006, 29155418772148565244180469181, 84593050834618012141071259243, 245520373392247425839507361109, 712810223556543328812416753699, 2070094145136330081404741573541, 6013571501191167332197882656260, 17474212987319706807329417621370, 50790470041475972327885352549864, 147666890448097620038211303697272, 429434835686374792898504482369180, 1249170527840811142815108070308562, 3634575434514670465004287210425262, 10577680258744298412199826138199351, 30791395012437739895028857954924396, 89653647876776180504693567021921568, 261098161658645785010810494373724021, 760561922279376449966615272384106730, 2215940056172807806616508926995683704, 6457611758340829680470487653613265217, 18822367624094358920116115309169741303, 54873535844069525687973279006257937069, 160005922296827189233377127488552375525, 466650459809795848791950708163209179809, 1361219118874827255543071462613595245228, 3971397126438082576665161887433845702185, 11588729327094956851892769369491746489957, 33822358778991300894521200975820231045302, 98729271745508524096856368430601517600504, 288244077116485267523850704197120612119580, 841677590935291353336410707208311139466354, 2458105926865241218504021014125252502527703, 7179983857695435138294008371294775747317478, 20975533535979607697117324152636124962970206, 61286936158739917083557388661179084572281984, 179096402117822814967863145889975334731802485, 523442060037000375499037362265129249122450229, 1530072327663595264163887701417733571713422989, 4473173193518870098564347636155951186810150052, 13079126141414021517427462417722610543197107898, 38247221448416237813529400786221366274848459391, 111860850335623448506962153874436737096291369618, 327199290317276234405459507880723184037385437431, 957197544501410525141546685013787239952225094345, 2800559398254571827556141817428334412418579129425, 8194850224213833044800796845711501768394691884574, 23982217018333593098022233211733652316873762599204, 70192190212060096228392308407048910277678336967556, 205465316549638435611494064326799484380284413283561, 601502781616729601895882112140318304609319102164410, 1761105203763979140388664899082962235112950247649002, 5156804594903318590283975550873518629778576701799265, 15101599835841653668927168268194546704516125232647579, 44229432100151074307521125063273180685553098592867523, 129552298847675795050449357358118317657610051583634383] ------------------------------------------------------------ Theorem Number, 3 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 2+ H H H H + HH HH HH HH + HH HH HH HH + H H H H H H H H + H H H H H H H H 1.5+ H HH H H H H H H + H H H H H H H H + H H H H H H H H + H H H H H H H H + H H H H H H H H 1+ H H H H H H H H + H H H H H H H H + H H H H H H H H + H H H H H H H H + H H H H H H H H 0.5+ HH H H H H H H HH + H H H H H H H H + H H H H H H H H +H HH HH HH H +H HH HH HH H -*-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-+*-+-+-+-+-++-+-+-+-*+-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 6 5 4 4 3 3 2 2 P(x) x + P(x) x + P(x) x + P(x) x - P(x) + 1 = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 3, 6, 14, 36, 83, 223, 548, 1463, 3789, 10102, 26960, 72427, 196354, 533155, 1459158, 4001154, 11029269, 30484089, 84548379, 235156302, 655735953, 1833153601, 5135741405, 14419261231, 40560371101, 114302565563, 322652846665, 912224361889, 2582916247215, 7323553321242, 20792332104091, 59104440656111, 168207251185140, 479235235944032, 1366809001163170, 3902101297480081, 11150634603133038, 31892687728409840, 91296611679112514, 261561064685027234, 749946664368204571, 2151848024846342016, 6178780264862793632, 17753777112020362358, 51046191915990272562, 146861843711635625042, 422782302640197395313, 1217801785473016272860, 3509770915032834282703, 10120785157703841139493, 29199426960206832426669, 84285141338238483522146, 243408977641033645940392, 703272705354424548358166, 2032851337438649345736952, 5878622923826844749366840, 17006990922032516878568291, 49221553693571655579253018, 142512669234844557419716074, 412778027454392734660353808, 1196022865619530838795184503, 3466708434000241788498335176, 10051836242320537794909094006, 29155418772148565244180469181, 84593050834618012141071259243, 245520373392247425839507361109, 712810223556543328812416753699, 2070094145136330081404741573541, 6013571501191167332197882656260, 17474212987319706807329417621370, 50790470041475972327885352549864, 147666890448097620038211303697272, 429434835686374792898504482369180, 1249170527840811142815108070308562, 3634575434514670465004287210425262, 10577680258744298412199826138199351, 30791395012437739895028857954924396, 89653647876776180504693567021921568, 261098161658645785010810494373724021, 760561922279376449966615272384106730, 2215940056172807806616508926995683704, 6457611758340829680470487653613265217, 18822367624094358920116115309169741303, 54873535844069525687973279006257937069, 160005922296827189233377127488552375525, 466650459809795848791950708163209179809, 1361219118874827255543071462613595245228, 3971397126438082576665161887433845702185, 11588729327094956851892769369491746489957, 33822358778991300894521200975820231045302, 98729271745508524096856368430601517600504, 288244077116485267523850704197120612119580, 841677590935291353336410707208311139466354, 2458105926865241218504021014125252502527703, 7179983857695435138294008371294775747317478, 20975533535979607697117324152636124962970206, 61286936158739917083557388661179084572281984, 179096402117822814967863145889975334731802485, 523442060037000375499037362265129249122450229, 1530072327663595264163887701417733571713422989, 4473173193518870098564347636155951186810150052, 13079126141414021517427462417722610543197107898, 38247221448416237813529400786221366274848459391, 111860850335623448506962153874436737096291369618, 327199290317276234405459507880723184037385437431, 957197544501410525141546685013787239952225094345, 2800559398254571827556141817428334412418579129425, 8194850224213833044800796845711501768394691884574, 23982217018333593098022233211733652316873762599204, 70192190212060096228392308407048910277678336967556, 205465316549638435611494064326799484380284413283561, 601502781616729601895882112140318304609319102164410, 1761105203763979140388664899082962235112950247649002, 5156804594903318590283975550873518629778576701799265, 15101599835841653668927168268194546704516125232647579, 44229432100151074307521125063273180685553098592867523, 129552298847675795050449357358118317657610051583634383] ------------------------------------------------------------ Theorem Number, 4 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 4+ H H + HH HH + HH HH HH HH + H H H H + H H H H 3+ H H H H H + H H H H H H + H HH H HH HH H + H H H H H H + H HH H H H 2+ H H H H H + H H H H + H H H H + HH HH H HH + H H H H 1+ H H H + H H + H H + HH HH +H H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 0, 1, 1, 2, 4, 7, 17, 28, 71, 136, 314, 690, 1516, 3513, 7810, 18210, 41566, 96816, 225253, 526302, 1237868, 2910500, 6887650, 16305276, 38756064, 92280535, 220226311, 526745786, 1261896444, 3029231142, 7282249108, 17535688127, 42284566754, 102102666224, 246861618162, 597564894378, 1448178958330, 3513349475049, 8532386352932, 20741488351787, 50467513278017, 122904199471345, 299561099682754, 730722958010467, 1783822971293415, 4357816071997443, 10653441443876049, 26061677900539930, 63796110680527836, 156262261112186223, 382976041697017416, 939153609198351043, 2304304513013031569, 5656820456892553956, 13893953751233242705, 34142262136934643150, 83939081109418192533, 206459319170464193106, 508038199343514864180, 1250672016873251376092, 3080133791260577501243, 7588728467090629618518, 18704073663508572234062, 46117514066131639064607, 113750430271947461187020, 280667993837967130552520, 692756869766787304462021, 1710458445083557097658826, 4224582235936388420152303, 10437357575856171620576471, 25794616615519775316914144, 63766949610291040192173376, 157683676549396351382663512, 390030873792399760303508529, 965004074489371521591730703, 2388218774177698010257148654, 5911951712739059261985946604, 14638500166581143487847780711, 36255045429332653858400180515, 89813957117394009502308249256, 222546184308385481312548551340, 551562775030700382074072197240, 1367306375197681629065025991554, 3390240680398285277545953018256, 8407885936313091312653490634069, 20856073319771412823188061047699, 51744675787126356606465318497157, 128405668436033778426109561645502, 318703034548914647889158611242610, 791170013993456214403057435699268, 1964415075612468894814892129252274, 4878370472612155234001452389120424, 12116932701040914840103406220900995, 30101308972711929228278141261177182, 74791330336689714761206960987598997, 185861226069357243573147893509403128, 461951646515466162885967379222461596, 1148346597499471639578982108936799082, 2855070335913574869678189973336987858, 7099481649941220546518862737973796148, 17656359630074288057904486521132079129, 43917652294410616163779376418769011129, 109254480619809558702352483085185829764, 271831880968421367092989387260921734444, 676427651214248541726102509680980417727, 1683453064586611108958804703875924693588, 4190233950602782184393799070155479208088, 10431146868407675382944603798167254380925, 25970561544262662352744662994683527862202, 64667355386240536187327592142372437583729, 161043187542231521189006983465301188032681, 401099532321232102808436803839464255438894, 999110589144387881949008614304372449612212, 2489004432322781082081421285797971727713269, 6201369324428927113200488414578143648520908, 15452490369388131592203336475287699626365254, 38508578423801664913336783834976803096253901, 95976253896389702104425701959448197937028357, 239230534074442189579395869268168561102966253, 596369130922328451415773878120845324500679184] ------------------------------------------------------------ Theorem Number, 5 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 4+ H + HH + HH HH + H H + H H 3+ H H H H H + H H H H H H H H + H HH H HH HH H HH H + H H H H H H H H + H HH HH HH H 2+ H H H H H + H H + H H + HH HH + H H 1+ H H H + H H H H + H H H H + HH HH HH HH +H HH H -*-+-+-+-+*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 2 3 2 P(x) x + 1/2 P(x) x - 1/2 P(x) x - P(x) x + 1/2 P(x) + x - 1/2 = 0 The sequence a(n) satisfies the linear recurrence 2 (5 n - 1) a(n - 1) 12 (3 n - 4) a(n - 2) 3 (18 n - 43) a(n - 3) a(n) = -------------------- - --------------------- + ---------------------- n + 1 n + 1 n + 1 6 (4 n - 13) a(n - 4) 8 (n - 5) a(n - 5) (n - 8) a(n - 6) - --------------------- - ------------------ - ---------------- n + 1 n + 1 n + 1 2 (n - 8) a(n - 7) + ------------------ n + 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 22, a(6) = 58, a(7) = 163] Just for fun, a(1000), equals 1569440179638816213204825179767741867736890148677563482898985610171319564313\ 864241513106064507199668871460857808144866230027280855899280330330108343\ 964376764739601229306999126336437768145269665949770352080091029366147241\ 626239450697800617960865110416321438672398367696463248929514384692695854\ 039553061162487679759204472910213024181401121214747226623296450805196377\ 963355708661771331462758314230290626418749103960518187849704429160683541\ 970316865624036987748067911271784533000109507077447215625302528153700578\ 0508475112946541395674580014890884616677177814972655 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 4, 9, 22, 58, 163, 482, 1481, 4679, 15080, 49303, 162901, 542572, 1818638, 6127737, 20738632, 70460132, 240219724, 821549886, 2817759153, 9689942960, 33404259296, 115417448859, 399635092329, 1386494720546, 4819263322858, 16780350617089, 58523949083284, 204426147704576, 715106715502861, 2504962631995120, 8786072198413679, 30854679159554041, 108480567712128596, 381822459588094149, 1345319506383249577, 4744838218244317696, 16750528006134970277, 59187128162963549467, 209314623612219717012, 740846907966829742447, 2624207275138666746860, 9302372619503413139542, 32999044497207625894679, 117140747779801335748202, 416103491117183127556098, 1479006017921338996087857, 5260207581569211306552351, 18719315031739603746807484, 66653275508656199266829340, 237458867471702011456913603, 846412396437536015887569136, 3018521010243574931636226490, 10770037657110159041733202787, 38445342848673345847751041156, 137298816112181741817699261413, 490546039092829434440514634579, 1753381402278566863235105587364, 6269756576904916201595021826239, 22428329659616161544506664913579, 80261953014321472105494099452832, 287331924760569420532027245905284, 1028997854656762049436842623497063, 3686351715209678582165764430796278, 13210713503989931646200990333968054, 47358580397859113601615792674285552, 169828216714824546752354347752539828, 609194321816264129663483706479669821, 2185913060671414009773685093650030716, 7845801887266646765046610640320373930, 28168630069853294466377485341946430047, 101161372465698898367696807451260024247, 363396793902085225419890442577383080612, 1305755254753289170569816744896077809994, 4693035343000665904454265604531849992531, 16871526251226689692160737640908608762042, 60668140510243353373775750601392719457688, 218207725881612916330834787265348661776790, 785018966187949350421073517599680560553988, 2824803971248287471622571598819293665291277, 10166986815223542461014847679259290207010690, 36600726799620007587252007539593376569039998, 131788788839405760462556965566071294976315867, 474631341475222216468623374962498074758438403, 1709706255643543264977883808265504631326746764, 6159872934785924774401108001008988048100221173, 22197561138989012502330600317111651503899120677, 80005561033554726278912117864985082331197875004, 288412918780315655194716585248203636514759172571, 1039889364340623542208724311527465142560447077212, 3750038982347845301944849018534284608491699835466, 13525677491943667077942368237675919590432239875933, 48792750937381306494629501669415307653785700971362, 176044755693264500421027345017616739446963080208032, 635273761765671095071714376682003347710457703243207, 2292806241009011133512549082577410000314925217436165, 8276391346446069901869869489218344650213947429216294, 29879997951875278902958213670614235708208089834727764, 107890868239396980098252484639288324915136828983633993, 389629765223143933989360957367960093279128998498057976, 1407283679874632781361356939941399184380859962275099410, 5083608162004769025633188189423124553852571786568359783, 18366323053066343268129858595654792291026954054333769000, 66363758943872769315915723130993244688221677698142751215, 239826543315140683303346327130111826136995324788464922431, 866802124109580949454379992537392947572943390803636365076, 3133272009367439375147712199189479901125693707980435665349, 11327410444614319108002424739708760323210663968416874351377, 40955912075398802624392358602542960220920560717284914334164, 148099993507532772691231460649766905186319058932505200705536, 535605491976758388111235864664934184877500145953659809668445, 1937249886839612745959773019192633464828598057869001790760542, 7007708483903059849415710518461805059444074410016437587102694, 25352180184160018672246957513930395819339587115205326375569348, 91728156530723000704292372784976674500645633875754553680237512, 331922941742160864694423036876572529847067586600118159859609831, 1201208329117832514810936646237006071682028812642086733207274032, 4347554986991815508982798387814079361089549590636065032813271566, 15736812195745619781515849778527273512754065684607846892818448421] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 6 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 6+ H + HHHH + H H 5+ HH HH + HH H + H HH + HH H 4+ H HH HH + H HH HH H + HH HH H HH 3+ H H H H + HH HH HH HH + HH HH H HH 2+ HH HH HH + H H + HH HH + H H 1+ HH HH + H H +HH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 8 5 2 2 3 3 2 3 3 - 5/2 + x P(x) - 3/2 x P(x) - 3 x P(x) - 9 x P(x) + 4 x P(x) 3 4 4 2 4 3 4 4 4 5 - 2 x P(x) + 4 x P(x) - 1/2 x P(x) - 3/2 x P(x) + 1/2 x P(x) 5 2 5 3 5 4 5 5 6 3 + 5 x P(x) - x P(x) + 4 x P(x) - 3 x P(x) + 6 x P(x) 6 4 6 5 7 3 7 4 7 5 + 3/2 x P(x) + 1/2 x P(x) + 5/2 x P(x) + 3/2 x P(x) + 3 x P(x) 8 4 9 4 2 2 3 + 2 x P(x) + 1/2 x P(x) + 2 P(x) x + 11/2 P(x) x - 5 P(x) x 2 + 5/2 P(x) + 3 x + 2 P(x) x = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 2, 4, 7, 18, 35, 90, 202, 501, 1216, 2993, 7493, 18627, 47139, 118762, 302281, 769869, 1970247, 5057206, 13014701, 33599823, 86920003, 225451914, 585890907, 1525801210, 3980713289, 10403550655, 27234028165, 71399673071, 187460654503, 492837890628, 1297342244188, 3419204031076, 9021744549856, 23829997037054, 63008851412038, 166763695885614, 441776612004418, 1171349758183650, 3108386242509484, 8255274912910064, 21941215308097938, 58359017873451259, 155331619404968609, 413717265114214435, 1102623870446550621, 2940491105593624366, 7846401760564983382, 20949296634160434487, 55963800829694488395, 149580486728073778811, 400003953393042242795, 1070205785105389028136, 2864682252220972374962, 7671576975700775137877, 20553467386480081157602, 55089824065539203707118, 147719353689793261973279, 396257344541672796127457, 1063372994844488566047424, 2854677343209351350584944, 7666312103732451258486599, 20595352339384150064115255, 55347834114602340974734266, 148790883878560593421561246, 400121704873682980345154795, 1076326360773822647648613405, 2896196856780711898827925342, 7795441725746835780869376938, 20988354882978856935718457353, 56524625998126673014874403008, 152270359096479512231875539579, 410306406216535587023824532677, 1105893925285907170245373212952, 2981453286819199210439065831492, 8039871936698596312229702800727, 21685735957295117700128115548291, 58506017822744504108352092971326, 157879511073745240377765532557882, 426135266384698695177712831377437, 1150438345891448190128523495922890, 3106498623860955312961055187904269, 8390131786783825785192588318312800, 22664916811277891824549905378561753, 61238593364086673154092918015370209, 165493172612029382495910450311403037, 447318528469566591049063626627306502, 1209299346032806575606452752861506213, 3269859756802121515159416736138136200, 8843030482777774397347826772478909325, 23919283650571926346637614896655285475, 64709595129457615725064704490800216575, 175089913400017658283987300414288427817, 473831596876944210698806379069046733297, 1282495678499823145883245257855938150750, 3471805668973018195643893642027821791113, 9399855006614121272443764339446004986870, 25453753553931578446889329561165540664260, 68936014627805493863716927015608767068118, 186725197194408991762797509347760929896561, 505848999434728063916817112693785860389882, 1370562701015070081453457068505225225542625, 3713948101838275298584088927542201265545345, 10065388852858434986651049424144019693666079, 27282365055540751723518538311132898750415602, 73958681773023322004758792079169910406853440, 200516899330248415354215672243840735845455180, 543708952258816356364727603437832245810450215, 1474465825051508602679743938040022549798179887, 3999030591201764405878888402797878612406554403, 10847399096088978416039172049003516994553632924, 29427034724081552447464510225799230720553840658, 79839261391245733294128290770076088589775484266, 216638082771904861252324048714746829376433508277, 587896074439560128406497102330327628530789886954, 1595559415221290296984324093684761771726097662400, 4330831491891702571909392045939966272819588885308, 11756409776272468226065588148545618437781689918704] ------------------------------------------------------------ Theorem Number, 7 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 3+ H H + H H H H + HH HH HH HH 2.5+ H H H H + H H H H + H H H H + H H H H 2+ H H H H H + H H HH H H + H H H H H H 1.5+ HH HH HH HH HH HH + H H H H H H + H H H H H H 1+ H H H H H H + H H H H H H + H H H H H H + H H H H H H 0.5+ H H H H H H + H H H H H H +H HH HH H -*-+-+-+-++-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-+-*+-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 5 2 2 2 3 5 x P(x) - 5/2 + 2 P(x) x + 11/2 P(x) x - 5 P(x) x + 5/2 P(x) + 3 x 5 3 5 4 5 5 6 3 6 4 - x P(x) + 4 x P(x) - 3 x P(x) + 6 x P(x) + 3/2 x P(x) 6 5 7 3 7 4 7 5 8 4 + 1/2 x P(x) + 5/2 x P(x) + 3/2 x P(x) + 3 x P(x) + 2 x P(x) 9 4 2 2 3 3 2 3 3 + 1/2 x P(x) - 3/2 x P(x) - 3 x P(x) - 9 x P(x) + 4 x P(x) 3 4 4 2 8 5 4 3 4 4 - 2 x P(x) + 4 x P(x) + x P(x) - 1/2 x P(x) - 3/2 x P(x) 4 5 2 + 1/2 x P(x) + 2 P(x) x = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 2, 4, 7, 18, 35, 90, 202, 501, 1216, 2993, 7493, 18627, 47139, 118762, 302281, 769869, 1970247, 5057206, 13014701, 33599823, 86920003, 225451914, 585890907, 1525801210, 3980713289, 10403550655, 27234028165, 71399673071, 187460654503, 492837890628, 1297342244188, 3419204031076, 9021744549856, 23829997037054, 63008851412038, 166763695885614, 441776612004418, 1171349758183650, 3108386242509484, 8255274912910064, 21941215308097938, 58359017873451259, 155331619404968609, 413717265114214435, 1102623870446550621, 2940491105593624366, 7846401760564983382, 20949296634160434487, 55963800829694488395, 149580486728073778811, 400003953393042242795, 1070205785105389028136, 2864682252220972374962, 7671576975700775137877, 20553467386480081157602, 55089824065539203707118, 147719353689793261973279, 396257344541672796127457, 1063372994844488566047424, 2854677343209351350584944, 7666312103732451258486599, 20595352339384150064115255, 55347834114602340974734266, 148790883878560593421561246, 400121704873682980345154795, 1076326360773822647648613405, 2896196856780711898827925342, 7795441725746835780869376938, 20988354882978856935718457353, 56524625998126673014874403008, 152270359096479512231875539579, 410306406216535587023824532677, 1105893925285907170245373212952, 2981453286819199210439065831492, 8039871936698596312229702800727, 21685735957295117700128115548291, 58506017822744504108352092971326, 157879511073745240377765532557882, 426135266384698695177712831377437, 1150438345891448190128523495922890, 3106498623860955312961055187904269, 8390131786783825785192588318312800, 22664916811277891824549905378561753, 61238593364086673154092918015370209, 165493172612029382495910450311403037, 447318528469566591049063626627306502, 1209299346032806575606452752861506213, 3269859756802121515159416736138136200, 8843030482777774397347826772478909325, 23919283650571926346637614896655285475, 64709595129457615725064704490800216575, 175089913400017658283987300414288427817, 473831596876944210698806379069046733297, 1282495678499823145883245257855938150750, 3471805668973018195643893642027821791113, 9399855006614121272443764339446004986870, 25453753553931578446889329561165540664260, 68936014627805493863716927015608767068118, 186725197194408991762797509347760929896561, 505848999434728063916817112693785860389882, 1370562701015070081453457068505225225542625, 3713948101838275298584088927542201265545345, 10065388852858434986651049424144019693666079, 27282365055540751723518538311132898750415602, 73958681773023322004758792079169910406853440, 200516899330248415354215672243840735845455180, 543708952258816356364727603437832245810450215, 1474465825051508602679743938040022549798179887, 3999030591201764405878888402797878612406554403, 10847399096088978416039172049003516994553632924, 29427034724081552447464510225799230720553840658, 79839261391245733294128290770076088589775484266, 216638082771904861252324048714746829376433508277, 587896074439560128406497102330327628530789886954, 1595559415221290296984324093684761771726097662400, 4330831491891702571909392045939966272819588885308, 11756409776272468226065588148545618437781689918704] ------------------------------------------------------------ Theorem Number, 8 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 4+ H + HH + HH HH + H H + H H 3+ H H + H H + H HH + H H + H H 2+ H H H H + H H HH HH + H H H H H H + HH H HH HH H HH + H H H H H H 1+ H H H H H H + H H H H H H + H H H H H H + HH HH HH HH HH HH +H HH HH H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+*-+-+-+-+-++-+-+-+-*+-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 0, 1, 1, 2, 3, 5, 11, 15, 38, 61, 138, 276, 567, 1256, 2588, 5825, 12441, 27769, 61163, 135901, 304348, 678577, 1529746, 3435043, 7765972, 17554933, 39793371, 90392705, 205546094, 468535526, 1068896307, 2443245066, 5590619341, 12810238051, 29388429459, 67493982196, 155187928362, 357161086338, 822845991392, 1897408952432, 4379199705556, 10115645813174, 23385163872791, 54103459823270, 125263966987253, 290226068594349, 672881292231173, 1561072590465759, 3623913478563441, 8417675667594288, 19563954277911916, 45494725468450088, 105851537003075703, 246408697595848338, 573891774454831629, 1337246062674936308, 3117402550104832018, 7270560516707012898, 16964060433670112149, 39597936560124193616, 92467733095841432991, 216011682820808944500, 504810413421752479405, 1180153077080363642209, 2759958270879520205010, 6456783053872643766578, 15110365459321992480201, 35373220787213323107990, 82834463654151847743320, 194035177266069993799436, 454652010944657215126729, 1065622642963625647828807, 2498331298922120689547297, 5858893541234603024139946, 13743489857111387389849681, 32247144527345948901070818, 75682490072301314155157416, 177666961760810128773913737, 417178926265176487457448928, 979805516777104962423787666, 2301742490838204806171623662, 5408421370373576706810699831, 12710976526865678154964747807, 29879937692999311091197200985, 70253938120404923695306950771, 165215120563788536576270940355, 388610945031906829659825155334, 914248883617127621462016752067, 2151276057455447689520905927096, 5063004647367725745116901405971, 11917886018267068752038809810748, 28058674268801748982895765107189, 66070932926449599235716320898338, 155606419045569412977045246840645, 366536147743584338539268940355824, 863528848474247804607001436530931, 2034727137596036439768879945230160, 4795163109183215876199258380932715, 11302307220615208339545758856083641, 26643791435704407447631808354692106, 62818686599125290373632766542075456, 148130449755646899322851460964091368, 349350430872584064624934809026985708, 824021420950189966747081892170751264, 1943904182569335987520926263804491886, 4586371508590509990516423496392689512, 10822324512044493288024706300393219481, 25540404377965199768980621384175338117, 60282306474625137804659688898428046816, 142300305924066269196762188407168118720, 335950059443170876797182002215175070625, 793223524628292688414345859569335876865, 1873128224967797362122067691384986172197, 4423740039619320325150697241445332170175, 10448669357067175456991155505494243211311, 24682027250913231341909679251494161820940, 58310705570106538205882868530193385946850, 137772516030738838285763552727315332342487, 325553915723842496947935257306844956484684, 769358105283462897130509465717966854802609] ------------------------------------------------------------ Theorem Number, 9 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 4+ H H + HH HH + HH HH HH HH + H H H H + H H H H 3+ H H H H + H H H H + H HH H H + H H H H + H HH H 2+ H H H H H + HH H H HH + H H H H H H + HH H HH HH H HH + H H H H H H 1+ H H H H + H H + H H + HH HH +H H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 3 2 2 3 2 2 2 P(x) x + 2 P(x) x + P(x) x - P(x) x - 2 P(x) x - 2 P(x) x - x + P(x) + 3 x - 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (5 n - 1) a(n - 1) 7 (5 n - 7) a(n - 2) (46 n - 125) a(n - 3) a(n) = -------------------- - -------------------- + --------------------- n + 1 n + 1 n + 1 2 (2 n - 19) a(n - 4) (22 n - 89) a(n - 5) (5 n - 28) a(n - 6) - --------------------- - -------------------- - ------------------- n + 1 n + 1 n + 1 2 (n - 8) a(n - 7) (n - 8) a(n - 8) + ------------------ + ---------------- n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 2, a(4) = 6, a(5) = 18, a(6) = 56, a(7) = 177, a(8) = 566] Just for fun, a(1000), equals 1878850820281290457851889922206929731717063713294792019364047791715507761067\ 704536873836198816485673606430439419333661066020461347285953785144875330\ 203823437600821388311552211744486254345104571823638941331430191436265097\ 922865563340872793666552690783147776167197676617665817914160088377598978\ 169430328107094845347080440311527887027786924148044871315663085337573682\ 047447739418843439701019795827035257839782859643170840264001388127084042\ 080391731789671238063680719289226760746355282096197470159025568126408372\ 5160253035018926523854193159581220905462651318670212 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 2, 6, 18, 56, 177, 566, 1826, 5935, 19418, 63914, 211541, 703766, 2352567, 7899361, 26634447, 90151123, 306236153, 1043733867, 3568363268, 12234885057, 42062506758, 144968828840, 500800359049, 1733794082826, 6014662406467, 20904942867133, 72787795989839, 253858784384819, 886759784853186, 3102127555080589, 10867161829437803, 38118985976682878, 133876343175824073, 470732996492167981, 1657016923367221314, 5838966048704429151, 20595800590422414501, 72716639380242867066, 256969446637200766711, 908873193397034708911, 3217229292636277446499, 11397289847895669247731, 40406108246628415557556, 143352165126538584321687, 508932434057286040260624, 1808016068928083405818596, 6427160117639986166274453, 22861236172809236872070284, 81364277908435451683629393, 289742108444069753162583993, 1032343156290706950982539309, 3680124638393986554988750829, 13125588069701689239420790774, 46836568312250392798114967959, 167206855109037524957847905793, 597198685398791393518926891298, 2133893549999528306349778006595, 7627979557745630481343293555999, 27278669171297118410352986379694, 97590611595429016318530035941061, 349267911094081627368452105261436, 1250460438919215479428222378150428, 4478544794828667069516976045364444, 16045560102147124100331635941254814, 57506818389002165579394059934223516, 206170252799257774808242518213670570, 739385212374132751354654107336154821, 2652465094586409027964268413576671286, 9518291167470769552782431387509809891, 34166073724847949069813395249901973255, 122674550943158977127351058654680920554, 440589224581853332009012340234126846481, 1582814667055984360875411598864246262286, 5687743392187909617074467652702313743596, 20443757016657161478276553336113782526458, 73500345433292206563081849644505380730116, 264315892744367784187723538687687766848104, 950735645346751292697932870088864151426732, 3420553222310259140364013842485348613884869, 12309220962694237091195665036680264255624606, 44305748316871655987977656096920673280152699, 159508052836603294355203927717406152654165875, 574375617786488940241894955362088463394291118, 2068702861102680006879630896782091561252618069, 7452241763490687198446497133404250371346254901, 26851001657501217357301009478684267711643806202, 96764683834069823187299433321534565118033500955, 348782166038847066368792225639986869800074230675, 1257392542691756187744175025632566174249110694375, 4533827505088957659384542672384473541669101300467, 16350647080117647980565930571008863631036153500310, 58976517618818225959261169008465669276662629520583, 212762936136255987330856610266726326323753090806784, 767686640270472294850634076188688190740700353961294, 2770394934154869520401245091857506012699163609679123, 9999255373008258970497895583967224865723124567663504, 36096120939154526560615510951969502151925607721301307, 130322369586963734384064974785966082668294989324444583, 470588888857431969121601448613285110937370926900980463, 1699524296730172586009902897218015302365638808405388967, 6138678284573280604051881552589641900759500405729919360, 22175987594933539010977148219205842287206450101062277121, 80121766312180441405662183930684986581340170197329686817, 289518545646689566493816396948701152210438759887901070756, 1046307895084859157240982316105256586301170431199838348543, 3781802096964685357214733243273908330792586548660740703039, 13670778514893670229377449143982873768845620080977322775300, 49424450312922190224357140654365095442983059491066551885049, 178707848497473218120538473897394049399289676561045798582606, 646245652269561469194207031814553568746424440701807557307634, 2337238055922692126246253827389266281965736323926343084621526, 8453930474338780079182879166669624262464775382832927732132296, 30581862220954151258027548637735300507346725384764649750250078, 110641451078650045955036434199256108139124685797706128161731268, 400331393058969106453938708342866697631372415828785958572847421, 1448666682830099044285004423368850515389763156897128458795480480, 5242803087475317674384872650420634946136390694974934442562531883, 18975975079542723156605002727109235198237511050182714171112449535] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 10 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 4+ H + HH + HH HH + H H + H H 3+ H H + H H + H HH + H H + H H 2+ H H H H + H H HH HH + H H H H H H + HH H HH HH H HH + H H H H H H 1+ H H H H H H + H H H H H H + H H H H H H + HH HH HH HH HH HH +H HH HH H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+*-+-+-+-+-++-+-+-+-*+-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 3 3 4 3 2 5 6 11 + 12 P(x) x + 9 P(x) x + 20 P(x) - 71 P(x) + 93 P(x) + P(x) x 5 5 4 6 5 4 5 3 4 4 + 8 P(x) x + P(x) x + 23 P(x) x + 26 P(x) x - 32 P(x) x 3 5 5 2 4 3 3 4 5 - 5 P(x) x + P(x) x - 95 P(x) x - 8 P(x) x - 15 P(x) x 4 2 3 3 2 4 4 3 2 - 68 P(x) x + 75 P(x) x + 13 P(x) x + 39 P(x) x + 168 P(x) x 2 2 2 2 3 + 13 P(x) x - 123 P(x) x + 9 x - 18 P(x) x + 90 P(x) x - 53 P(x) 2 - 24 x - 99 P(x) x = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 3, 6, 14, 32, 74, 176, 416, 1007, 2438, 5982, 14754, 36658, 91658, 230303, 581866, 1475973, 3760300, 9613446, 24661635, 63456896, 163736820, 423583172, 1098375860, 2854450108, 7433123697, 19392947545, 50685026701, 132687658311, 347896900795, 913478011405, 2401796680875, 6323100672063, 16666667951907, 43980809849955, 116184216396912, 307238799747556, 813256413628877, 2154669241190123, 5713681762837795, 15164072864239230, 40277575113095549, 107063842984255112, 284799897320100046, 758124790715345244, 2019448006677898569, 5382744803880305822, 14356308967685766625, 38312378611898341438, 102301685243083709516, 273315599535432648029, 730592391765233548095, 1953919132179709977243, 5228183401015491595863, 13995883691893088592132, 37484178976655606230665, 100435465648654728984427, 269222403719113134917681, 721961783826466802795768, 1936824793528448473754646, 5197973462402844549364901, 13955330178061705089989116, 37480337731729934508686631, 100697667349190070601569213, 270634581505989183305003853, 727596775761895795113768467, 1956760450205254149065698121, 5264049693458769670325701528, 14165564764226055124638301171, 38130784035915368801506173601, 102669627907736407670364694179, 276521739144393817189774943310, 744962432776667131555909387754, 2007493545529360764174326580619, 5411101087804094964898671950676, 14589014952693323252720739744556, 39343442837101472028227981780726, 106126089993140106002537665771758, 286333932123214430359384707110814, 772719470970545078485487559148686, 2085772333108177308500711239980365, 5631261120745805979512312498803534, 15206733539338397629038037981056941, 41072920040187694210155053359600825, 110959000921484190856561174939664856, 299816010675872017453231347498816037, 810271397495250517935220279356143047, 2190220011297991641326483111842145298, 5921404471190224992769591015347398467, 16011784092013118113408873472504141487, 43304303278639086997956991199444050128, 117137807517238290776064961631775554760, 316910227852894917223469890232304642000, 857525460185929221289420734474369428124, 2320747624555027299322521428160710351868, 6281704403505757580063791183241474934218, 17005694679897486406338551186550244282165, 46044441605838280359064702656322767282935, 124688008053392280827168816152329423186037, 337703480839361357844902664613371663557652, 914762869994001669405165708513505180106779, 2478234872314934326039560810799821324881033, 6714847914751914141629919556810823042600847, 18196528809448884148318203696659909074612904, 49317206851895284680136331928249056473591080, 133679520909711236029735153922531490837724584, 362398788713184598425551896297021524161537216, 982568943474227737214826379135232071458473110, 2664359264403152216154720636456483638398078604, 7225618660639979273322644483750331194526298590, 19597869428439712849640913760266743246150125610, 53161025010008731302083644016510644819086553460, 144220704906525364953350514884704490183075246238, 391300861370208602262227972693239571420566530185, 1061798429533255667803730098065483672069611530819, 2881513257753054741060285685894873984787794982586, 7820700216036834767027892003479559957295045883453, 21228355561436473541377202988437736969435775445127] ------------------------------------------------------------ Theorem Number, 11 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 4+ H + HH + HH HH + H H + H H 3+ H H H H + H H H H H H + H HH H HH HH H + H H H H H H + H H H HH H 2+ H H H H H + H H H H + H H H H + HH H HH HH + H H H H 1+ H H H H + H H H H + H H H H + HH HH HH HH +H HH H -*-+-+-+-++-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 3 5 6 5 5 4 6 5 4 5 3 11 + 12 P(x) x + P(x) x + 8 P(x) x + P(x) x + 23 P(x) x + 26 P(x) x 4 4 3 5 5 2 4 3 3 4 - 32 P(x) x - 5 P(x) x + P(x) x - 95 P(x) x - 8 P(x) x 5 4 2 3 3 2 4 4 - 15 P(x) x - 68 P(x) x + 75 P(x) x + 13 P(x) x + 39 P(x) x 3 2 3 4 3 2 2 + 168 P(x) x + 9 P(x) x + 20 P(x) - 71 P(x) + 93 P(x) + 13 P(x) x 2 2 2 3 - 123 P(x) x + 9 x - 18 P(x) x + 90 P(x) x - 53 P(x) - 24 x 2 - 99 P(x) x = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 3, 6, 14, 32, 74, 176, 416, 1007, 2438, 5982, 14754, 36658, 91658, 230303, 581866, 1475973, 3760300, 9613446, 24661635, 63456896, 163736820, 423583172, 1098375860, 2854450108, 7433123697, 19392947545, 50685026701, 132687658311, 347896900795, 913478011405, 2401796680875, 6323100672063, 16666667951907, 43980809849955, 116184216396912, 307238799747556, 813256413628877, 2154669241190123, 5713681762837795, 15164072864239230, 40277575113095549, 107063842984255112, 284799897320100046, 758124790715345244, 2019448006677898569, 5382744803880305822, 14356308967685766625, 38312378611898341438, 102301685243083709516, 273315599535432648029, 730592391765233548095, 1953919132179709977243, 5228183401015491595863, 13995883691893088592132, 37484178976655606230665, 100435465648654728984427, 269222403719113134917681, 721961783826466802795768, 1936824793528448473754646, 5197973462402844549364901, 13955330178061705089989116, 37480337731729934508686631, 100697667349190070601569213, 270634581505989183305003853, 727596775761895795113768467, 1956760450205254149065698121, 5264049693458769670325701528, 14165564764226055124638301171, 38130784035915368801506173601, 102669627907736407670364694179, 276521739144393817189774943310, 744962432776667131555909387754, 2007493545529360764174326580619, 5411101087804094964898671950676, 14589014952693323252720739744556, 39343442837101472028227981780726, 106126089993140106002537665771758, 286333932123214430359384707110814, 772719470970545078485487559148686, 2085772333108177308500711239980365, 5631261120745805979512312498803534, 15206733539338397629038037981056941, 41072920040187694210155053359600825, 110959000921484190856561174939664856, 299816010675872017453231347498816037, 810271397495250517935220279356143047, 2190220011297991641326483111842145298, 5921404471190224992769591015347398467, 16011784092013118113408873472504141487, 43304303278639086997956991199444050128, 117137807517238290776064961631775554760, 316910227852894917223469890232304642000, 857525460185929221289420734474369428124, 2320747624555027299322521428160710351868, 6281704403505757580063791183241474934218, 17005694679897486406338551186550244282165, 46044441605838280359064702656322767282935, 124688008053392280827168816152329423186037, 337703480839361357844902664613371663557652, 914762869994001669405165708513505180106779, 2478234872314934326039560810799821324881033, 6714847914751914141629919556810823042600847, 18196528809448884148318203696659909074612904, 49317206851895284680136331928249056473591080, 133679520909711236029735153922531490837724584, 362398788713184598425551896297021524161537216, 982568943474227737214826379135232071458473110, 2664359264403152216154720636456483638398078604, 7225618660639979273322644483750331194526298590, 19597869428439712849640913760266743246150125610, 53161025010008731302083644016510644819086553460, 144220704906525364953350514884704490183075246238, 391300861370208602262227972693239571420566530185, 1061798429533255667803730098065483672069611530819, 2881513257753054741060285685894873984787794982586, 7820700216036834767027892003479559957295045883453, 21228355561436473541377202988437736969435775445127] ------------------------------------------------------------ Theorem Number, 12 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 3+ H H + H H H H + HH HH HH HH 2.5+ H H H H + H H H H + H H H H + H H H H 2+ H H H H H + H H HH H H + H H H H H H 1.5+ HH HH HH HH HH HH + H H H H H H + H H H H H H 1+ H H H H H H + H H H H H H + H H H H H H + H H H H H H 0.5+ H H H H H H + H H H H H H +H HH HH H -*-+-+-+-++-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-+-*+-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 0, 1, 1, 2, 4, 7, 17, 28, 71, 127, 296, 600, 1285, 2826, 5902, 13268, 28214, 63025, 137671, 305382, 679587, 1508783, 3387824, 7569178, 17062501, 38402915, 86810675, 196556898, 445744034, 1013593988, 2306701471, 5262155628, 12015954888, 27485622186, 62948488575, 144346776027, 331422199381, 761728587608, 1752757335246, 4036932290669, 9307123849416, 21476647478691, 49601498496070, 114652758049265, 265223164408389, 614001603704128, 1422446807093654, 3297643300825569, 7649908370446817, 17757568672149800, 41245282524074469, 95855604696448414, 222897076202031185, 518590673528028017, 1207175826671974896, 2811468121206061216, 6550961686783418358, 15271398095563980951, 35616181361681573163, 83100608719214675745, 193973750362865588251, 452957797142659657115, 1058139181109871989104, 2472821415946868465696, 5780993040651118084043, 13519696992843685337394, 31628719300601011434155, 74018776519578152517078, 173278058318377800206694, 405772412686378699563652, 950505910404492645174389, 2227187252922455271162064, 5220170087465189743310413, 12238695782010760990381299, 28701518977927468054757052, 67327223673832655580195286, 157975436181378525174104527, 370764823064482245297240205, 870391754249481684950257529, 2043786791047093879898015403, 4800189408204203818273121753, 11276663340147064888087863961, 26497194277984863646087355292, 62275018731726655589147246126, 146392995114410375504640772271, 344204868238636207854229515030, 809472145848148360753896392384, 1904026446791514989670058150133, 4479486757943566854799011280834, 10540612889419661658846273918154, 24807555540786248839765632083122, 58395693192043308165586011403064, 137484802576182723980662192275450, 323745655539692068434778789241997, 762477413558659746028464482603239, 1796065820064925216894103640739463, 4231440545040176907186238604677408, 9970650979692406565872384086833947, 23497770169510248149312996334683148, 55385526524131085812083627002768463, 130566300597282446771814650938736772, 307843364188749097272322443013217737, 725923960876988064982540307115761745, 1712039939537390048671213554194676962, 4038284387105848567641748528089979040, 9526623707185420495338382930028627504, 22477039794088031639238704166090410956, 53039097874170420830555307395661046642, 125172522198192649208944060894138529360, 295445048871271706050426487238916890214, 697426225184916833930704037589456340688, 1646541605169017665604394012926526292374, 3887756713713356757103087871598871561489, 9180714258990688088267905286709948076465, 21682232068512542553302659855214345353476, 51213064546502304536276086549639578168581, 120977875035846186055108666714042238133095, 285810859421935098551339271922536719468957, 675302382890594525938263316591139342537555, 1595746266754308329334420594393958203564885] ------------------------------------------------------------ Theorem Number, 13 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 3+ H H H H + H H H H H H H H + HH HH HH HH HH HH HH HH 2.5+ H H H H H H H H + H H H H H H H H + H H H H H H H H + H HH HH HH H 2+ H H H H H H + H H HH + H H H H 1.5+ HH HH HH HH + H H H H + H H H H 1+ H H H H + H H H H + H H H H + H H H H 0.5+ H H H H + H H H H +H HH H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-*+-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 3 2 2 3 2 2 P(x) x + P(x) x + P(x) x - P(x) x - 2 P(x) x - P(x) x + P(x) + 2 x - 1 = 0 The sequence a(n) satisfies the linear recurrence (7 n - 2) a(n - 1) 2 (7 n - 11) a(n - 2) (n - 8) a(n - 3) a(n) = ------------------ - --------------------- + ---------------- n + 1 n + 1 n + 1 (17 n - 55) a(n - 4) 3 a(n - 5) (11 n - 64) a(n - 6) + -------------------- - ---------- - -------------------- n + 1 n + 1 n + 1 3 (n - 6) a(n - 7) (n - 8) a(n - 8) - ------------------ + ---------------- n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 3, a(5) = 7, a(6) = 19, a(7) = 52, a(8) = 146] Just for fun, a(1000), equals 3513842649600043764124719344871886089679570494391868561956868444487193769115\ 552697638066955695132023257838484151368498435841497023697583409413650748\ 658796737298732284557689342841676257578566846748316344909665656605561223\ 685570143602345364149889676056136830804297487655625663862189681580521229\ 153582028123159506961333714004204636695186967273049746888036744542224947\ 359113122274943805438688614239342620007928468129189775281531755360774797\ 92855549747135916156276107952383562222342131081051453680338324678287015 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 3, 7, 19, 52, 146, 415, 1192, 3452, 10068, 29548, 87207, 258694, 770972, 2307473, 6933099, 20906124, 63248652, 191932770, 584072132, 1782019774, 5450109014, 16705916422, 51314569388, 157926653170, 486921793636, 1503840243173, 4651971276462, 14411967860113, 44711799675412, 138898795449650, 432036053674687, 1345417199997534, 4194517801106745, 13090911460358360, 40897530960105419, 127891578218231227, 400298809103093239, 1254022689570550290, 3931766960776346287, 12337157937755707362, 38741125484034226744, 121743237466378095653, 382842031816783821293, 1204714129454426334939, 3793379148953853571454, 11951854269686029135421, 37679114593301638163996, 118853677562617266997172, 375112743874435318310263, 1184512119666690115767103, 3742289698905585492533955, 11828989798444014050906948, 37407857115736587108027407, 118352073131097608117975698, 374610612776640703484987096, 1186230504130037854317509776, 3757827584654410093073372637, 11909063278981496611293784562, 37755989694126119172260617752, 119744723909120678012125740898, 379913036999335288838488059805, 1205770139903937474082586743832, 3828184132040176871682918922158, 12158072485398800874005052720299, 38625675799635515996484522738473, 122750401863646560173286635901410, 390212706298567120652792443201876, 1240817433577317845433180420180374, 3946743063774783673536905543007124, 12557146025110591724267322623026017, 39963261651907861710890216796111000, 127217160084213527552601119039100771, 405081371466777779328797827673192972, 1290172510125706916362287439554685123, 4110167059461745149548927328092086049, 13097086216517638598802344606532615043, 41743692519948763472248333781180046029, 133077777524566317841305497204737489030, 424342314473189298128801218502325615682, 1353383810458184004975994130798354101070, 4317349809826676179141457216509889054046, 13775361117484690122051145729762851624175, 43961872312169009182330358291005450756408, 140324923276131371399298008859782128553093, 447998922669602150806984605007112823996190, 1430542587578816137150406906679398872451442, 4568824565339785883198129450119456591729395, 14594401990460801977587588330398024793362444, 46627762519512536758056832112930732582410919, 148997049605368684528399694689329949150264732, 476194095525192109385241523672776175632999343, 1522166153099562214678208772959208089853901470, 4866428560646460047043716273844738247861322653, 15560639666217389234779218172899373960395696795, 49763618317251816582606565406067549948421780253, 159170476354715109493740823738063699026770346687, 509187616739735180546172642096998413399610166283, 1629133338283519884683598910042860739796437934101, 5213119443791568947809612126356010091355743774534, 16683984150256439414160090472334370774241380690169, 53402519319121023402078627795297115791953891269534, 170955263278083428091428408851471223954444336494791, 547344628357779813128880281423966309161939384721931, 1752652550962053385975440167700013487496760890982159, 5612887579452715051095927484485936518735211132381069, 17977586737684129500995872052592074391801497938429440, 57587734340527293722811051012256908155814432383739924, 184493549188453706412228659640484194345648093085907586, 591131415351812451246771248143921970712899751495093754, 1894251540293727419939440008993363293567441549631458503, 6070732942709353487243080234182218937512769113076568916, 19457794712235942778773518956530152283561920382006635225, 62372661588365274222355229622887884928875698918010840198, 199959614143389928224140722005488215429658138213539608730, 641116360939285092801562467353432174345434635659862103155, 2055782713220529884892262908870595215633749631565998798091, 6592688892644573498973647594986192635704500786408651908829] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 14 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 5+ H + HH H + H H + HH HH 4+ H H + H H + HH HH + H H 3+ H H H + HH HH H HH + H H HH H + HH HHH HH 2+ H H H H + HHH H H + HH H HH HH + H HH H H 1+ H H H H + HH H HH HH + H HH H H +HH HHH HH -*-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 3 2 2 3 5 8 4 9 5 7 -5 + 6 P(x) - 17 P(x) - 16 P(x) x + P(x) x + P(x) x - 3 P(x) x 4 8 5 6 5 5 4 6 3 7 5 4 - 2 P(x) x - P(x) x + 4 P(x) x + 7 P(x) x + 5 P(x) x + P(x) x 4 5 3 6 5 3 4 4 3 5 - 7 P(x) x - 8 P(x) x - 2 P(x) x - 9 P(x) x - 7 P(x) x 4 3 3 4 2 5 4 2 3 3 + 10 P(x) x + 23 P(x) x + 10 P(x) x + 4 P(x) x - 3 P(x) x 2 4 4 3 2 3 2 - 15 P(x) x - 4 P(x) x - 24 P(x) x + 5 P(x) x - 15 P(x) x 5 9 2 2 3 + P(x) x + 35 P(x) x + 11 P(x) x - 15 P(x) x + 16 P(x) + 6 x 2 + 8 P(x) x = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 2, 4, 7, 15, 30, 63, 136, 291, 645, 1420, 3185, 7165, 16238, 37038, 84782, 195196, 450727, 1045167, 2430671, 5670139, 13263087, 31098781, 73092513, 172145280, 406249178, 960450803, 2274602523, 5395484160, 12817567364, 30492637149, 72637127727, 173247513035, 413701984479, 988994885132, 2366792869224, 5669735144344, 13595023546331, 32628072258815, 78375187587135, 188418653355513, 453326570459234, 1091503694799630, 2629976331104194, 6341292586015729, 15299971012288316, 36938445659544857, 89234094741029071, 215693418226536816, 521659452550094967, 1262327943994496322, 3056212551359225984, 7403088603946914005, 17941246099585996437, 43500591329892557533, 105519721792338236053, 256071594843802419560, 621687550751125391323, 1509940880088451980810, 3668757665990303826763, 8917517940922081215675, 21683514123798360028370, 52743763776568122370124, 128340472029002689006662, 312394019268377467669670, 760648566597364233722061, 1852693331009565612588791, 4513955077147547432616856, 11001232965101124858973173, 26819600766697597867586268, 65401333965565227442456449, 159529471964336963644236123, 389235172618476302511361417, 949941777607356517857322817, 2318957073055254599912751038, 5662346029467444285609581245, 13829464029052914285869788090, 33784454629083715637652259466, 82552184015320681881562547554, 201761304352715054544550289607, 493222059012912522533925316810, 1205980116400173507330967924380, 2949365924229789138447422423344, 7214494642973432030321274566236, 17651023041090541485505254377530, 43193519312094325134143793214277, 105718292780304781173467600123146, 258799060372649558547954769265749, 633657348299883290468532742441247, 1551757178073305319410124682529074, 3800746405461556762195232581073262, 9310826970402275535931918090551620, 22812889153916080536243217030713277, 55904077454928787406279531848742124, 137017606048547545486637138132218946, 335874893050480395774074163735758668, 823465873165199871166656573701396648, 2019199510953637344112622569246011359, 4951959974828158540377215622798064661, 12146132863532891889383647642449057623, 29796188694378018750280678420360125375, 73104482113619636938355187813128117771, 179385254736419524471227497644280237195, 440238283512500751367937598990506443518, 1080553092839363051071600268961987779912, 2652531780968256950476210880190871251248, 6512237534528927021994580346694932775757, 15990204597812317396332231844418085725156, 39267294943024900274062315491123497994181, 96440660571902759491472649958826589224316, 236886697526886397745682898875452806975709, 581931112051031290066801559222708545135215, 1429723352814823523599787917937119854676349, 3513024052765714047882831659059842354283294, 8632927286701273061391929152488235111376441, 21216907357105546016818560695746281111733403, 52149761330295717999722770871344773460321987, 128194103211917058320685938274196479954105930] ------------------------------------------------------------ Theorem Number, 15 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 5+ H H + HH H H HH + H HH HH H + HH H H HH 4+ H H H H + H HH HH H + HH H H HH + H HH H H 3+ H H H H + HH H HH HH + H HH H H + HH HHH HH 2+ H H H + H H + HH HH + H H 1+ H H + HH HH + H H +HH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 3 5 9 5 8 4 9 5 7 4 8 -5 - 16 P(x) x + P(x) x + P(x) x + P(x) x - 3 P(x) x - 2 P(x) x 5 6 5 5 4 6 3 7 5 4 4 5 - P(x) x + 4 P(x) x + 7 P(x) x + 5 P(x) x + P(x) x - 7 P(x) x 3 6 5 3 4 4 3 5 4 3 - 8 P(x) x - 2 P(x) x - 9 P(x) x - 7 P(x) x + 10 P(x) x 3 4 2 5 4 2 3 2 3 3 + 23 P(x) x + 10 P(x) x + 4 P(x) x + 6 P(x) - 17 P(x) - 3 P(x) x 2 4 4 3 2 3 2 - 15 P(x) x - 4 P(x) x - 24 P(x) x + 5 P(x) x - 15 P(x) x 2 2 3 2 + 35 P(x) x + 11 P(x) x - 15 P(x) x + 16 P(x) + 6 x + 8 P(x) x = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 2, 4, 7, 15, 30, 63, 136, 291, 645, 1420, 3185, 7165, 16238, 37038, 84782, 195196, 450727, 1045167, 2430671, 5670139, 13263087, 31098781, 73092513, 172145280, 406249178, 960450803, 2274602523, 5395484160, 12817567364, 30492637149, 72637127727, 173247513035, 413701984479, 988994885132, 2366792869224, 5669735144344, 13595023546331, 32628072258815, 78375187587135, 188418653355513, 453326570459234, 1091503694799630, 2629976331104194, 6341292586015729, 15299971012288316, 36938445659544857, 89234094741029071, 215693418226536816, 521659452550094967, 1262327943994496322, 3056212551359225984, 7403088603946914005, 17941246099585996437, 43500591329892557533, 105519721792338236053, 256071594843802419560, 621687550751125391323, 1509940880088451980810, 3668757665990303826763, 8917517940922081215675, 21683514123798360028370, 52743763776568122370124, 128340472029002689006662, 312394019268377467669670, 760648566597364233722061, 1852693331009565612588791, 4513955077147547432616856, 11001232965101124858973173, 26819600766697597867586268, 65401333965565227442456449, 159529471964336963644236123, 389235172618476302511361417, 949941777607356517857322817, 2318957073055254599912751038, 5662346029467444285609581245, 13829464029052914285869788090, 33784454629083715637652259466, 82552184015320681881562547554, 201761304352715054544550289607, 493222059012912522533925316810, 1205980116400173507330967924380, 2949365924229789138447422423344, 7214494642973432030321274566236, 17651023041090541485505254377530, 43193519312094325134143793214277, 105718292780304781173467600123146, 258799060372649558547954769265749, 633657348299883290468532742441247, 1551757178073305319410124682529074, 3800746405461556762195232581073262, 9310826970402275535931918090551620, 22812889153916080536243217030713277, 55904077454928787406279531848742124, 137017606048547545486637138132218946, 335874893050480395774074163735758668, 823465873165199871166656573701396648, 2019199510953637344112622569246011359, 4951959974828158540377215622798064661, 12146132863532891889383647642449057623, 29796188694378018750280678420360125375, 73104482113619636938355187813128117771, 179385254736419524471227497644280237195, 440238283512500751367937598990506443518, 1080553092839363051071600268961987779912, 2652531780968256950476210880190871251248, 6512237534528927021994580346694932775757, 15990204597812317396332231844418085725156, 39267294943024900274062315491123497994181, 96440660571902759491472649958826589224316, 236886697526886397745682898875452806975709, 581931112051031290066801559222708545135215, 1429723352814823523599787917937119854676349, 3513024052765714047882831659059842354283294, 8632927286701273061391929152488235111376441, 21216907357105546016818560695746281111733403, 52149761330295717999722770871344773460321987, 128194103211917058320685938274196479954105930] ------------------------------------------------------------ Theorem Number, 16 Let a(n) be the number of Dyck paths of semi-length n obeying the following \ restrictions The height of a peak can't be equal (for a non-negative integer r) to someth\ ing of the form , {5 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {5 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {5 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {5 r + 1} To make it crystal clear here is such a path of semi-length 8 5+ H + HH H + H HH + HH H 4+ H H + H HH + HH H + H HH 3+ H H H + HH H H HH + H HH HH H + HH H H HH 2+ H H H H + H HH HH H + HH H H HH + H HH HH H 1+ H H H H + HH H H HH + H H HH H +HH HHH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-*+-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 0, 1, 1, 2, 3, 5, 11, 15, 38, 57, 130, 240, 471, 1003, 1876, 4126, 7990, 17078, 34956, 72507, 153725, 316820, 677790, 1413037, 3010971, 6371928, 13526576, 28905832, 61442981, 131801787, 281507849, 604479417, 1297696483, 2789458358, 6010620753, 12946035692, 27959366191, 60374515188, 130599324626, 282699849182, 612457477627, 1328396617222, 2882604234359, 6262251158622, 13611263437766, 29610207354573, 64456570864936, 140400703927449, 306039446076077, 667447540327475, 1456605931202380, 3180469453373356, 6948444060721918, 15188289836744396, 33215861138502264, 72677533814020812, 159093069740402160, 348421767559285178, 763387823520951447, 1673288682758053494, 3669222482556287912, 8049115616394800773, 17664052114977169253, 38778608369957182524, 85163144180016732965, 187094895693136350714, 411168258122395089238, 903899154539856216812, 1987736031335614702072, 4372526161552046521635, 9621363493668900249537, 21177187473907197267318, 46625499970520839551023, 102683140623796513855536, 226199668098257194908302, 498423825779771854460462, 1098542374248603265770843, 2421826488230776833019825, 5340412549433041783079806, 11779027773763482916784610, 25986299166039192460562403, 57342592617335086879378413, 126562701758070382952120566, 279400660749263583548097237, 616936086344518442565553092, 1362516844066565052219915929, 3009750441701398768457643404, 6649730213621299196049240907, 14694695465497543349559193964, 32478676948571667000276769066, 71798515909209587730177571087, 158748734388360696404074086007, 351059780712940621855456478257, 776472832123158175324577500973, 1717687953786021716208519067019, 3800437339351153040449484400081, 8409936434301139949399896356874, 18613166291069572175589453153440, 41201670624671453897694084394431, 91216851942269792787647872688711, 201975977398991162976459689183229, 447288239787073825971531749345940, 990688538880585141198664241782593, 2194560233051938319960262298177319, 4862027642408214603660312054980990, 10773225999847139173737407448328946, 23874344395162684741189842678278186, 52914343688833991077475538030892923, 117292600893617849183892978840596673, 260029163468195549101764979499788199, 576536441901717311779386376854429802, 1278450095861606269981359230137388972, 2835255378111296670154762812234312811, 6288558002648590625190145494050326343, 13949529725522830666776435860485494144, 30946876018645573931802572968010222364, 68662874863373486737391637855592731845, 152361155938653365914826853482521724864, 338121550067807241094220650409101274012, 750441751650933668250250457886538220359] This concludes this exciting paper with its, 16, theorems that took, 10442.562, to generate. --------------------------------------------------