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, 2 r + 3 (ii) the heights of the valleys are not allowed to take certain values, 2 r + 3 (iii) the upward runs can't have certain values, 2 r + 3 (iv) the downward runs can't have certain values, 2 r + 3 ------------------------------------------------------------ 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, 100, 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] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 3+ H + H H + HH HH 2.5+ H H + H H + H H + H H 2+ H H H H H H + HH HH H H HH HH + H H H H H H H H H H 1.5+ HH HH HH HH HH HH HH HH HH HH + 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 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 3 3 3 2 P(x) x - P(x) x - P(x) x + P(x) - 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (2 n - 1) a(n - 1) (n - 2) a(n - 2) a(n) = -------------------- + 3/4 ---------------- n + 1 n + 1 (2 n - 3) (n - 2) a(n - 3) (n - 2) (n - 3) a(n - 4) - 19/4 -------------------------- + 23/4 ------------------------ (n + 1) n (n + 1) n subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10] Just for fun, a(1000), equals 2091807408569580495806858158603634865965892106089733870741237813328607920097\ 192154869960248164837963878141432180985524283373487058281906552029040529\ 105554247685896214052715696224587320197998474940796077868909272084630579\ 073344255334028030353161093497007292104254923918086216077564842915603646\ 734277348841588741357323474691318722179408520523714883799318249437455065\ 609086661314774483947995722894490959981935169075425230698063762364116063\ 925447148814831409450519552286613301273528273967788430389623092442888551\ 00420031393254309216073963443258531946326592 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 10, 26, 73, 211, 630, 1918, 5944, 18668, 59311, 190243, 615269, 2004025, 6568174, 21645438, 71681152, 238416580, 796107464, 2667768904, 8968626418, 30240087086, 102238147891, 346514952331, 1177137322768, 4007326361986, 13669068510355, 46711170248183, 159899495303170, 548239080150964, 1882547609495918, 6473445649582702, 22289614990054804, 76844749808542752, 265240722138647848, 916542925435941016, 3170490488962229666, 10978361620419086878, 38050836199648806832, 132003739295654672288, 458336898299337389176, 1592731179647047816456, 5539147372699716292782, 19278397252149072957430, 67144783510977781292782, 234020372004098188781294, 816173717862592612095931, 2848310823550010264748331, 9946195070493935905342754, 34752096846844356608052928, 121492573723274065746782356, 424965729724986210334066828, 1487252939350238878476066961, 5207559972930290080162726687, 18242924008420031564631470699, 63937839847917393677053053883, 224190811906862448816952048084, 786443186109759025676790140414, 2759944049159695398638082071182, 9689705499782879737971134629942, 34032397051513870217854824705849, 119575091303511375375852324889363, 420290850338817368151589425462094, 1477798545029540420475101554032014, 5197947572864762967786298700883004, 18289229262458766929906360779137688, 64372659016508808143565473281880756, 226644874989213423590879554064645044, 798224066086982890986490172624490358, 2812123626646071603709661773786964322, 9909940641278328450187604549396319424, 34932629096517215773190969375145818704, 123171925942262852453727416626502492432, 434419417794604713731879202058499353840, 1532571297349428315119992948243188469294, 5408080543848836989075546658750300454038, 19088586775071194339579396132604350096062, 67392230289889284712631980419658521072286, 237984502320302368880873397596958128821088, 840596898334587256867517230380851241540352, 2969782931526114453285021806068481214508504, 10494387425572016549372108310139844062360904, 37092206749686294813058124112080687420017432, 131129151974825388984163394313590661606182296, 463665434843834327783533182800457260363814680, 1639823241289127022761984690398474032921602200, 5800617503249234867223315788272576387481171686, 20522694971400634620406881139006729356057492918, 72623249986630870018612296037918944238071889024, 257037398826754306994500288369330255368205414948, 909901915172720635517882245202481999613688004866, 3221579087063273771060159674524234342817327900378, 11408206083937759265421675169732156368086711753584, 40405333643397594075614428835011091272242205200692, 143130207471773819571032600404978112653524311301931, 507100105234281282927160949795028574508354762378827, 1796902338665082183141757938838653457003459258680750, 6368281326912628307690946092566447516334743223474644, 22572811888639848332091438375932298250025406632415394] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H + HH HH + HH HH + 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 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 + H H H H H H H H H H H H 0.5+ HH H H H H H H H H H 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 HH HH HH HH HH H +H HH HH 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 3 3 3 2 P(x) x - P(x) x - P(x) x + P(x) - 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (2 n - 1) a(n - 1) (n - 2) a(n - 2) a(n) = -------------------- + 3/4 ---------------- n + 1 n + 1 (2 n - 3) (n - 2) a(n - 3) (n - 2) (n - 3) a(n - 4) - 19/4 -------------------------- + 23/4 ------------------------ (n + 1) n (n + 1) n subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10] Just for fun, a(1000), equals 2091807408569580495806858158603634865965892106089733870741237813328607920097\ 192154869960248164837963878141432180985524283373487058281906552029040529\ 105554247685896214052715696224587320197998474940796077868909272084630579\ 073344255334028030353161093497007292104254923918086216077564842915603646\ 734277348841588741357323474691318722179408520523714883799318249437455065\ 609086661314774483947995722894490959981935169075425230698063762364116063\ 925447148814831409450519552286613301273528273967788430389623092442888551\ 00420031393254309216073963443258531946326592 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 10, 26, 73, 211, 630, 1918, 5944, 18668, 59311, 190243, 615269, 2004025, 6568174, 21645438, 71681152, 238416580, 796107464, 2667768904, 8968626418, 30240087086, 102238147891, 346514952331, 1177137322768, 4007326361986, 13669068510355, 46711170248183, 159899495303170, 548239080150964, 1882547609495918, 6473445649582702, 22289614990054804, 76844749808542752, 265240722138647848, 916542925435941016, 3170490488962229666, 10978361620419086878, 38050836199648806832, 132003739295654672288, 458336898299337389176, 1592731179647047816456, 5539147372699716292782, 19278397252149072957430, 67144783510977781292782, 234020372004098188781294, 816173717862592612095931, 2848310823550010264748331, 9946195070493935905342754, 34752096846844356608052928, 121492573723274065746782356, 424965729724986210334066828, 1487252939350238878476066961, 5207559972930290080162726687, 18242924008420031564631470699, 63937839847917393677053053883, 224190811906862448816952048084, 786443186109759025676790140414, 2759944049159695398638082071182, 9689705499782879737971134629942, 34032397051513870217854824705849, 119575091303511375375852324889363, 420290850338817368151589425462094, 1477798545029540420475101554032014, 5197947572864762967786298700883004, 18289229262458766929906360779137688, 64372659016508808143565473281880756, 226644874989213423590879554064645044, 798224066086982890986490172624490358, 2812123626646071603709661773786964322, 9909940641278328450187604549396319424, 34932629096517215773190969375145818704, 123171925942262852453727416626502492432, 434419417794604713731879202058499353840, 1532571297349428315119992948243188469294, 5408080543848836989075546658750300454038, 19088586775071194339579396132604350096062, 67392230289889284712631980419658521072286, 237984502320302368880873397596958128821088, 840596898334587256867517230380851241540352, 2969782931526114453285021806068481214508504, 10494387425572016549372108310139844062360904, 37092206749686294813058124112080687420017432, 131129151974825388984163394313590661606182296, 463665434843834327783533182800457260363814680, 1639823241289127022761984690398474032921602200, 5800617503249234867223315788272576387481171686, 20522694971400634620406881139006729356057492918, 72623249986630870018612296037918944238071889024, 257037398826754306994500288369330255368205414948, 909901915172720635517882245202481999613688004866, 3221579087063273771060159674524234342817327900378, 11408206083937759265421675169732156368086711753584, 40405333643397594075614428835011091272242205200692, 143130207471773819571032600404978112653524311301931, 507100105234281282927160949795028574508354762378827, 1796902338665082183141757938838653457003459258680750, 6368281326912628307690946092566447516334743223474644, 22572811888639848332091438375932298250025406632415394] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {2 r + 3} 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 + HH H + H H + H H 2+ H H H H + HH HH H H + H H H H H H + HH H HH H HH 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 4 8 4 7 4 6 3 7 4 5 4 4 P(x) x - 4 P(x) x + 6 P(x) x + P(x) x - 4 P(x) x + P(x) x 3 5 3 4 2 5 3 3 2 4 3 2 - 4 P(x) x + 3 P(x) x + 3 P(x) x + P(x) x - 2 P(x) x - P(x) x 2 3 2 2 3 2 2 - P(x) x - 2 P(x) x + P(x) x + 2 P(x) x + 2 P(x) x - P(x) x - P(x) + 1 = 0 For the sake of the OEIS are the first , 100, terms [1, 1, 2, 4, 9, 20, 49, 124, 328, 886, 2451, 6886, 19621, 56505, 164258, 481206, 1419352, 4211141, 12559453, 37630898, 113217787, 341901457, 1035981368, 3148732001, 9597057937, 29326418704, 89827722566, 275749133292, 848205209366, 2614018626033, 8070151675714, 24955703167003, 77290771330682, 239725377931894, 744545848432909, 2315398426996593, 7209174870122282, 22472023871390289, 70124403384555250, 219049446273934868, 684918038518195040, 2143569933620342658, 6714597249696548347, 21050749052816264022, 66048607994003542488, 207392332429906452872, 651688482232760908831, 2049236433565099756349, 6448162551856444690156, 20302979315435366720059, 63966440022455015169504, 201652030801511665231334, 636064329451966233958298, 2007419256691545835635257, 6338767810719145553271593, 20025940068771074756800752, 63298634499718878297690293, 200171204887472815628744513, 633297190938581414664224043, 2004497159721156933253810293, 6347297047844815332866239521, 20107199352490197399843985559, 63721781833549103155001717831, 202019024497697770822806849150, 640706873549652170394453085122, 2032751176257047230338082287299, 6451519026495022442572445785708, 20482741421858137503526460632281, 65051623458355179360971010167060, 206665490657419717666718225460230, 656770359692030327438369974545498, 2087810337310725015496750156059091, 6638910002383968648814661992748065, 21116757426304763239949147207636815, 67186034628571547749146138106807889, 213820267721874977336221428181780840, 680665425308508397003763349938963990, 2167357129627970284455087316328408663, 6902975807073746705542057105107774548, 21991180212298405967209688982253544507, 70075203958787258625763743229386205104, 223347596134593007003882645051512351035, 712027554176353398978911594769261684954, 2270432214376639408510667110818605096125, 7241261043650991649486765712538947376474, 23099978434708042178407508202636609222118, 73705265132181816628922120462849634810704, 235219300213000762394229644167756602592435, 750814934023507481719003567351164778656536, 2397046350557964243471911481351002868290860, 7654233021009732622414767170769952670220827, 24445945778726318129593045251069144342005060, 78089057959760415158375607482380838452727422, 249488201474384834051450540108748754971390080, 797231955222367908352427816943947674388351053, 2547960323790169568936495344705140687442980520, 8144648954644092358040604477073239857412001004, 26038882573091356445800767363124822756172995451, 83260907757500241776433331537566303126145059392, 266273147373638596875339544340865029724627496665, 851686339942831448288557339144758149868990420925] ------------------------------------------------------------ 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 , {2 r + 3} 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 HH H H 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 2 2 2 2 2 P(x) x - 3 P(x) x + 4 P(x) x + 3 P(x) x - P(x) - 7 P(x) x + 2 P(x) + 3 x - 1 = 0 The sequence a(n) satisfies the linear recurrence 3 (2 n - 3) a(n - 1) (8 n - 11) a(n - 2) (5 n - 32) a(n - 3) a(n) = -------------------- - ------------------- - ------------------- n - 1 n - 1 n - 1 (7 n - 31) a(n - 4) 3 (n - 4) a(n - 5) + ------------------- - ------------------ n - 1 n - 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 5, a(4) = 14, a(5) = 41] Just for fun, a(1000), equals 1089066382306852761044020352434471381384852478474402956280586147893346563165\ 150356790025903379881182338889373531010389847325439350403916885914216211\ 447761849212852518052341647498136958014015474902547174686293164543707991\ 470196554835720855040832181986232993747560108338572973029156653494227566\ 100760638266683488520487026135373681625835099282417680801697360282573054\ 558240776585363668162423548577515291983442150687263160922163351419462252\ 13151906015970628297418208397574085805152379448469499862124272 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 5, 14, 41, 123, 374, 1147, 3538, 10958, 34042, 105997, 330632, 1032781, 3229714, 10109310, 31667245, 99260192, 311294876, 976709394, 3065676758, 9625674442, 30231524869, 94972205349, 298419158008, 937861780439, 2947969125284, 9267666915326, 29138952247415, 91627769596164, 288153865279528, 906277361792206, 2850578235455193, 8966774960047291, 28207708926269084, 88741086595613573, 279193005857170061, 878425541498638781, 2763910767064544151, 8696809432899909331, 27365991316146898387, 86114502983906378757, 270990479220170807701, 852792261327009151103, 2683755405821701721462, 8446021036389789328518, 26580925710495553880720, 83655791461524029778499, 263286877529619625688350, 828646104944966953136985, 2608045082179338506251960, 8208554991671584683810542, 25835893616336580855597695, 81317684431699317774082086, 255947492281959233845300220, 805602428761273832942388580, 2535679449249079994677644769, 7981257841296075572059755243, 25121841629303158907699211442, 79074145050907834990870642877, 248897316365118658567586355821, 783444790225811040157170094425, 2466032903322883026091312895195, 7762318392424597279140356316427, 24433517652824306964613655350930, 76909918789425897661982744784054, 242091972574389517090845629958586, 762043884664753426395783940603301, 2398728079969763136095844319944854, 7550633581696440951551801418488247, 23767692197436190897145046062065076, 74815535361523805808800324524782610, 235503645173857539126479943792784882, 741317880826599757625977553638357377, 2333523848658890183184459756771446263, 7345491715706915232548740319364773570, 23122261267749476861580732575881376480, 72784764438258320231486256314760047391, 229113854481154349709496468772791525337, 721211875475216949351373402360461614566, 2270256820186227910105000029489570574126, 7146405746023181411839217904703803863795, 22495770594018151999202406562412816022151, 70813256496983430049604385958463654788768, 222909570002952372561183464502929140992260, 701686766468626714935642974277603730108891, 2208809462217227057343891055970311157965207, 6953021816411732110130294053896439366752714, 21887153080515424855062360139205886645146305, 68897788390617048450692731416412237634548088, 216881040741610674872326281440401233569050216, 682713007653534926717860806834299266427921802, 2149092109239027163524721094856815158436126884, 6765067398932719829375526278181997847402027092, 21295579172236715105379335652566867073455904395, 67035831319876797120159174688726559563179141629, 211020546931909885093110812737194448135083156840, 664266999731156387679292589433339345604146464765, 2091032520317620303228796095944812782890734947036, 6582321061687785721502202206851428483940862837188] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 3+ H H H + H H H H H H + 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 HH HH H 2+ H H H H H H H + H H HH HH HH + H H H H H H H H 1.5+ 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+ H H H H H + H H + H H + H H 0.5+ H H + H H +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 6 2 5 2 4 5 2 3 4 P(x) x - 6 P(x) x + 11 P(x) x + 2 P(x) x - 7 P(x) x - 9 P(x) x 2 2 3 4 2 2 3 2 - 2 P(x) x + 13 P(x) x + x + 4 P(x) x - 2 P(x) x - 4 x - P(x) 2 - 6 P(x) x + 3 x + 2 P(x) + 2 x - 1 = 0 The sequence a(n) satisfies the linear recurrence 2 2 (5 n - 47 n + 86) a(n - 1) 2 (n - 7 n + 4) a(n - 2) a(n) = --------------------------- - ------------------------- (n - 2) (n - 7) (n - 2) (n - 7) 2 2 (21 n - 235 n + 614) a(n - 3) 2 (13 n - 139 n + 346) a(n - 4) - ------------------------------ + -------------------------------- (n - 2) (n - 7) (n - 2) (n - 7) (n - 6) (11 n - 97) a(n - 5) (37 n - 206) a(n - 6) + ---------------------------- - --------------------- (n - 2) (n - 7) n - 2 2 (23 n - 287 n + 890) a(n - 7) 2 (n - 6) (2 n - 13) a(n - 8) + ------------------------------ - ----------------------------- (n - 2) (n - 7) (n - 2) (n - 7) subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10, a(5) = 25, a(6) = 67, a(7) = 180, a(8) = 494] Just for fun, a(1000), equals 7568664487522070953404176986940801395544161031504968776526545665432332298188\ 142471318309485247616751674111043221424452747211384276017664325438818479\ 975945525595679591079327583463299821177998468415962975179288387316360441\ 430273934955991424925594181613151877320124707231302225138450120616174208\ 561787026452509096133299089498970311687907869049796934226942715139670159\ 920489756834202860903734701870707479542308550340114934912389554377776440\ 25256891151 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 10, 25, 67, 180, 494, 1359, 3766, 10455, 29110, 81150, 226536, 632890, 1769474, 4949726, 13851949, 38777981, 108587899, 304140386, 852015143, 2387185458, 6689287954, 18746454415, 52540795601, 147267276203, 412803155533, 1157184850151, 3244008703329, 9094481289459, 25496941892839, 71484264621066, 200421031780590, 561933799466103, 1575559466611122, 4417648636576828, 12386635752948331, 34731266042623075, 97385041045936684, 273066049317309889, 765678565317672963, 2146980868510567440, 6020220457131332417, 16881025796287479912, 47335526687500689500, 132732506651604765330, 372193575234903410134, 1043666539620627589049, 2926549008951571459476, 8206365532034551908044, 23011599550294587442803, 64527307795929984394348, 180942663551213912233279, 507386637827005487003450, 1422779550871601469258291, 3989667313295043291583880, 11187580535165834260507367, 31371554708491632982263622, 87970334161145366936056083, 246681588278869939461714664, 691731402223367403361817297, 1939717477776754650952825689, 5439258163522146695954739794, 15252500511391554195954642176, 42770328575902179730841129520, 119934538827719168457423823480, 336314878502961812671061666756, 943078852681776201164740753028, 2644539351791863974979490211373, 7415699994680987186475309758844, 20794780989158941300336626252736, 58311823344492113473382756954456, 163515511229465775174732966561154, 458523236016392777854606771199965, 1285771491172389374575494867644022, 3605506485354740539297294335807529, 10110411005659662031805585795292000, 28351195506659377953742692297731801, 79501253349198150146795373215147735, 222934151242334360848422608012532823, 625142833220189527209401718909018322, 1753000070458517689240551829002266887, 4915691632076912117552773642692089306, 13784383505661511695757258771802383173, 38653611767665091803282326312590302237, 108390901439929663503204170145247342966, 303945409985223631895710701715717387697, 852311527701094641129691976553982478612, 2390017859497439910599656776256394875292, 6701992533700211763016418795949524531435, 18793459903964576264386579173903937197199, 52699870921098318579254642932969149545093, 147778879119005562993540266890117771480741, 414395653049577979826276254418833166681860, 1162031817358019861105478768816369168912278, 3258523467039354457199797778169093276010624, 9137422174147018890588843987908274612842067, 25622796830493754135256316169507477403025576, 71850431158227944381049253324292996478806426] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 6+ H + HHHH + HH H 5+ HH HH + HH HH + H H + HH HH 4+ H H + H H + HH HH 3+ H H H + HH HH HH HH + HH H HH HH 2+ H HH HH HH + HHH H H + HH H HH HH + H HH H H 1+ HH H 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 6 2 5 2 4 5 2 3 4 P(x) x - 6 P(x) x + 11 P(x) x + 2 P(x) x - 7 P(x) x - 9 P(x) x 2 2 3 4 2 2 3 2 - 2 P(x) x + 13 P(x) x + x + 4 P(x) x - 2 P(x) x - 4 x - P(x) 2 - 6 P(x) x + 3 x + 2 P(x) + 2 x - 1 = 0 The sequence a(n) satisfies the linear recurrence 2 2 (5 n - 47 n + 86) a(n - 1) 2 (n - 7 n + 4) a(n - 2) a(n) = --------------------------- - ------------------------- (n - 2) (n - 7) (n - 2) (n - 7) 2 2 (21 n - 235 n + 614) a(n - 3) 2 (13 n - 139 n + 346) a(n - 4) - ------------------------------ + -------------------------------- (n - 2) (n - 7) (n - 2) (n - 7) (n - 6) (11 n - 97) a(n - 5) (37 n - 206) a(n - 6) + ---------------------------- - --------------------- (n - 2) (n - 7) n - 2 2 (23 n - 287 n + 890) a(n - 7) 2 (n - 6) (2 n - 13) a(n - 8) + ------------------------------ - ----------------------------- (n - 2) (n - 7) (n - 2) (n - 7) subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10, a(5) = 25, a(6) = 67, a(7) = 180, a(8) = 494] Just for fun, a(1000), equals 7568664487522070953404176986940801395544161031504968776526545665432332298188\ 142471318309485247616751674111043221424452747211384276017664325438818479\ 975945525595679591079327583463299821177998468415962975179288387316360441\ 430273934955991424925594181613151877320124707231302225138450120616174208\ 561787026452509096133299089498970311687907869049796934226942715139670159\ 920489756834202860903734701870707479542308550340114934912389554377776440\ 25256891151 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 10, 25, 67, 180, 494, 1359, 3766, 10455, 29110, 81150, 226536, 632890, 1769474, 4949726, 13851949, 38777981, 108587899, 304140386, 852015143, 2387185458, 6689287954, 18746454415, 52540795601, 147267276203, 412803155533, 1157184850151, 3244008703329, 9094481289459, 25496941892839, 71484264621066, 200421031780590, 561933799466103, 1575559466611122, 4417648636576828, 12386635752948331, 34731266042623075, 97385041045936684, 273066049317309889, 765678565317672963, 2146980868510567440, 6020220457131332417, 16881025796287479912, 47335526687500689500, 132732506651604765330, 372193575234903410134, 1043666539620627589049, 2926549008951571459476, 8206365532034551908044, 23011599550294587442803, 64527307795929984394348, 180942663551213912233279, 507386637827005487003450, 1422779550871601469258291, 3989667313295043291583880, 11187580535165834260507367, 31371554708491632982263622, 87970334161145366936056083, 246681588278869939461714664, 691731402223367403361817297, 1939717477776754650952825689, 5439258163522146695954739794, 15252500511391554195954642176, 42770328575902179730841129520, 119934538827719168457423823480, 336314878502961812671061666756, 943078852681776201164740753028, 2644539351791863974979490211373, 7415699994680987186475309758844, 20794780989158941300336626252736, 58311823344492113473382756954456, 163515511229465775174732966561154, 458523236016392777854606771199965, 1285771491172389374575494867644022, 3605506485354740539297294335807529, 10110411005659662031805585795292000, 28351195506659377953742692297731801, 79501253349198150146795373215147735, 222934151242334360848422608012532823, 625142833220189527209401718909018322, 1753000070458517689240551829002266887, 4915691632076912117552773642692089306, 13784383505661511695757258771802383173, 38653611767665091803282326312590302237, 108390901439929663503204170145247342966, 303945409985223631895710701715717387697, 852311527701094641129691976553982478612, 2390017859497439910599656776256394875292, 6701992533700211763016418795949524531435, 18793459903964576264386579173903937197199, 52699870921098318579254642932969149545093, 147778879119005562993540266890117771480741, 414395653049577979826276254418833166681860, 1162031817358019861105478768816369168912278, 3258523467039354457199797778169093276010624, 9137422174147018890588843987908274612842067, 25622796830493754135256316169507477403025576, 71850431158227944381049253324292996478806426] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {2 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H + HH HH + HH HH + H H H H + H H H H 1.5+ 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 H H H H H H H H H H H 0.5+ HH H HH H H H H H H H 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 HH HH HH HH HH H +H HH HH 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 2 2 5 2 4 5 4 3 -2 x - 68/3 P(x) x - 13/3 P(x) x + 89/3 P(x) x - 4 P(x) x - 38/3 P(x) x 11 12 5 6 10 3 x x 19 x 13 x 7 9 5 x 2 6 10 x + --- - --- - ----- - ----- + 6 x - 3 x + ----- + 68/3 P(x) x + ----- 3 3 3 3 3 3 4 14 x 2 15 2 2 2 2 + ----- + 1/3 P(x) + x P(x) + 2 P(x) x - P(x) x - 4/3 P(x) x 3 2 2 3 6 7 7 2 + 10/3 P(x) x + 28/3 P(x) x - 19/3 x P(x) - 28 x P(x) + 55/3 x P(x) 8 8 2 9 9 2 10 + 55/3 x P(x) - 30 x P(x) + 11/3 x P(x) + 3 x P(x) - 35/3 x P(x) 10 2 11 11 2 12 2 + 7 x P(x) + 7 x P(x) - 13/3 x P(x) + 22/3 x P(x) 13 13 2 14 14 2 - 4/3 x P(x) - 4 x P(x) + 1/3 x P(x) - 4/3 x P(x) - 2/3 P(x) 2 x - --- + 1/3 = 0 3 For the sake of the OEIS are the first , 100, terms [1, 1, 2, 4, 9, 19, 46, 108, 269, 661, 1668, 4185, 10622, 26902, 68484, 174223, 444275, 1132805, 2891755, 7382530, 18858641, 48180401, 123133270, 314724928, 804585916, 2057096868, 5260056347, 13451089088, 34400068344, 87980130141, 225026383503, 575571921215, 1472251945407, 3765975034099, 9633506061136, 24643405904712, 63041348135807, 161271351776991, 412567591255657, 1055451249960827, 2700136945879539, 6907760623581435, 17672262460036755, 45211606222369749, 115667209850114840, 295918950674708650, 757072050895810050, 1936882665911589950, 4955310413106447280, 12677677025871591311, 32434679402632141477, 82981351280167006473, 212301099231664864250, 543156178877382562621, 1389625759969489347213, 3555261568091119444334, 9095901757749073498482, 23271287078091348127419, 59538163347716506931891, 152324865424240476226647, 389714417278283675590171, 997062553860040197334240, 2550930180754896016379947, 6526418865622720347157363, 16697501676809700663212077, 42719701360634083126008648, 109296199709167906915493563, 279628890754908471034495373, 715416790609935037192674221, 1830359152123613044360550292, 4682886027566999758208881676, 11980941219627113644513644418, 30652673175453849335896712340, 78423429811677747173817418606, 200642699666926880251423508457, 513335076093201476527216337175, 1313344199534325925897566332115, 3360131061704777720752940500931, 8596742281861813835407576091792, 21994375069684975117893891389677, 56271614047151829934059382679916, 143968387662382355313900636167877, 368336646820569519575656865327936, 942372789730593646471934489451914, 2411018604358394404717832671277041, 6168483394282314060352248012142410, 15781789674997199867281488129088680, 40377006148333287478622431903761313, 103302774748459052112497441293652163, 264295561081393423700708752320438899, 676188467193061399731899454636054581, 1729998222129288757355183591806510402, 4426123837150957403317569758821460691, 11324041973459677555834899733250132709, 28972060622411810604294489233896556359, 74123736694520116150573533697439154154, 189642306249873913788832557745192040483, 485191468016899386827304490280823924990, 1241340959492709467312584995258635803922, 3175916085917421026219100426525501586502, 8125441256026178092287720088221572020581] ------------------------------------------------------------ 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 , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H + HH + HH + H H + H H 1.5+ 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 H H H H + H H H H H H H H H H H H H H 0.5+ HH H HH H H H H H H H H H 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 HH HH HH HH HH HH H +H HH HH HH 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 2 2 P(x) x + P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence (2 n + 1) a(n - 1) 3 (n - 1) a(n - 2) a(n) = ------------------ + ------------------ n + 2 n + 2 subject to the initial conditions [a(1) = 1, a(2) = 2] Just for fun, a(1000), equals 6113276597677185504356904766347702612354574971465608501154658923615549572276\ 696990107943183029388971134843974419526697509491161299179783336635341085\ 951686706984893024288224904033483357682387428696232998837169493679543025\ 183026827681506943202019217503411671799888555630269575896218409691887122\ 093560366976953000654462569519440192461932987949316582488835710972517056\ 497520791693103466653417515528995390532609891053412869321468991714009337\ 7138459245912955193770266157466468457 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, 1697385471211, 4859761676391, 13933569346707, 40002464776083, 114988706524270, 330931069469828, 953467954114363, 2750016719520991, 7939655757745265, 22944749046030949, 66368199913921497, 192137918101841817, 556704809728838604, 1614282136160911722, 4684478925507420069, 13603677110519480289, 39532221379621112004, 114956499435014161638, 334496473194459009429, 973899740488107474693, 2837208756709314025578, 8270140811590103129028, 24119587499879368045581, 70380687801729972163737, 205473381836953330090977, 600161698382141668958313, 1753816895177229449263803, 5127391665653918424581931, 14996791899280244858336604, 43881711243248048262611670, 128453535912993825479057919, 376166554620363320971336899, 1101997131244113831001323618, 3229547920421385142120565580, 9468017265749942384739441267, 27766917351255946264000229811, 81459755507915876737297376646, 239056762740830735069669439852, 701774105036927170410592656651, 2060763101398061220299787957807, 6053261625552368838017538638577, 17785981695172350686294020499397, 52274487460035748810950928411209, 153681622703766437645990598724233, 451929928113276686826984901736388, 1329334277731700374912787442584082, 3911184337415864255099077969308357, 11510402374965653734436362305721089, 33882709435158403490429948661355518, 99762777233730236158474945885114348, 293804991106867190838370294149325217, 865461205861621792586606565768282577, 2549948950073051466077548390833960154, 7514646250637159480132421134685515996, 22150145406114764734833589779994282345, 65303054248346999524711654923215773701, 192564948449128362785882746541078077821, 567944426681696509718034692302003744197, 1675395722976475387857861526496400455935, 4943221572052274428484817274841589781103, 14587540897567180436019575590444202957764, 43055804394719442101962182766220627765254, 127103430617648266466982424978107271745123, 375281510930976756310181851730346874521559, 1108229819877900763405338193186744667723583, 3273209089476438052473101825635320104642103, 9669131152389329200998265687814683780583133, 28567321136213468215221364999058944720713501, 84414794291793480358891042199686850901302514, 249478578991224378680142561460010030467811580, 737415571391164350797051905752637361193303669] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 6+ H + HHHH + HH H 5+ HH HH + HH HH + H H + HH HH 4+ HH H H + H HH H H + HH HH HH HH 3+ H H H + HH HH + HH HH 2+ HH HH + H H + HH HH + H H 1+ HHH HH HH + H H H H +HH HHHH 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 2 2 2 2 P(x) x - 3 P(x) x + P(x) x + 2 P(x) x - 3 P(x) x + P(x) + x - 1 = 0 The sequence a(n) satisfies the linear recurrence (5 n + 2) a(n - 1) (11 n - 31) a(n - 3) a(n) = ------------------ - 4 a(n - 2) - -------------------- n + 1 n + 1 3 (5 n - 16) a(n - 4) 2 (2 n - 7) a(n - 5) + --------------------- - -------------------- n + 1 n + 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 20] Just for fun, a(1000), equals 1799993429501472982316532100035564849515281386617048658519803624568997431117\ 673712910728405651652486302434954557299298995838081226779107798433888410\ 214790178377696612650654905563133447873895355421719061002311721825890506\ 103288477776692288553808437473436799311814511557807702234009760766293286\ 112183609412779976959703000823185665227984086055003838706723031838165780\ 801621425362551713402541175583951276273510 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 20, 46, 106, 248, 583, 1382, 3291, 7879, 18935, 45679, 110537, 268265, 652697, 1591727, 3889788, 9523853, 23358958, 57383956, 141178327, 347808104, 857950994, 2118844049, 5238597807, 12965230766, 32119356924, 79643399855, 197654281051, 490925173264, 1220275537498, 3035403970871, 7555703827461, 18819942335986, 46906475428998, 116978403726829, 291893950182652, 728752358192452, 1820371551612567, 4549416385046238, 11375170923190053, 28454984578745935, 71211324309739903, 178288215020546701, 446552063180558370, 1118898983190136311, 2804611911777476478, 7032535471161541826, 17640172034511257214, 44262933289098852910, 111101287927405907783, 278955428364888474330, 700620586020507352050, 1760188091066227588905, 4423431767367680943062, 11119360545983881350860, 27958692385203334954864, 70318074534178033405850, 176899588748307937974611, 445136525906120431507460, 1120374342353604910073438, 2820549210655529015413113, 7102349306325660286579136, 17888154082465231171625284, 45063157938230075460940048, 113544960694329387173598208, 286155369119212371829250423, 721309195092517171249268264, 1818546470025872236061155480, 4585731444439767224303399401, 11565704848177093471780747964, 29175139136751013205152106114, 73608717529546379922166726684, 185745910394877502321804102024, 468793130003551884573514599245, 1183350834763975377026401821056, 2987545333763121283172908073725, 7543669228976405853019460099045, 19050940723339117080890647703815, 48118759664551499522530199243369, 121555674240218500064479128973790, 307112513947418170317558653235179, 776032568361030552153696571961912, 1961197262219940246795134465157370, 4957015550042231380884527654774667, 12530712708561842412876632889978362, 31680104598200735709431554464897894, 80103533041067776246041673461416405, 202567556716888646794853529174337151, 512318711012686500106032529467666378, 1295870613667515763142270143699250698, 3278182886490451603662269404259253151, 8293806049446667826283498364136683650, 20985668315569132182065569696845836944, 53105446769453220929287835785445865747, 134400779762202508696290866644198464172, 340181051865767257554864539055627746093, 861119125497622007457876919389016969143] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {2 r + 3} 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 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 0.5+ HH H HH 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 2 3 2 2 2 2 P(x) x - 3 P(x) x + P(x) x + 2 P(x) x - 3 P(x) x + P(x) + x - 1 = 0 The sequence a(n) satisfies the linear recurrence (5 n + 2) a(n - 1) (11 n - 31) a(n - 3) a(n) = ------------------ - 4 a(n - 2) - -------------------- n + 1 n + 1 3 (5 n - 16) a(n - 4) 2 (2 n - 7) a(n - 5) + --------------------- - -------------------- n + 1 n + 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 20] Just for fun, a(1000), equals 1799993429501472982316532100035564849515281386617048658519803624568997431117\ 673712910728405651652486302434954557299298995838081226779107798433888410\ 214790178377696612650654905563133447873895355421719061002311721825890506\ 103288477776692288553808437473436799311814511557807702234009760766293286\ 112183609412779976959703000823185665227984086055003838706723031838165780\ 801621425362551713402541175583951276273510 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 20, 46, 106, 248, 583, 1382, 3291, 7879, 18935, 45679, 110537, 268265, 652697, 1591727, 3889788, 9523853, 23358958, 57383956, 141178327, 347808104, 857950994, 2118844049, 5238597807, 12965230766, 32119356924, 79643399855, 197654281051, 490925173264, 1220275537498, 3035403970871, 7555703827461, 18819942335986, 46906475428998, 116978403726829, 291893950182652, 728752358192452, 1820371551612567, 4549416385046238, 11375170923190053, 28454984578745935, 71211324309739903, 178288215020546701, 446552063180558370, 1118898983190136311, 2804611911777476478, 7032535471161541826, 17640172034511257214, 44262933289098852910, 111101287927405907783, 278955428364888474330, 700620586020507352050, 1760188091066227588905, 4423431767367680943062, 11119360545983881350860, 27958692385203334954864, 70318074534178033405850, 176899588748307937974611, 445136525906120431507460, 1120374342353604910073438, 2820549210655529015413113, 7102349306325660286579136, 17888154082465231171625284, 45063157938230075460940048, 113544960694329387173598208, 286155369119212371829250423, 721309195092517171249268264, 1818546470025872236061155480, 4585731444439767224303399401, 11565704848177093471780747964, 29175139136751013205152106114, 73608717529546379922166726684, 185745910394877502321804102024, 468793130003551884573514599245, 1183350834763975377026401821056, 2987545333763121283172908073725, 7543669228976405853019460099045, 19050940723339117080890647703815, 48118759664551499522530199243369, 121555674240218500064479128973790, 307112513947418170317558653235179, 776032568361030552153696571961912, 1961197262219940246795134465157370, 4957015550042231380884527654774667, 12530712708561842412876632889978362, 31680104598200735709431554464897894, 80103533041067776246041673461416405, 202567556716888646794853529174337151, 512318711012686500106032529467666378, 1295870613667515763142270143699250698, 3278182886490451603662269404259253151, 8293806049446667826283498364136683650, 20985668315569132182065569696845836944, 53105446769453220929287835785445865747, 134400779762202508696290866644198464172, 340181051865767257554864539055627746093, 861119125497622007457876919389016969143] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {2 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {2 r + 3} 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 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 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 2 4 2 3 2 2 3 2 2 P(x) x - 2 P(x) x + 3 P(x) x + P(x) x - P(x) x - 2 P(x) x + 3 P(x) x - P(x) - x + 1 = 0 The sequence a(n) satisfies the linear recurrence (3 n - 7) a(n - 2) 2 (3 n - 7) a(n - 3) a(n) = 2 a(n - 1) + ------------------ - -------------------- n + 1 n + 1 2 (n - 1) a(n - 4) 2 a(n - 5) (n - 5) a(n - 6) + ------------------ - ---------- - ---------------- n + 1 n + 1 n + 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 19, a(6) = 42] Just for fun, a(1000), equals 5418417295961267473864962248844651527814851120273322458100214563397904003815\ 291320042123849343212352887328673855224557665647689833085423197186334195\ 005310552634925671539349174410931900445930891482147321691021474631360937\ 657174490381546178466075313530801493450317219834969086175440125464981467\ 229827693122205272580023979977437982376123450031142240608738975084795041\ 8 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 19, 42, 91, 202, 445, 993, 2210, 4955, 11104, 24997, 56295, 127158, 287435, 651079, 1476014, 3351244, 7615138, 17324298, 39442468, 89882781, 204968914, 467769513, 1068177410, 2440815721, 5580396279, 12765433822, 29215857950, 66897701219, 153247575117, 351204944208, 805189013614, 1846712300534, 4236954905599, 9724238370805, 22325223518877, 51270645467089, 117778881160838, 270636573823209, 622042511739232, 1430090161353178, 3288603581713849, 7564149939580975, 17402229913133029, 40044422638558328, 92165367232341616, 212167403323750084, 488507713034772246, 1124975336676098049, 2591137415609999466, 5969129803085076549, 13753147733245577272, 31692846071913391087, 73044255792749698585, 168373745161468194352, 388171844945007599190, 895020621209559652413, 2063951486667650236541, 4760159907910110223776, 10979876986134457212631, 25329442226335494139374, 58439220609843960503837, 134844218588164228697465, 311177314597976846051128, 718174246177811416320253, 1657664756294239691352996, 3826549121413159474768479, 8834060706960288414693662, 20396460097852143998479150, 47096587241890152778092563, 108758502967416982323680287, 251174252902139466098909056, 580128421395542208377692836, 1340014013180147115390796282, 3095492779962471346645303494, 7151293912179736094882457523, 16522394514994563354128449307, 38176319678496457164329235900, 88215937103280746884845940637, 203859618729755235105840166274, 471135460046430726499639256771, 1088905269461874065100130057853, 2516885419174359150346104219414, 5817885486910125493085118798249, 13449143695791646111190072112517, 31092183582226218936578919015601, 71884348547404553112269414205130, 166204742207230532385765916285928, 384306627879043958260685873545826, 888663190220519595931695347119113, 2055042644930382703933184357964023, 4752567665860975596971340711027778, 10991554346322936797686540050461919, 25422178873947671138522934358166660, 58801556611872968393484434523036821, 136015005122902765757912816872241024, 314634493821224121911774539842768662] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 6+ H + HHHH + HH H 5+ HH HH + HH HH + H H + HH HH 4+ H H + H H + HH HH 3+ H H + HH HH + HH HH 2+ HH HH + H H + HH HH + H H 1+ HHH HHH HH HH + H H H H H H +HH HHHH HHHH 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 2 2 2 2 2 P(x) x - 2 P(x) x + 3 P(x) x + 2 P(x) x - P(x) - 5 P(x) x + 2 P(x) + 2 x - 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (n - 7) a(n - 2) (11 n - 47) a(n - 3) a(n) = 3 a(n - 1) + ------------------ - -------------------- n - 1 n - 1 8 (n - 4) a(n - 4) 4 (n - 4) a(n - 5) + ------------------ - ------------------ n - 1 n - 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 20] Just for fun, a(1000), equals 6518095374157182391051665651013497156526168379323387587026425762981831175255\ 450564925478659398165173453730234483047213523100479591173592851856140091\ 492231625975148074354018030218082111511390868335258556018772435879738102\ 444439360824076984596753480234646833035378447030363331791183701601235128\ 552490840734163942586862393373920465704545148748399899701398685326183272\ 89 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 20, 46, 105, 243, 560, 1299, 3006, 6980, 16185, 37601, 87281, 202826, 471088, 1094893, 2543899, 5912999, 13741230, 31941591, 74238516, 172573596, 401126561, 932471007, 2167525483, 5038760996, 11712960129, 27228883878, 63296817932, 147145646169, 342062491676, 795193000622, 1848564307013, 4297369411471, 9990042976219, 23223954412728, 53988669058517, 125508141326314, 291769273011446, 678280205440227, 1576803647503683, 3665619804642041, 8521507858091964, 19810087612495493, 46052775443380952, 107059658963243834, 248883170555851441, 578582969184447607, 1345040935500736449, 3126840038689165574, 7269016352304069979, 16898409915034615238, 39284018711831799178, 91324252657730237037, 212303060931010811989, 493544696189403761071, 1147351955615968145912, 2667269535400107727583, 6200648388915574000628, 14414758051562474692630, 33510243097269881711913, 77901861577600269751107, 181099842045187481295216, 421006046077631786095347, 978720260186055788398518, 2275248530448091274300076, 5289310904713663619955429, 12296155913430864099664653, 28585093648369314183652413, 66452280022959877971583362, 154482805569286374739808651, 359128950310308682459911642, 834873507855514790011247494, 1940845428515213379853727849, 4511918174194114917376857837, 10488937173407432782434365307, 24383820423615419105396406696, 56685505098225506668697347311, 131777810940427742847757793458, 306346243048447634311275092448, 712168609740585881630514928919, 1655591154065290119116752395319, 3848782475649227636762604286547, 8947333728557688553684822997922, 20800027349395470594741568856751, 48354197066720262313617664860956, 112409870079074055099969328206588, 261321243453177111267414223754603, 607498186684803366322924986623549, 1412261943227129931533915840568029, 3283110697507842319146063698957872, 7632306392754070460693284402361107, 17742959717733327963788468259689286, 41247377065199685289124899673303516, 95888518119017696643300000016463593, 222913759944387047315438668962473033, 518211620528997535706671541049803529, 1204695859817236209132437285240928114] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {2 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {2 r + 3} 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 + HH 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 4 2 3 2 2 3 2 2 P(x) x - 4 P(x) x + 6 P(x) x + 2 P(x) x - 2 P(x) x - 6 P(x) x 2 + 5 P(x) x + x - P(x) - 2 x + 1 = 0 The sequence a(n) satisfies the linear recurrence 2 2 (3 n - 9 n - 8) a(n - 1) 2 (n - 9 n + 16) a(n - 2) a(n) = ------------------------- + -------------------------- (n + 1) (n - 4) (n + 1) (n - 4) 2 (23 n - 141 n + 204) a(n - 3) 2 (2 n - 5) (2 n - 7) a(n - 4) - 1/2 ------------------------------ + ------------------------------ (n + 1) (n - 4) (n + 1) (n - 4) 2 2 (n - 3) a(n - 5) - ------------------- (n + 1) (n - 4) subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 19] Just for fun, a(1000), equals 1968123447799563822698647333615591790710332754533173459495442939271259468411\ 090707557997318250564278115710649920463966769769432375543824531760088425\ 722156005720467261922370220137080278054237716794630521024819030051757923\ 383695568095146416408345635164876941741073059322388274579099540093021419\ 2174694182925107620552800538201350548961653297728 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 19, 42, 90, 198, 428, 940, 2042, 4481, 9763, 21414, 46742, 102494, 223990, 491068, 1074040, 2354410, 5152286, 11293456, 24723608, 54189448, 118663850, 260078464, 569630966, 1248439345, 2734758115, 5993548358, 13130501094, 28776633046, 63047992294, 138173640172, 302748430056, 663486828366, 1453811625722, 3186074254812, 6981459295580, 15300018821572, 33526892940752, 73474652887112, 161007949057108, 352850221000986, 773226350050478, 1694528323959836, 3713385852472220, 8137885614329052, 17833504347948972, 39082079693498584, 85645742218561608, 187692250415862868, 411317122980678604, 901398922896126956, 1975373881159497092, 4329017125952034668, 9486871203009298118, 20790398171679448744, 45561459550887441646, 99847519031916402193, 218812929586563001507, 479526387964550967110, 1050869791918465485958, 2302970336937595637862, 5046906853925692901126, 11060242550893558694732, 24238292945232881979320, 53117953328939581120614, 116406988899778683885186, 255104612986094405269372, 559057279680448184947420, 1225167665661792539896740, 2684934764218335522203320, 5884003581070838509516936, 12894702072204578443221356, 28258589411983388382603038, 61928277515145034012774170, 135715093124502007998077812, 297417678836521785172086420, 651787329230819721514390916, 1428382865518145459951984404, 3130284088574578967659269000, 6859975142343560024881966640, 15033553739599890688252421132, 32945833456184885546600984996, 72200399982741611227961075664, 158226234478915405392131637216, 346750895626095039036449083168, 759900126261765315440717968884, 1665311996422623367443668102944, 3649510055998459952343756285788, 7997857366839942818488328262778, 17527203616569864467912611245070, 38410655514193293509519750375708, 84176471058473244406454749553628, 184471720889704957029804496746748, 404267482645315907946581127324892, 885947307349723553068044502253944, 1941542562427268732017304473181136, 4254867068681139633697684006002252] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {2 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {2 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H H H H H + HH HH HH HH HH HH + HH HH HH HH HH 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 1.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 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 0.5+ HH H HH HH + H H H H + H H H H +H HH 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 4 2 3 2 2 3 2 2 P(x) x - 4 P(x) x + 6 P(x) x + 2 P(x) x - 2 P(x) x - 6 P(x) x 2 + 5 P(x) x + x - P(x) - 2 x + 1 = 0 The sequence a(n) satisfies the linear recurrence 2 2 (3 n - 9 n - 8) a(n - 1) 2 (n - 9 n + 16) a(n - 2) a(n) = ------------------------- + -------------------------- (n + 1) (n - 4) (n + 1) (n - 4) 2 (23 n - 141 n + 204) a(n - 3) 2 (2 n - 5) (2 n - 7) a(n - 4) - 1/2 ------------------------------ + ------------------------------ (n + 1) (n - 4) (n + 1) (n - 4) 2 2 (n - 3) a(n - 5) - ------------------- (n + 1) (n - 4) subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 19] Just for fun, a(1000), equals 1968123447799563822698647333615591790710332754533173459495442939271259468411\ 090707557997318250564278115710649920463966769769432375543824531760088425\ 722156005720467261922370220137080278054237716794630521024819030051757923\ 383695568095146416408345635164876941741073059322388274579099540093021419\ 2174694182925107620552800538201350548961653297728 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 19, 42, 90, 198, 428, 940, 2042, 4481, 9763, 21414, 46742, 102494, 223990, 491068, 1074040, 2354410, 5152286, 11293456, 24723608, 54189448, 118663850, 260078464, 569630966, 1248439345, 2734758115, 5993548358, 13130501094, 28776633046, 63047992294, 138173640172, 302748430056, 663486828366, 1453811625722, 3186074254812, 6981459295580, 15300018821572, 33526892940752, 73474652887112, 161007949057108, 352850221000986, 773226350050478, 1694528323959836, 3713385852472220, 8137885614329052, 17833504347948972, 39082079693498584, 85645742218561608, 187692250415862868, 411317122980678604, 901398922896126956, 1975373881159497092, 4329017125952034668, 9486871203009298118, 20790398171679448744, 45561459550887441646, 99847519031916402193, 218812929586563001507, 479526387964550967110, 1050869791918465485958, 2302970336937595637862, 5046906853925692901126, 11060242550893558694732, 24238292945232881979320, 53117953328939581120614, 116406988899778683885186, 255104612986094405269372, 559057279680448184947420, 1225167665661792539896740, 2684934764218335522203320, 5884003581070838509516936, 12894702072204578443221356, 28258589411983388382603038, 61928277515145034012774170, 135715093124502007998077812, 297417678836521785172086420, 651787329230819721514390916, 1428382865518145459951984404, 3130284088574578967659269000, 6859975142343560024881966640, 15033553739599890688252421132, 32945833456184885546600984996, 72200399982741611227961075664, 158226234478915405392131637216, 346750895626095039036449083168, 759900126261765315440717968884, 1665311996422623367443668102944, 3649510055998459952343756285788, 7997857366839942818488328262778, 17527203616569864467912611245070, 38410655514193293509519750375708, 84176471058473244406454749553628, 184471720889704957029804496746748, 404267482645315907946581127324892, 885947307349723553068044502253944, 1941542562427268732017304473181136, 4254867068681139633697684006002252] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {2 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {2 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {2 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {2 r + 3} 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 2+ H H H + HH 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 H H + H H H H H H H H + HH HH HH HH HH HH HH HH +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 2 6 2 5 2 4 2 3 4 2 2 P(x) x - 2 P(x) x + 5 P(x) x - 6 P(x) x - 2 P(x) x + 4 P(x) x 3 2 2 2 + 4 P(x) x - P(x) x - 5 P(x) x + 4 P(x) x + x - P(x) - 2 x + 1 = 0 The sequence a(n) satisfies the linear recurrence (5 n + 2) a(n - 1) 9 (n - 5) a(n - 3) a(n) = ------------------ - 6 a(n - 2) - ------------------ n + 1 n + 1 3 (11 n - 40) a(n - 4) (41 n - 157) a(n - 5) 3 (9 n - 38) a(n - 6) + ---------------------- - --------------------- + --------------------- n + 1 n + 1 n + 1 12 (n - 4) a(n - 7) 4 (n - 5) a(n - 8) - ------------------- + ------------------ n + 1 n + 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 18, a(6) = 39, a(7) = 80, a(8) = 172] Just for fun, a(1000), equals 4922559330986032314023387012244121891442203338452801184174032777537942912509\ 713851664826065444106596849495356284389915700899646035201838083026500547\ 849578670110599800486196264111748545377456334030663223121665936295096401\ 573613645320840558842818189773624038329815367959539391385318749361343028\ 29731526376397718513293972524190574 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 18, 39, 80, 172, 357, 764, 1597, 3409, 7158, 15256, 32130, 68411, 144378, 307202, 649299, 1380906, 2921837, 6211973, 13154422, 27960094, 59244143, 125902033, 266895961, 567112395, 1202638447, 2555148180, 5420064839, 11514623372, 24430628340, 51898154750, 110131981862, 233942248323, 496513959072, 1054651851900, 2238624183919, 4754937431232, 10093846827483, 21439222138247, 45514867840872, 96671054526916, 205242416699273, 435916046518225, 925539902791055, 1965734293565575, 4173831247474491, 8864608874417260, 18822803871037308, 39976513683480936, 84887118378929185, 180284758974801939, 382829994271391814, 813055858737308991, 1726536259617850977, 3666804953737335059, 7786640331192395912, 16537135661664904747, 35117891538974782176, 74582510167019045249, 158383534411363235697, 336369992618153622410, 714322588722329366991, 1517052010571902700063, 3221670044193405992903, 6842049278389735083286, 14530136436258950790595, 30858444751327246055572, 65532989472351988577379, 139175775621142982357914, 295564089729087293992584, 627703819081627404296182, 1333044171261613551723752, 2831047559040841518427115, 6012269215497678550775840, 12768522283345139349962450, 27116469952922577005677223, 57588402093031255143283694, 122300606646946733237849913, 259734832697104239955152183, 551600547703758907058292888, 1171456121471187197206885894, 2487833393598350792579037771, 5283508614197636584581764187, 11220658541936847004930206059, 23829739462273117158473270469, 50607604849135257057224728069, 107477258098028823919512005234, 228251451721019611457021015176, 484745976394680554781265842206, 1029465018060185662603057818229, 2186312041788258054574722105801, 4643119686318841893372064223932, 9860758821325920443043475541811, 20941528119934230553977913137015, 44474261573655762916695690007281, 94451103470654423039459719973554, 200589106188511627669115527893059] ------------------------------------------------------------ This concludes this exciting paper with its, 16, theorems that took, 1754.661, to generate. --------------------------------------------------