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, 3 r + 1 (ii) the heights of the valleys are not allowed to take certain values, 3 r + 1 (iii) the upward runs can't have certain values, 3 r + 1 (iv) the downward runs can't have certain values, 3 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 , {3 r + 1} 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 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 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 4 3 2 2 P(x) x + P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (1657446640358 n - 13154733884241 n + 25055843682181) a(n - 1) a(n) = -4/3 --------------------------------------------------------------- + (n + 1) %1 4 3 2 4/9 (6555719814168 n - 81805072004652 n + 277751180414824 n - 320971975174395 n + 108137123286410) a(n - 2)/(n (n + 1) %1) + 2/27 ( 5 4 3 68835058048764 n - 871926023696388 n + 3203200747502919 n 2 - 3066275492292224 n - 3547718344871905 n + 5401104724659594) a(n - 3)/( 5 4 (n + 1) n (n - 1) %1) - 4/27 (17481919504448 n - 427300054486936 n 3 2 + 3495047953107662 n - 13109361033346295 n + 23376972138390349 n - 16137459370691294) a(n - 4)/((n + 1) n (n - 1) %1) + 8/81 (n - 4) ( 4 3 2 3277859907084 n - 151895910845864 n + 1343069428906611 n - 4194339215820769 n + 4183421674759092) a(n - 5)/((n + 1) n (n - 1) %1) 32 (n - 5) (1657446640358 n - 3126664259721) (2 n - 11) (n - 4) a(n - 6) + -- --------------------------------------------------------------------- 81 (n + 1) n (n - 1) %1 2 %1 := 546309984514 n - 5724469364693 n + 11311760686618 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 6, a(6) = 9] Just for fun, a(1000), equals 1605603620884456385712052379784545353489819961800200269468379408032446375702\ 644206347843892210545537139554137296095902675061275209296374331992968293\ 355707561166293342553341772212588735033183129557307734449238587150474628\ 410536291973038862039035434662648497667796005189088293651786775431095577\ 010744653468439144366645654603741077381276740541217495479692572911226028\ 810910125914889810204947029083228865106865083820764838963574721359853967\ 7894664770172 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 2, 6, 9, 28, 59, 142, 372, 859, 2274, 5642, 14409, 37537, 95882, 251958, 656331, 1723566, 4554516, 12020236, 31958544, 85005126, 226859619, 607186190, 1627382344, 4374213667, 11774920230, 31758271810, 85807453465, 232172679308, 629220615459, 1707515394966, 4639879581988, 12623893279229, 34385523812058, 93767062016838, 255961353697707, 699412020878198, 1912952870464092, 5236782090525072, 14348273784561248, 39344972819499448, 107973893745984420, 296533037708373736, 814962366932284464, 2241299195398899763, 6168037658709153114, 16985088423424140110, 46800589530131583303, 129028958764729108234, 355931079577475546180, 982377172853088338436, 2712786957051834753852, 7494972561717125802786, 20717321727056852346819, 57292675318194371002278, 158511062270462544618492, 438741247318216578041499, 1214897168884083229126854, 3365478282655212389750802, 9326627477123630543941785, 25856375241708547206747649, 71708508647641768561695018, 198943097034137712703703734, 552125129016058965179990179, 1532823457051308794050456046, 4256851219091217724981017132, 11825579310513245592382898732, 32861704320320766867865600912, 91345613417952445847102793462, 253987105730721077440782479013, 706412789770065672371206544682, 1965282747177412739563294540500, 5469000414893977749171758324729, 15223140163748468164938939829362, 42384881914154877542958608001750, 118038947858944911702988479651579, 328809675498469426996983844714078, 916149061489606810370781218773844, 2553215491842040868743500722724040, 7117150562656708290823952620254504, 19843571995000313216180013600209944, 55338363290849993474609101150077352, 154355943001077056789346176982944960, 430634566782854845345247939148121800, 1201657992483155016213072945610360740, 3353801640697330146276343518094765864, 9362168975755375995546032327515150280, 26139444698154932982575758186281771604, 72995359046813758747041168320143640904, 203878504311917716717175306686017901936, 569538739368710073116619255838331857008, 1591289280260471038644976554832341970304, 4446798881241334427941781185756279916022, 12428445608121503791212544828476741264571, 34742067768352529614173092583933924619070, 97132063385630582542837256203323333802776, 271604085800975097194657481808154221496193, 759583260364677916810565887120782620591250, 2124606875108366869798324076926534853130846, 5943532438125941235693813294706649139994063, 16629237373883183380237782971188079018466222, 46532939368464932853582379180404485593467984, 130229073555814225750465117845294410274333672, 364513493672426345270819011609028829729485768, 1020413929246314468855196000024729721785447276, 2856901072213446353156933167674447604599286620, 7999614431171889490866504381381534663935356032, 22402523418595965936556541735015854836933446172, 62744821127446505382462504120029747678153150475, 175756318465625249160376240842288910456327467822, 492374104734552728021273167109171565504893759142, 1379525591490575413711985183715271758761858173119, 3865571817612204434024244008342973971761535306502, 10832939278788997569010264680567883172636612914332, 30361737466919754218613587151952854946600219540748, 85104764568989669147139613296134388662430050788176, 238576291649785550163746674702828918706493212314106, 668876720014341262383498229576901916076026471361091] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 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 4 3 2 2 P(x) x + P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (1657446640358 n - 13154733884241 n + 25055843682181) a(n - 1) a(n) = -4/3 --------------------------------------------------------------- + (n + 1) %1 4 3 2 4/9 (6555719814168 n - 81805072004652 n + 277751180414824 n - 320971975174395 n + 108137123286410) a(n - 2)/(n (n + 1) %1) + 2/27 ( 5 4 3 68835058048764 n - 871926023696388 n + 3203200747502919 n 2 - 3066275492292224 n - 3547718344871905 n + 5401104724659594) a(n - 3)/( 5 4 (n + 1) n (n - 1) %1) - 4/27 (17481919504448 n - 427300054486936 n 3 2 + 3495047953107662 n - 13109361033346295 n + 23376972138390349 n - 16137459370691294) a(n - 4)/((n + 1) n (n - 1) %1) + 8/81 (n - 4) ( 4 3 2 3277859907084 n - 151895910845864 n + 1343069428906611 n - 4194339215820769 n + 4183421674759092) a(n - 5)/((n + 1) n (n - 1) %1) 32 (n - 5) (1657446640358 n - 3126664259721) (2 n - 11) (n - 4) a(n - 6) + -- --------------------------------------------------------------------- 81 (n + 1) n (n - 1) %1 2 %1 := 546309984514 n - 5724469364693 n + 11311760686618 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 6, a(6) = 9] Just for fun, a(1000), equals 1605603620884456385712052379784545353489819961800200269468379408032446375702\ 644206347843892210545537139554137296095902675061275209296374331992968293\ 355707561166293342553341772212588735033183129557307734449238587150474628\ 410536291973038862039035434662648497667796005189088293651786775431095577\ 010744653468439144366645654603741077381276740541217495479692572911226028\ 810910125914889810204947029083228865106865083820764838963574721359853967\ 7894664770172 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 2, 6, 9, 28, 59, 142, 372, 859, 2274, 5642, 14409, 37537, 95882, 251958, 656331, 1723566, 4554516, 12020236, 31958544, 85005126, 226859619, 607186190, 1627382344, 4374213667, 11774920230, 31758271810, 85807453465, 232172679308, 629220615459, 1707515394966, 4639879581988, 12623893279229, 34385523812058, 93767062016838, 255961353697707, 699412020878198, 1912952870464092, 5236782090525072, 14348273784561248, 39344972819499448, 107973893745984420, 296533037708373736, 814962366932284464, 2241299195398899763, 6168037658709153114, 16985088423424140110, 46800589530131583303, 129028958764729108234, 355931079577475546180, 982377172853088338436, 2712786957051834753852, 7494972561717125802786, 20717321727056852346819, 57292675318194371002278, 158511062270462544618492, 438741247318216578041499, 1214897168884083229126854, 3365478282655212389750802, 9326627477123630543941785, 25856375241708547206747649, 71708508647641768561695018, 198943097034137712703703734, 552125129016058965179990179, 1532823457051308794050456046, 4256851219091217724981017132, 11825579310513245592382898732, 32861704320320766867865600912, 91345613417952445847102793462, 253987105730721077440782479013, 706412789770065672371206544682, 1965282747177412739563294540500, 5469000414893977749171758324729, 15223140163748468164938939829362, 42384881914154877542958608001750, 118038947858944911702988479651579, 328809675498469426996983844714078, 916149061489606810370781218773844, 2553215491842040868743500722724040, 7117150562656708290823952620254504, 19843571995000313216180013600209944, 55338363290849993474609101150077352, 154355943001077056789346176982944960, 430634566782854845345247939148121800, 1201657992483155016213072945610360740, 3353801640697330146276343518094765864, 9362168975755375995546032327515150280, 26139444698154932982575758186281771604, 72995359046813758747041168320143640904, 203878504311917716717175306686017901936, 569538739368710073116619255838331857008, 1591289280260471038644976554832341970304, 4446798881241334427941781185756279916022, 12428445608121503791212544828476741264571, 34742067768352529614173092583933924619070, 97132063385630582542837256203323333802776, 271604085800975097194657481808154221496193, 759583260364677916810565887120782620591250, 2124606875108366869798324076926534853130846, 5943532438125941235693813294706649139994063, 16629237373883183380237782971188079018466222, 46532939368464932853582379180404485593467984, 130229073555814225750465117845294410274333672, 364513493672426345270819011609028829729485768, 1020413929246314468855196000024729721785447276, 2856901072213446353156933167674447604599286620, 7999614431171889490866504381381534663935356032, 22402523418595965936556541735015854836933446172, 62744821127446505382462504120029747678153150475, 175756318465625249160376240842288910456327467822, 492374104734552728021273167109171565504893759142, 1379525591490575413711985183715271758761858173119, 3865571817612204434024244008342973971761535306502, 10832939278788997569010264680567883172636612914332, 30361737466919754218613587151952854946600219540748, 85104764568989669147139613296134388662430050788176, 238576291649785550163746674702828918706493212314106, 668876720014341262383498229576901916076026471361091] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {3 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 + H HH + HH HH 3+ H H + HH H + HH HH 2+ HH HH H + H H HHH + HH HH H HH + H H HH H 1+ HH HH HH HH + H H H H +HH HHHH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-*+-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 0, 1, 1, 1, 4, 3, 9, 18, 23, 68, 108, 222, 510, 895, 2080, 4229, 8611, 19337, 39348, 85819, 185720, 393010, 866313, 1863267, 4055206, 8902594, 19341525, 42574201, 93429486, 205219163, 453363136, 998974320, 2209631598, 4893289841, 10837455829, 24067834616, 53457655678, 118896921145, 264798900782, 590016293078, 1316421697859, 2939288297250, 6567947597928, 14690650428642, 32878994015842, 73646231147270, 165078249873499, 370254019445214, 831028399074827, 1866319679090262, 4193897242828534, 9429846751714458, 21213970315222320, 47750301262639320, 107535066607784161, 242290590151400440, 546175628591312355, 1231756103108622148, 2779141355607386808, 6273106776180306700, 14165553360306078922, 32000685947581192495, 72319074436894354043, 163496904220342833327, 369763891132518059190, 836550786788370433004, 1893254274606837299029, 4286173196643401313465, 9706673070887664772822, 21989085731909109289077, 49828287695444917200718, 112946613270964974809995, 256091617493789398864952, 580816528944324352070114, 1317652354736760763092773, 2990045578858558891097173, 6786828542916918364657126, 15408670708550453945470737, 34992090993047140730802813, 79483757219631635566909571, 180587659957285858857285993, 410389708236042104443431215, 932827151980562826751667450, 2120800965491342133349367857, 4822702199077353102132906564, 10969090837096842692612011192, 24953898499217458156999237901, 56779526095802018253730497559, 129219714696332287027906111626, 294135593479326492723751169878, 669647685027245202869589821421, 1524836929760082504131182134813, 3472777692116845901055914640962, 7910528174529360172480204118586, 18022179647205769364306785818204, 41065862506809446865048508805205, 93589019809523784037149867174917, 213323020785089142592069346375619, 486315409820066393860776099451944, 1108828713509835554629584828095907, 2528574236688110837114536893235988, 5767007171331584929790577353997096, 13154900710959773927984180740235785, 30011365508093340057236929770226293, 68476864959794231274022876820503124, 156264662810434675368213868647735248, 356644379567220914889878095492390665, 814079114505496227453793791180821767, 1858460877448583590857513106052552726, 4243212694632672122964586651927659348, 9689241096632213627548167392835652750, 22127754597587157104092979074737290317, 50540160785266514192449440971079767843, 115448068655352439881274259243796518307, 263746447767631222582494726029922481596, 602608978704489400042540547618495655083, 1376996286658609863130514616132456966920, 3146859207963897686792630416160256753646, 7192310551360970034419846024859033427739, 16440133739516225266302878771451066518137] ------------------------------------------------------------ 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 , {3 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 ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 2 2 2 P(x) x - P(x) x - P(x) x + P(x) - 1 = 0 The sequence a(n) satisfies the linear recurrence (4 n - 1) a(n - 1) (2 n - 1) a(n - 2) a(n - 3) (n - 4) a(n - 4) a(n) = ------------------ - ------------------ - -------- - ---------------- n + 1 n + 1 n + 1 n + 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9] Just for fun, a(1000), equals 3815969184918582708339731381315026503551170712179924901430225212675970224195\ 175928673259658617016167299278551021391753174962863676187301060520536898\ 803474672006722477524698327894400111071411504761244267409075435316229910\ 851747538765872275436718421024632044469197866106942141401970600912425548\ 374434707217892201068512004631499269198504744411532437358367642997646876\ 353802938335670980642031249392811254422732955374772320802639788902980143\ 195719366534057294302218758926431781254622848088690277835012587190846127\ 39534330611986071 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 4, 9, 22, 57, 154, 429, 1223, 3550, 10455, 31160, 93802, 284789, 871008, 2681019, 8298933, 25817396, 80674902, 253106837, 796968056, 2517706037, 7977573203, 25347126630, 80738862085, 257778971504, 824798533933, 2644335308022, 8493626448824, 27328990723991, 88076273435888, 284285615020391, 918906283429371, 2974207601755522, 9638768694329390, 31274571286496725, 101590361828264430, 330353588780170703, 1075342923114051812, 3503758934959966001, 11426684110709769209, 37298034316048691658, 121846672402217906911, 398370258741839758354, 1303437617133408126110, 4267851622898510768327, 13983974539928694754029, 45850234774474445255812, 150428554125110631145985, 493839291745701673090756, 1622172984992118130634304, 5331568321137005598292983, 17532739146145549165258768, 57686308517951932176874797, 189895903713319165311816649, 625418105100565606186412568, 2060771573361373463554220381, 6793393132139483082486854356, 22404456986002745157503844347, 73920774614279746859303111580, 243992767147579170197542153740, 805675189670564339859633140515, 2661399890266809551858173736308, 8794722825936467701229310231763, 29073081698294754677375412629155, 96141769176179125562172215711322, 318039258650792333581481727347444, 1052428477000323358871481851053143, 3483722295148071940134327690805830, 11535317831253359292868402823579507, 38207347830864154536305375515083980, 126587801628186464557480357198559085, 419528009217979573720275236237896417, 1390755683785892862033259848117674774, 4611670612906361418776164768012745653, 15296081009513120554549309437500764824, 50747371356271234761926556868119238498, 168405219545731112554364288982832201851, 558989193462415329625493999178237080626, 1855899670106913269845444317474927546423, 6163199761989091486599405750108261145703, 20471808188252730253305209012013844045216, 68014577424164474931486461475668614678686, 226017132897486482313785408684642017611167, 751228528821566884887025400929475175495820, 2497422446108808789481493034865234440887015, 8304225298346845920034040079844000097625855, 27617949257960572453634177384195377555692288, 91868580681918549990991435834923337673699491, 305649725186484753579669948042728038245882292, 1017092952054919259060371147707157938894201331, 3385128662146733432732965716893157161425815142, 11268495575748944733138124584087087054280266324, 37517275924900806062363173300021942892499461393, 124930847129392818302763649939141795556224243713, 416082622849568526097964338720091330511969411924, 1385988103901435234706475570273478135988166521923, 4617511943290153995888525252387585225192807082142, 15385930480308862008739312762662824092531367200626, 51274965000307280025396615989999357497440689837989, 170903730495686502105057036501035279063272041545834, 569719401123876549106765883713153813889415868065943, 1899470452189871578196668241768272753441549107841410, 6333808775196455664589257750187708401660251943230383, 21123071284136259909038469888950595262519640647268685, 70454342544451967445867781208934442631077877253481078, 235026026088974199171680577807557503801365095549234211, 784116462508129717367948943112182630308912171830076006, 2616378515475911514335529070454642899220772080606204962, 8731220510530124900371916918937528182861005024062334275, 29140885115987861760427406247770786328058746593303970095, 97270907225946924187062292963751348114085595754006368810, 324724241483398152914964764344780153258258425787310003393, 1084169206898973097261256426145847954992759862589795174640, 3620171599239912715912028139478648686336267163412165925288, 12089549553877156823402161133014004555797677976507300126123, 40377471614772962791056393371372109986169401728621344684316, 134869996001774880464574438243175356448048932758006630259157, 450544817038961741000326729494333713688471887071674869178187, 1505241926424578135155516575230297041547401974637729004504946] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {3 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 HH H H H 2+ H H H H H + H H H H + H H H H + HH H H 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 3 4 3 3 2 4 3 2 2 2 2 P(x) x - P(x) x - P(x) x - P(x) x + 2 P(x) x - 2 P(x) x + P(x) - 1 = 0 The sequence a(n) satisfies the linear recurrence 4 3 a(n) = -1/2 (930247885581669792 n - 10322663107020676776 n 2 + 28782519747012638523 n - 774500809137474272 n - 29223193132251896555) 5 a(n - 1)/((n + 1) %1) + 1/2 (1744214785465630860 n 4 3 - 22581790678775186046 n + 90258764382659078595 n 2 - 139383555726759522883 n + 129682008474656493876 n - 51763949175384689936) a(n - 2)/(n (n + 1) %1) + 1/8 ( 5 4 28372560510240928656 n - 405191550651250320216 n 3 2 + 1916896085765740918413 n - 3364763135884791287837 n + 1348587213609382001690 n + 961216645626894958528) a(n - 3)/(n (n + 1) %1 5 4 ) + 1/8 (19535205597215065632 n - 310963523662578278736 n 3 2 + 1718461253639477916423 n - 3383044124201022331267 n - 870305782985304370702 n + 7009774513221800842968) a(n - 4)/(n (n + 1) %1 5 4 ) - 1/4 (9069916884421280472 n - 137797740223869535884 n 3 2 + 705640502355456093507 n - 1524890306939902844397 n + 2244273511342286079808 n - 3772030906748483739428) a(n - 5)/(n (n + 1) 5 4 %1) - 1/8 (14418842226515881776 n - 249653918131753916232 n 3 2 + 1513927935969170682285 n - 3370531874408735356055 n + 134407807673454662556 n + 5367999679875385875524) a(n - 6)/(n (n + 1) %1 5 4 ) + 1/8 (1860495771163339584 n - 24831441699158867616 n 3 2 + 120135904089537607875 n - 478395444985553947489 n + 2626902890169493416892 n - 6946326371525429912260) a(n - 7)/(n (n + 1) 4 3 %1) + 1/2 (697685914186252344 n - 10543208615258328981 n 2 + 54381077040172595405 n - 103830130914911402845 n + 91302411546453955248 5 ) a(n - 8)/(n (n + 1) %1) + 1/4 (930247885581669792 n 4 3 - 19392579991441957248 n + 136923705771093300312 n 2 - 370570087659532389493 n + 298339305195747768543 n - 166118867990930523542) a(n - 9)/(n (n + 1) %1) - 1/4 (n - 10) (246371007278221101 n - 5343210532909953017) (2 n - 13) a(n - 10)/(n (n + 1) %1) 3 2 %1 := 232561971395417448 n - 2638806269604023556 n + 7826372109065447622 n - 4094179133879874103 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 1, a(5) = 4, a(6) = 4, a(7) = 11, a(8) = 23, a(9) = 38, a(10) = 101] Just for fun, a(1000), equals 3016441162058742514359882326046971547696945679864372909651805592564345741498\ 456741656312443287952789618363319701104764714822120718991433054402301448\ 278905237070264697427218637439295350364415541591792520745499252716408012\ 863244007122880947086987501315925344233820015179759644371468447644540115\ 781204974546083819743934919610657523983476715823530434423867829672345570\ 44443109049518881963 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 1, 4, 4, 11, 23, 38, 101, 187, 419, 947, 1949, 4552, 9869, 22106, 50429, 112063, 257174, 583087, 1329699, 3059004, 6999422, 16156301, 37277124, 86168125, 199949880, 463909975, 1079584552, 2515427442, 5868290519, 13716885966, 32090835976, 75190316340, 176379036112, 414169440447, 973713811947, 2291295228426, 5397182852985, 12724878229299, 30026538480590, 70914003572921, 167607851479183, 396450072502494, 938424872965151, 2222840376149161, 5268769250335083, 12496416241287841, 29657051604397195, 70424984074078756, 167328654119131852, 397787402354373622, 946148111116021749, 2251575796586379886, 5360752963171633955, 12769353691191420861, 30430512464030327592, 72550427576471590687, 173043265763080918238, 412902489954747378422, 985626826505780218381, 2353663385405963868139, 5622607467576857685141, 13436550019897707060886, 32121044240767800860084, 76813729279945022484938, 183751561772670560410123, 439705675587739044957657, 1052514226357464783137277, 2520141671773006902240861, 6036001877391457204701565, 14460979709318757403277743, 34655060118440011304867621, 83071675031450337790680456, 199183592836231250706146049, 477711250099641063513511534, 1146003211610373279446785653, 2749868414038254745935450819, 6599956281739131399641131350, 15844215046205972251887688103, 38045077091215406178397495323, 91373848251054330965998632816, 219502156433222986993042388353, 527408221837836851218610636051, 1267488733591608891974115438304, 3046690778229226696908605174525, 7324833005856389087153276299275, 17613685809763839608358337171138, 42362743810051539811592706444917, 101905458871248374124816383036713, 245182019964885501220844539720766, 590005306037655798307007072237549, 1420030671470106853466060430865683, 3418318083242072551729552770792122, 8229977357862844859765056622715974, 19817768726108879117255033179718645, 47728676453991312201141314019742898, 114966460863622966388838550496509597, 276967445725478453841528877782241128, 667345565940930718430977187451833785, 1608185187821197252357749873007314372, 3875996119678157247897692385884762650, 9343108977675632588749576447840022454, 22524706567294607565059480240627698560, 54310698816280265762804113805887609436, 130969167525702137880295030056053776882, 315870528415530843436247685827517069543, 761911408134743618474266776818772577836, 1838036659836399765071923412809960307976, 4434628121028256040638224836444012525008, 10700711026162892866008435949236108789444, 25823763166718300433344275889753056400237, 62327109417544554122958258945995166981413, 150447205007059067462076239448360821173094, 363195189448427347311986079907905142463485, 876887829378595455943102150614959062268521, 2117362293422639358236949678448028980145374, 5113198958865870827882288594787550806101589, 12349114586340582255550593138285060689061346] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {3 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 H H HH + 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 3 4 3 3 2 4 3 2 2 2 2 P(x) x - P(x) x - P(x) x - P(x) x + 2 P(x) x - 2 P(x) x + P(x) - 1 = 0 The sequence a(n) satisfies the linear recurrence 4 3 a(n) = -1/2 (5874851025561633009876 n - 64731653013429926573328 n 2 + 176835919880509137396693 n + 10958571027931798955864 n - 199229214341990060273737) a(n - 1)/((n + 1) %1) + 1/2 ( 5 4 11049714428443373737107 n - 143151874351879736449224 n 3 2 + 574797842926291217942352 n - 902704403284060254550073 n + 861250631448357847012944 n - 348523267101089384579632) a(n - 2)/(n 5 (n + 1) %1) + 1/8 (179320431301691054175576 n 4 3 - 2550856117471435315511694 n + 11986963625406688749301257 n 2 - 20697548515532998795531159 n + 7483885300870486919023318 n + 6743352440770283626268096) a(n - 3)/(n (n + 1) %1) + 1/8 ( 5 4 123017097286313654821956 n - 1938949173544803869665458 n 3 2 + 10510883740100824133888007 n - 19483107321683295769872833 n - 10084570557328212170875442 n + 48391161994624746525686376) a(n - 4)/(n 5 4 (n + 1) %1) - 1/4 (57552530204282912605098 n - 877925356162430767060122 n 3 2 + 4555723611956022196248933 n - 10267652370487209841542243 n + 16097125315266332048887640 n - 25989758720419862798187676) a(n - 5)/(n 5 (n + 1) %1) - 1/8 (90851761024047936601632 n 4 3 - 1560474885222680700419982 n + 9324290058229346360914629 n 2 - 19912449053839088366958817 n - 2623099456141872624471972 n + 37045531577448777219212188) a(n - 6)/(n (n + 1) %1) + 1/8 ( 5 4 12042390807769792687740 n - 169417034585199524176362 n 3 2 + 943537443830393703624855 n - 4233917653518083116775903 n + 20243992078967141413514492 n - 47997900493869401536966940) a(n - 7)/(n 5 4 (n + 1) %1) - 1/2 (8869356262015959636 n - 4789737927503415011664 n 3 2 + 71198000945049989803383 n - 367288736780608832598685 n + 714593345824749360903887 n - 637886490420799217463696) a(n - 8)/(n 5 4 (n + 1) %1) + 1/4 (5883720381823648969512 n - 122474874377346182310600 n 3 2 + 863515207490126569759386 n - 2337682263954604240620089 n + 1916445591707985925625349 n - 1148537598315091468203994) a(n - 9)/(n 3 (n + 1) %1) - 1/4 (n - 10) (2 n - 13) (8869356262015959636 n 2 - 297123434777534647806 n + 3390311431155600570861 n - 36901494092920450771471) a(n - 10)/(n (n + 1) %1) 3 2 %1 := 1470930095455912242378 n - 16638230670308867305332 n + 49080765530600427980466 n - 25127024278070295731933 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 1, a(5) = 4, a(6) = 4, a(7) = 11, a(8) = 23, a(9) = 38, a(10) = 101] Just for fun, a(1000), equals 3016441162058742514359882326046971547696945679864372909651805592564345741498\ 456741656312443287952789618363319701104764714822120718991433054402301448\ 278905237070264697427218637439295350364415541591792520745499252716408012\ 863244007122880947086987501315925344233820015179759644371468447644540115\ 781204974546083819743934919610657523983476715823530434423867829672345570\ 44443109049518881963 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 1, 4, 4, 11, 23, 38, 101, 187, 419, 947, 1949, 4552, 9869, 22106, 50429, 112063, 257174, 583087, 1329699, 3059004, 6999422, 16156301, 37277124, 86168125, 199949880, 463909975, 1079584552, 2515427442, 5868290519, 13716885966, 32090835976, 75190316340, 176379036112, 414169440447, 973713811947, 2291295228426, 5397182852985, 12724878229299, 30026538480590, 70914003572921, 167607851479183, 396450072502494, 938424872965151, 2222840376149161, 5268769250335083, 12496416241287841, 29657051604397195, 70424984074078756, 167328654119131852, 397787402354373622, 946148111116021749, 2251575796586379886, 5360752963171633955, 12769353691191420861, 30430512464030327592, 72550427576471590687, 173043265763080918238, 412902489954747378422, 985626826505780218381, 2353663385405963868139, 5622607467576857685141, 13436550019897707060886, 32121044240767800860084, 76813729279945022484938, 183751561772670560410123, 439705675587739044957657, 1052514226357464783137277, 2520141671773006902240861, 6036001877391457204701565, 14460979709318757403277743, 34655060118440011304867621, 83071675031450337790680456, 199183592836231250706146049, 477711250099641063513511534, 1146003211610373279446785653, 2749868414038254745935450819, 6599956281739131399641131350, 15844215046205972251887688103, 38045077091215406178397495323, 91373848251054330965998632816, 219502156433222986993042388353, 527408221837836851218610636051, 1267488733591608891974115438304, 3046690778229226696908605174525, 7324833005856389087153276299275, 17613685809763839608358337171138, 42362743810051539811592706444917, 101905458871248374124816383036713, 245182019964885501220844539720766, 590005306037655798307007072237549, 1420030671470106853466060430865683, 3418318083242072551729552770792122, 8229977357862844859765056622715974, 19817768726108879117255033179718645, 47728676453991312201141314019742898, 114966460863622966388838550496509597, 276967445725478453841528877782241128, 667345565940930718430977187451833785, 1608185187821197252357749873007314372, 3875996119678157247897692385884762650, 9343108977675632588749576447840022454, 22524706567294607565059480240627698560, 54310698816280265762804113805887609436, 130969167525702137880295030056053776882, 315870528415530843436247685827517069543, 761911408134743618474266776818772577836, 1838036659836399765071923412809960307976, 4434628121028256040638224836444012525008, 10700711026162892866008435949236108789444, 25823763166718300433344275889753056400237, 62327109417544554122958258945995166981413, 150447205007059067462076239448360821173094, 363195189448427347311986079907905142463485, 876887829378595455943102150614959062268521, 2117362293422639358236949678448028980145374, 5113198958865870827882288594787550806101589, 12349114586340582255550593138285060689061346] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {3 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {3 r + 1} To make it crystal clear here is such a path of semi-length 8 8+ HH + HH HH + HH HHH + HH H + HH HH 6+ HH HH + HH HH + HH HH + HH HH + HH HH 4+ HH HH + HH HH + HH HH + HHH HHH + HH HH 2+ HH HH + HH HH + HH HH + HHH HHH + 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 4 7 3 7 4 5 3 6 3 5 4 3 P(x) x - P(x) x - 2 P(x) x + P(x) x + 5 P(x) x + P(x) x 3 4 2 5 3 3 2 4 3 2 - 3 P(x) x - P(x) x - 4 P(x) x + 5 P(x) x + 3 P(x) x 2 3 2 2 3 2 2 + 4 P(x) x - 10 P(x) x - P(x) + 8 P(x) x + 5 P(x) - 8 P(x) + 4 = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 1, 3, 3, 6, 12, 15, 36, 58, 100, 218, 349, 721, 1394, 2492, 5267, 9765, 19277, 39248, 74609, 153190, 303758, 602144, 1235837, 2452224, 4992928, 10159685, 20460117, 42023807, 85357758, 174337814, 358252672, 731333732, 1505529743, 3094461165, 6360356560, 13135878164, 27063304667, 55922408343, 115689768751, 239203323659, 495901840181, 1027816516434, 2132364545362, 4429989146396, 9202566709836, 19142366031839, 39838228837166, 82947240771563, 172879021828164, 360415388064160, 751929745794485, 1569704041453709, 3278080727250095, 6850435165004786, 14321687990803169, 29955507191775341, 62688834991462250, 131238969920260657, 274881738770908093, 575979259844837521, 1207346270237452165, 2531880853038448666, 5311370261630073860, 11146360468383596734, 23400108371686480824, 49141095094077609826, 103234204442967161168, 216940426042669910399, 456029809654063589944, 958919675329918241879, 2016959370332736765010, 4243650010393882663803, 8931085578888851959451, 18801241595452504581452, 39590062822386033283443, 83386839984810312971197, 175678587783939344072280, 370209581140725059496830, 780333073049579221481723, 1645184656490609633394590, 3469351391017765122059199, 7317766327520728717904067, 15438445978291529038012101, 32577708787020011914341692, 68758703329378320588977311, 145151933287064858853209541, 306481151629023264497583462, 647245247564046966802014618, 1367149485644161597304736817, 2888307558507578154074583194, 6103085755413112704707662009, 12898294080723537398109554481, 27264046905405167278566537311, 57639732451159153330670864912, 121878086084336507295011541789, 257750721618571435724313286741, 545184170987082877893328904060, 1153331890308303284080937993629, 2440235347227757769962158826277, 5163856107570410693109686363022, 10928996892600922310122541288829, 23133905624757063655837558036869, 48975502314403269378206204706528, 103697659712179334304337729645049, 219592738012133971642780525016721, 465076994686098917660826842596073, 985118612447528493604535984890917, 2086930205945067417047882982520269, 4421626415470706800287302054153556, 9369359242514090938202972364719067, 19855942129171212681639526446331686, 42084573467714041727556216414674183, 89208506653113763534992087145824315, 189120945224284023941571490697112521, 400979475079869009979075856375775539, 850262381322503161459503159842797279, 1803147580601220425358778066247654846] ------------------------------------------------------------ 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 , {3 r + 1} 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 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 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 0.5+ HH H H 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 2 P(x) x + P(x) x - P(x) - x + 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (2 n - 1) a(n - 1) 2 (n - 2) a(n - 2) (n - 5) a(n - 4) a(n) = -------------------- - ------------------ - ---------------- n + 1 n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 2, a(4) = 5] Just for fun, a(1000), equals 2686283994387753850848760555248012257933817935904451572765706895563763740381\ 718694055526880288966855978797785801414602527004815548224715317372110874\ 013487648559748246035759330642356732493168453509177146786979292003111783\ 532200636814316998608949886964676082308774362805604086260920434702324154\ 244411119695705771551729164098154793768298930590140795477554053112104692\ 279227211020001866460127527686246236733772182433391263031110633227460685\ 180038272658596281963975681046783417098410171514286074364425105253765031\ 03954688061082969 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089, 5849291140802, 18835364275167, 60747282711897, 196209341584503, 634620668408980, 2055301318326151, 6664561092573868, 21635802592167335, 70315790541767705, 228763226951906273, 744989334333881109, 2428416011845914189, 7922925175749803208, 25871350205338922449, 84548638086169215253, 276523586339621851443, 905067358391568367756, 2964414005765102642217, 9716122917030183985702, 31866260234545750501783, 104578319350636185890173, 343410737620591041944771, 1128333693246416457543548, 3709395336144887467658679, 12201170825008543566965785, 40153569371806383011616029, 132209595195367233134941852, 435522201387246440874595919, 1435353468260807857367807813, 4732621558778109618932633975, 15611063853863262075016989991, 51516317628277001701799267233, 170071992533299423338239042160, 561682422522985169662090986775, 1855724700596245211998540595793, 6133322935669658149371136495455, 20278358872358286976146102397392, 67068687477884370884796803082167, 221897489474613208019309511636122, 734389218349531025290000123705699, 2431293818147748581262845839752687, 8051595536105287352734075132773677, 26672029999610795243436972691504473, 88380453797322310021174981683475105, 292940207589793109162794879039337332, 971227674567913288312984611879778357, 3220914929120468556742904919895070879, 10684410396606759135773144669488019171, 35451290346758114207377247430618473674, 117657848189459877792437732114712963353, 390583973916684217071129710195404878775, 1296910476644497940219950318296690465797, 4307300091882178216753961432633333599280, 14308608426263638766705803261905582899513, 47542769235911744678181252463654770633470, 158002555473322007382298947208973402932481, 525211395924080402573239992244833157884653, 1746193917287241904594467633935759265391195, 5806802852238037130552547044978765656738840, 19313723959613726533600137304351377458066433, 64250631423957977537357258450727960118007203, 213781144504566203588678512207804700572182801, 711443226868434505480701199664429900648319039, 2368035710091814173672594569185999222531613811, 7883366913602211300405158867193929892854451182, 26248780349151861329225048715934855838219195069, 87413571204492012240400476639119852663724782320, 291151775720175707795200688780949534955745168211, 969905481051866708608511231553386805476197109999, 3231523839388718761182049682114107089204640560219, 10768418537018708012850787510275238867338560118484, 35889034519998418016657303227336533404909322637363, 119628765495379222079660420511035921565831351707845, 398815670628190047001708847212118534826143826520109, 1329751051065995029089902358055118939552133239775467, 4434338323006584086392589508419435648218702835388973, 14789262508939804244449212138762886860859388704038302, 49331271260315707536829311319983847368558236606212393, 164571683544522231725812796598623061170287218295753133, 549090436419155518196268365304625126507547076280841795, 1832262052967781796967580127342460268911859908776128956, 6114841995054213386036387848482885283640232943456129313, 20409664605457736860055489328833258145197741569241635820, 68130022109959062426634886715980561786026849160702398715, 227453334257451228727902471381028805144172830033303634583, 759444965415574944346291661801067801734501436802485171247, 2536002392340939618650771713332800731343507300822370750648, 8469377954637244107490132993535355869461410813095134200835, 28287922060895805967654232238358105430371723752114044558193, 94492524387001917673518044871803246461879531029385285574841, 315674821037186860535752291251158357240422954313668238919030, 1054697109385616394155189845735963327858930087566054135326759] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {3 r + 1} 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+ H HH HH + HHH H H + HH H HH HH + H HH H H 1+ HH HH 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 3 2 2 3 3 2 2 2 2 2 P(x) x + P(x) x + P(x) x + P(x) x - 2 P(x) x - 2 P(x) x - 2 P(x) + 4 P(x) + x - 2 = 0 The sequence a(n) satisfies the linear recurrence a(n) = - 4 3 2 (458010 n - 5679261 n + 22635962 n - 24419413 n - 11255034) a(n - 1) 1/2 ----------------------------------------------------------------------- (n + 1) (n - 1) %1 4 3 2 + 1/4 (3435075 n - 35666574 n + 119420583 n - 170869112 n + 138459236) a(n - 2)/((n + 1) (n - 1) %1) + 1/4 4 3 2 (9618210 n - 132253803 n + 651801912 n - 1366643717 n + 1088610838) a(n - 3)/((n + 1) (n - 1) %1) + 1/4 4 3 2 (3435075 n - 77352678 n + 667604550 n - 2499725785 n + 3390545422) a(n - 4)/((n + 1) (n - 1) %1) - 1/4 4 3 2 (2748060 n - 28515483 n + 25051701 n + 482724946 n - 1199747672) a(n - 5)/((n + 1) (n - 1) %1) - 4 3 2 (229005 n - 6419391 n + 64092850 n - 272982607 n + 420128706) a(n - 6) ------------------------------------------------------------------------- (n + 1) (n - 1) %1 3 2 (n - 8) (458010 n - 6137271 n + 29689253 n - 49702490) a(n - 7) - 1/2 ----------------------------------------------------------------- (n + 1) (n - 1) %1 (2 n - 13) (272203 n - 1168754) (n - 9) a(n - 8) + 3/2 ------------------------------------------------ (n + 1) (n - 1) %1 2 %1 := 229005 n - 1908519 n + 3751678 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4, a(6) = 7, a(7) = 15, a(8) = 30] Just for fun, a(1000), equals 4610323063716418082852692560734159481962082191457914432964591024948291166652\ 048126279768991300383628170158881297854634991746096719630741213956508508\ 812275686206353417074955778244271668372698071009250438327415816377821417\ 675333864281124302277495705149586556082902192825467502876658491694969638\ 375805837500806694458938093475622732901450843335904523674211165915121096\ 49984621765219412864 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 2, 4, 7, 15, 30, 62, 134, 282, 617, 1347, 2957, 6591, 14655, 32923, 74218, 167798, 381638, 869440, 1988698, 4561712, 10486775, 24178857, 55852825, 129305173, 299946848, 696948546, 1622331595, 3782088489, 8830235779, 20645478585, 48331649127, 113288466051, 265852512947, 624561682711, 1468815547690, 3457698062422, 8147403697810, 19215013373676, 45355877479326, 107147463726934, 253319153215168, 599346976512124, 1419051762659414, 3362131270397964, 7971053089776619, 18909908400663849, 44887484162036543, 106613680033775751, 253362753027401724, 602428895310698806, 1433155589332500079, 3411122771231771215, 8122881787950813302, 19351934808940846194, 46124667722724340308, 109984157496361023928, 262366762979344821475, 626128367635332798241, 1494817511585095693929, 3570079107050219220309, 8529572038501756367784, 20385975444872189300562, 48740046531935532918615, 116569815525144073563531, 278886661992969279373936, 667431600401765912060556, 1597788410916040494166281, 3826145745187890642750035, 9164945903124429388359491, 21959427739962066172868329, 52629778943716325851551583, 126170643987992937089558207, 302550792911841064351639391, 725685668736503991087875059, 1741030015527473487988824754, 4178002768223059065086617038, 10028438934371508115220553882, 24076734318850944418049663084, 57817464497129645702652457058, 138872223096012792905819947650, 333629440713746677426531237880, 801685097971624213369586542884, 1926777752662186441873808949890, 4631757157542627148187120415258, 11136387419845749205167937989336, 26780913306863979245213789625240, 64415015116961838009839492603128, 154962906424215685690969777259792, 372859828540218321008020820796686, 897302723860369151593518739573682, 2159764128731168599645183975810130, 5199314134565648880174710321939652, 12518626585416916635773944258594353, 30146489739182607285518406020196527, 72608061256880199987066608730770339, 174903937830571590123089402928647771, 421385572659579334556362691800844110, 1015368710376103400453603822268634272, 2446981453454761901270439238682264441, 5897923732026545088184337745173299869, 14217656576002540835022908440765261600, 34278052041224516913639315733845963612, 82653715374899499375346166228332605576, 199326791685054487619807794931059515852, 480756283661169831146874616306029749591, 1159682850333402621982617732157741482257, 2797740801778336757309584509610981771357, 6750387835013508479274994629298144195979, 16289285594917841071953214602553714462049, 39312122733814535247148922255466414204037, 94885795477785824171264057519054619401482, 229047359796439948855864778244717238962006, 552965336764813472750927586843767430956676, 1335113629496993335616000101360984259872790, 3223928848688203915992238989773632208090932, 7785719968946204376051055706557578844599510, 18804312314876702095710217058339372796482257] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {3 r + 1} To make it crystal clear here is such a path of semi-length 8 8+ HH + HH HH + HH HHH + HH H + HH HH 6+ HH HH + HH HH + HH HH + HH HH + HH HH 4+ HH HH + HH HH + HH HH + HHH HHH + HH HH 2+ HH HH + HH HH + HH HH + HHH HHH + 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 3 2 2 3 3 2 2 2 2 2 P(x) x + P(x) x + P(x) x + P(x) x - 2 P(x) x - 2 P(x) x - 2 P(x) + 4 P(x) + x - 2 = 0 The sequence a(n) satisfies the linear recurrence a(n) = -1/2 4 3 2 (45983826 n - 532151943 n + 1917318700 n - 1893738959 n - 815266704) a(n - 1)/((n + 1) (n - 1) %1) + 1/4 ( 4 3 2 251785269 n - 2565197892 n + 8573128325 n - 12990255118 n + 10564104656) 4 3 a(n - 2)/((n + 1) (n - 1) %1) + 1/4 (833369688 n - 11187251055 n 2 + 53310751944 n - 107753368345 n + 81547511528) a(n - 3)/((n + 1) (n - 1) 4 3 2 %1) + 1/4 (477169353 n - 8824339548 n + 63244788120 n - 204979999317 n + 250512623032) a(n - 4)/((n + 1) (n - 1) %1) - 1/4 ( 4 3 2 143612298 n - 1210336299 n - 2553997995 n + 42638018468 n - 88032540232) a(n - 5)/((n + 1) (n - 1) %1) - 4 3 2 (32791221 n - 735887856 n + 6133782772 n - 22576511898 n + 31090947846) a(n - 6)/((n + 1) (n - 1) %1) - 1/2 3 2 (n - 8) (45983826 n - 578135769 n + 2487795823 n - 3686511430) a(n - 7) ------------------------------------------------------------------------- (n + 1) (n - 1) %1 2 (2 n - 13) (n - 9) (4899654 n - 80844291 n + 258734392) a(n - 8) - 1/2 ----------------------------------------------------------------- (n + 1) (n - 1) %1 2 %1 := 18092259 n - 146787627 n + 271755568 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4, a(6) = 7, a(7) = 15, a(8) = 30] Just for fun, a(1000), equals 4610323063716418082852692560734159481962082191457914432964591024948291166652\ 048126279768991300383628170158881297854634991746096719630741213956508508\ 812275686206353417074955778244271668372698071009250438327415816377821417\ 675333864281124302277495705149586556082902192825467502876658491694969638\ 375805837500806694458938093475622732901450843335904523674211165915121096\ 49984621765219412864 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 2, 4, 7, 15, 30, 62, 134, 282, 617, 1347, 2957, 6591, 14655, 32923, 74218, 167798, 381638, 869440, 1988698, 4561712, 10486775, 24178857, 55852825, 129305173, 299946848, 696948546, 1622331595, 3782088489, 8830235779, 20645478585, 48331649127, 113288466051, 265852512947, 624561682711, 1468815547690, 3457698062422, 8147403697810, 19215013373676, 45355877479326, 107147463726934, 253319153215168, 599346976512124, 1419051762659414, 3362131270397964, 7971053089776619, 18909908400663849, 44887484162036543, 106613680033775751, 253362753027401724, 602428895310698806, 1433155589332500079, 3411122771231771215, 8122881787950813302, 19351934808940846194, 46124667722724340308, 109984157496361023928, 262366762979344821475, 626128367635332798241, 1494817511585095693929, 3570079107050219220309, 8529572038501756367784, 20385975444872189300562, 48740046531935532918615, 116569815525144073563531, 278886661992969279373936, 667431600401765912060556, 1597788410916040494166281, 3826145745187890642750035, 9164945903124429388359491, 21959427739962066172868329, 52629778943716325851551583, 126170643987992937089558207, 302550792911841064351639391, 725685668736503991087875059, 1741030015527473487988824754, 4178002768223059065086617038, 10028438934371508115220553882, 24076734318850944418049663084, 57817464497129645702652457058, 138872223096012792905819947650, 333629440713746677426531237880, 801685097971624213369586542884, 1926777752662186441873808949890, 4631757157542627148187120415258, 11136387419845749205167937989336, 26780913306863979245213789625240, 64415015116961838009839492603128, 154962906424215685690969777259792, 372859828540218321008020820796686, 897302723860369151593518739573682, 2159764128731168599645183975810130, 5199314134565648880174710321939652, 12518626585416916635773944258594353, 30146489739182607285518406020196527, 72608061256880199987066608730770339, 174903937830571590123089402928647771, 421385572659579334556362691800844110, 1015368710376103400453603822268634272, 2446981453454761901270439238682264441, 5897923732026545088184337745173299869, 14217656576002540835022908440765261600, 34278052041224516913639315733845963612, 82653715374899499375346166228332605576, 199326791685054487619807794931059515852, 480756283661169831146874616306029749591, 1159682850333402621982617732157741482257, 2797740801778336757309584509610981771357, 6750387835013508479274994629298144195979, 16289285594917841071953214602553714462049, 39312122733814535247148922255466414204037, 94885795477785824171264057519054619401482, 229047359796439948855864778244717238962006, 552965336764813472750927586843767430956676, 1335113629496993335616000101360984259872790, 3223928848688203915992238989773632208090932, 7785719968946204376051055706557578844599510, 18804312314876702095710217058339372796482257] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {3 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {3 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 + 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 2+ H H H H H H + H H H H 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 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 2 2 3 2 2 2 2 2 1 - P(x) x + 6 P(x) x + 8 P(x) x + 2 x + 2 P(x) x - 8 P(x) x 4 8 3 9 4 7 3 8 2 9 4 6 + P(x) x - P(x) x + 2 P(x) x + 5 P(x) x + 2 P(x) x + 2 P(x) x 3 7 3 4 3 10 2 8 4 5 3 6 + 12 P(x) x + 2 x + x - P(x) x + 6 P(x) x + P(x) x + 7 P(x) x 2 7 8 4 4 3 5 2 6 7 + 6 P(x) x - P(x) x + P(x) x - 5 P(x) x - 2 P(x) x - P(x) x 3 4 2 5 6 3 3 2 4 - 8 P(x) x - 10 P(x) x + 5 P(x) x - 3 P(x) x - 6 P(x) x 5 4 3 + 12 P(x) x + 7 P(x) x - 5 P(x) x - 3 P(x) x - P(x) + x = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 1, 4, 3, 9, 17, 21, 62, 89, 180, 395, 623, 1436, 2664, 5041, 10937, 20008, 41667, 84100, 162655, 341877, 673452, 1366992, 2815962, 5613598, 11604636, 23596603, 47995024, 99188268, 201863004, 415853757, 856384354, 1756106149, 3633901774, 7483064293, 15454305893, 32007173618, 66115166135, 137121306589, 284234238535, 589383671573, 1224973829203, 2543855067983, 5291124789231, 11012996285100, 22923134758560, 47780117194278, 99600369960791, 207762709335420, 433728832504700, 905621077192191, 1892428395782387, 3956103823466661, 8273533418732805, 17313513606053444, 36241907467782917, 75902092299946114, 159032487450639972, 333321934089208813, 698945636366225255, 1466120419357701515, 3076493039915806667, 6458162940523442210, 13561166702102394773, 28486629656629893322, 59858286025624208598, 125817305688097212611, 264543400196905469281, 556387816910255449715, 1170540415901056154252, 2463311348906808601202, 5185235304399864140777, 10917840334753602979865, 22994121075674796259383, 48440303588561458149256, 102071778029518862759411, 215133389734657910624789, 453537235940881419962956, 956351773010486928328269, 2017061195983646580603734, 4255161583276790987351668, 8978529225597278185257050, 18948940422286552228304134, 39999377395039197248815682, 84451539843325756097198681, 178339101609350918614876166, 376676039713798090631370900, 795737909481417095629936859, 1681323052674185320024116895, 3553115885971424461974376317, 7510056547682305955155183656, 15876362880956386338292613607, 33568441699860480711510787301, 70987571980518674086982064276, 150142235941415603202275464581, 317608036943795863806677454097, 671965206442683301305541770286, 1421894600591232965612370645061, 3009207281803032600234612344345, 6369415853128792162646508700951, 13483687814889182665699401119609, 28548165112664777056752432604345, 60451483801537204428769099923989, 128024735506030505699223439303660, 271167652199187821364788545100096, 574431020291105696860292106371522, 1217006467719284225743733580085789, 2578706296913804132834707630859989, 5464669500299236606014875736103623, 11581851898251071078567259456109898, 24549535214900703518938567617674884, 52042579319874387207812999649343238, 110337654954503766297170329824110401, 233957641508109530669762473169987140, 496133375507203012052956759812068849, 1052220036759389406424198961885301924, 2231828514594519436852563309001575885, 4734350865188012728701046365200449426] ------------------------------------------------------------ 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 , {3 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {3 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 H H HH + 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 2 2 P(x) x + P(x) x - P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence (2 n - 1) a(n - 1) (n - 2) a(n - 2) (2 n - 7) a(n - 3) a(n) = ------------------ + ---------------- + ------------------ n + 1 n + 1 n + 1 (n - 5) a(n - 4) - ---------------- n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2] Just for fun, a(1000), equals 1258976834224262773199644936372839877301103060006870706162324567937209163404\ 664302285780840930405187497908781943435725250693212008816722364247013884\ 666083868760309087497764707542210251550367470907064283210333730955232698\ 389440175341142704919913139331694533974031860259334845579975521445364654\ 700207290194856330574815120730458306294903984090244990972375467298717489\ 01445379751297218627473874798563437753301835209165 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 2, 4, 8, 17, 37, 82, 185, 423, 978, 2283, 5373, 12735, 30372, 72832, 175502, 424748, 1032004, 2516347, 6155441, 15101701, 37150472, 91618049, 226460893, 560954047, 1392251012, 3461824644, 8622571758, 21511212261, 53745962199, 134474581374, 336908488839, 845139060165, 2122553644686, 5336735929371, 13432403613621, 33843022209066, 85349327734485, 215440028338359, 544288586926914, 1376230297675914, 3482537223611046, 8819175375714063, 22349794473772659, 56678600914995057, 143830921235537742, 365225623668676437, 927972354829010775, 2359192024476568203, 6001174121892988758, 15273713134056377698, 38893747432145085266, 99090832134641995427, 252579381177903040849, 644118340220292169786, 1643348924746923013481, 4194532932723720267271, 10710773165730370402070, 27361217667381195152609, 69923263927774760117419, 178761583832906815958299, 457180542019634361749654, 1169653910683020997823700, 2993493968182857335738916, 7663836950023084292126586, 19627124209913879819201256, 50281185027971273570344779, 128851301008215990676245297, 330295607482296149639113771, 846922848867278127081934118, 2172243398314031502060434813, 5573055540747246795936497203, 14301951559375317288722742625, 36712267090479571354186761752, 94262318866766131085885820862, 242087967735412291153757221292, 621890217530867044998372625244, 1597927417599990976164331285618, 4106772441264045401019924649921, 10557037252659735639822884541089, 27144318295978988020876731613899, 69808615378820015816460193046634, 179568484819409906464233459965565, 461998012612770916903282585499931, 1188877068859680412470053314034196, 3059980617900905437254279674385261, 7877408686568953921404087246339411, 20282861001228149602530202549462410, 52234134723235412099021791134645474, 134541797507827311283829108795938674, 346605946314513254492433135097630809, 893077485129793636878895057273178901, 2301521609537728551186835553085928773, 5932151623905973421624468114595077244, 15292526112023196667544094397358322057, 39428894200253097844359818441341768857, 101675651191856047918093722573856681533, 262231577763896699071580185616362344474, 676421455498354043694557131153096948242, 1745070036795404191515676477125772132266, 4502671102948126616280146347910232986991, 11619522365904160254086750853999996193257, 29989267641483567746124647302471464623364, 77410853278458837325716535951115639407503, 199845865999157029828297153922576763209097, 515994107988232434150265659196576131793842, 1332445775476334218476042448014555471425367, 3441189354555212307826207610982518728843605, 8888343824153407839499893993501731400851013, 22960715623990327053314884809239717289910938, 59320030743640344359639159629624808652870468, 153273751949431824265963271978491026076658628, 396080814085725989138698666331011334921428590, 1023643104778581902866325330178218535617989992, 2645825722733062522533035808645683954790135357, 6839447205478408814272817631837320918132045127, 17681824513801923840994437263886860582120444673, 45717101366879162702499445595617460969722316454] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {3 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {3 r + 1} 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+ H HH HH + HHH H H + HH H HH HH + H HH H H 1+ HH HH 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 3 3 2 4 2 2 2 P(x) x + P(x) x - P(x) x + 2 P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 4 3 2 a(n) = -1/2 (106965060956 n + 328551487142 n - 4633602560261 n + 2856359133481 n + 2521415347218) a(n - 1)/((2 n + 3) (n + 1) %1) + 3 ( 4 3 2 141738153856 n - 544744508742 n - 117364594423 n + 524735223558 n 4 - 42104852007) a(n - 2)/((2 n + 3) (n + 1) %1) + 1/2 (4019996420284 n 3 2 - 19974179532374 n + 15771733952459 n + 34977005747993 n 4 - 35525879184354) a(n - 3)/((2 n + 3) (n + 1) %1) + 3 (100010442376 n 3 2 + 10642249470 n - 6578873747558 n + 29449440168443 n - 37247078748195) 4 3 a(n - 4)/((2 n + 3) (n + 1) %1) - 1/2 (190420483916 n - 2399624452594 n 2 + 12927849453421 n - 44075370480401 n + 72795145872858) a(n - 5)/( (2 n + 3) (n + 1) %1) - (n - 7) 3 2 (276521689132 n - 670397647462 n - 563728299389 n + 1173466046400) a(n - 6)/((2 n + 3) (n + 1) %1) 2 2086385574 (2 n - 7) (n - 8) (4 n - 66 n + 305) a(n - 7) + --------------------------------------------------------- (2 n + 3) (n + 1) %1 2 %1 := 140347230140 n - 446056957494 n + 140078630401 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 1, a(5) = 3, a(6) = 4, a(7) = 6] Just for fun, a(1000), equals 4857237495456591247290889799209830276426786984979173880434555418599624793882\ 774787850616938566365637479130778959106826928668396376799025864120902357\ 524210367950453817235840726506390940184925753604869026396636972037610748\ 856777730456963920461804780475070322595928840912531881811739520526132246\ 16478729761796466201982027153600496 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 1, 3, 4, 6, 15, 22, 41, 90, 146, 296, 605, 1071, 2220, 4404, 8303, 17195, 33925, 66565, 137020, 271989, 546142, 1119141, 2243396, 4561879, 9333933, 18889965, 38677445, 79210043, 161567501, 332160042, 681855618, 1399146498, 2884621820, 5938929047, 12240875038, 25296348896, 52235851299, 108026901172, 223721928937, 463245353038, 960543184138, 1993284988300, 4137360722781, 8597381407418, 17874708041971, 37179633674881, 77401374987998, 161205337838564, 335920412262282, 700462639167634, 1461193927041706, 3049692460831907, 6368493856007509, 13304148171859417, 27806499506928579, 58143262401191199, 121623384053016241, 254520439421297525, 532839929065405326, 1115906800356559256, 2337904012008738955, 4899779169639813456, 10272445163714622275, 21543741233250437189, 45196666117863362453, 94848111118975891110, 199106883003592862760, 418091273500715741370, 878177874807873967370, 1845087889500258384704, 3877657833799005785536, 8151520707718590595399, 17140394887243603242817, 36050592228373914943092, 75842345945857869642631, 159593604742998446686113, 335908413838588571555524, 707173592791606009176790, 1489114207405833742355419, 3136350583207045992996987, 6607144542541310034222149, 13921727836716923614241141, 29340038231247628296341720, 61846403589446946062544405, 130392421006416847838704986, 274961964674781045262264881, 579927132705094698969873092, 1223356224287678742685853207, 2581127911655188222141650349, 5446801073619735163083762077, 11496013925632586299279051293, 24267516167964246276884982190, 51235870796829974846422323916, 108191268700346877239702764543, 228495796938575230850712386473, 482648255270420050683023939857, 1019643773669030654564483866971, 2154418800355701008770733152052, 4552756843002836317157392087474, 9622329951478161354253076477308, 20339783267335678230849887801966, 43000304852567094051454667722352, 90919027219072161515013913854258, 192262673250677844613363405294660, 406622185669753685850262730625400, 860086328058471633153115850476418, 1819478390575739483110907431468810, 3849503124428944918282820842535743, 8145437735226519656355610037717643, 17237538113668707793866745981445823, 36482636678271142447880935953755257, 77222969189614909309103051692832831, 163476460252923373972946927393238543, 346107955247186653876780189235941961, 732849440656484758443470646021046294, 1551900875809770990450667231834443936, 3286687931181428521468817497124832957] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {3 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {3 r + 1} To make it crystal clear here is such a path of semi-length 8 6+ H + HHHH + H H 5+ HH HH H + HH H H HH + H HH HH H + HH H H HH 4+ H HH HH H + H HH HH H + HH HH H HH 3+ H H H + HH HH + HH HH 2+ 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 3 3 2 4 2 2 2 P(x) x + P(x) x - P(x) x + 2 P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 4 3 2 a(n) = -1/2 (106965060956 n + 328551487142 n - 4633602560261 n + 2856359133481 n + 2521415347218) a(n - 1)/((2 n + 3) (n + 1) %1) + 3 ( 4 3 2 141738153856 n - 544744508742 n - 117364594423 n + 524735223558 n 4 - 42104852007) a(n - 2)/((2 n + 3) (n + 1) %1) + 1/2 (4019996420284 n 3 2 - 19974179532374 n + 15771733952459 n + 34977005747993 n 4 - 35525879184354) a(n - 3)/((2 n + 3) (n + 1) %1) + 3 (100010442376 n 3 2 + 10642249470 n - 6578873747558 n + 29449440168443 n - 37247078748195) 4 3 a(n - 4)/((2 n + 3) (n + 1) %1) - 1/2 (190420483916 n - 2399624452594 n 2 + 12927849453421 n - 44075370480401 n + 72795145872858) a(n - 5)/( (2 n + 3) (n + 1) %1) - (n - 7) 3 2 (276521689132 n - 670397647462 n - 563728299389 n + 1173466046400) a(n - 6)/((2 n + 3) (n + 1) %1) 2 2086385574 (2 n - 7) (n - 8) (4 n - 66 n + 305) a(n - 7) + --------------------------------------------------------- (2 n + 3) (n + 1) %1 2 %1 := 140347230140 n - 446056957494 n + 140078630401 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 1, a(5) = 3, a(6) = 4, a(7) = 6] Just for fun, a(1000), equals 4857237495456591247290889799209830276426786984979173880434555418599624793882\ 774787850616938566365637479130778959106826928668396376799025864120902357\ 524210367950453817235840726506390940184925753604869026396636972037610748\ 856777730456963920461804780475070322595928840912531881811739520526132246\ 16478729761796466201982027153600496 For the sake of the OEIS here are the first, 120, terms. [1, 0, 1, 1, 1, 3, 4, 6, 15, 22, 41, 90, 146, 296, 605, 1071, 2220, 4404, 8303, 17195, 33925, 66565, 137020, 271989, 546142, 1119141, 2243396, 4561879, 9333933, 18889965, 38677445, 79210043, 161567501, 332160042, 681855618, 1399146498, 2884621820, 5938929047, 12240875038, 25296348896, 52235851299, 108026901172, 223721928937, 463245353038, 960543184138, 1993284988300, 4137360722781, 8597381407418, 17874708041971, 37179633674881, 77401374987998, 161205337838564, 335920412262282, 700462639167634, 1461193927041706, 3049692460831907, 6368493856007509, 13304148171859417, 27806499506928579, 58143262401191199, 121623384053016241, 254520439421297525, 532839929065405326, 1115906800356559256, 2337904012008738955, 4899779169639813456, 10272445163714622275, 21543741233250437189, 45196666117863362453, 94848111118975891110, 199106883003592862760, 418091273500715741370, 878177874807873967370, 1845087889500258384704, 3877657833799005785536, 8151520707718590595399, 17140394887243603242817, 36050592228373914943092, 75842345945857869642631, 159593604742998446686113, 335908413838588571555524, 707173592791606009176790, 1489114207405833742355419, 3136350583207045992996987, 6607144542541310034222149, 13921727836716923614241141, 29340038231247628296341720, 61846403589446946062544405, 130392421006416847838704986, 274961964674781045262264881, 579927132705094698969873092, 1223356224287678742685853207, 2581127911655188222141650349, 5446801073619735163083762077, 11496013925632586299279051293, 24267516167964246276884982190, 51235870796829974846422323916, 108191268700346877239702764543, 228495796938575230850712386473, 482648255270420050683023939857, 1019643773669030654564483866971, 2154418800355701008770733152052, 4552756843002836317157392087474, 9622329951478161354253076477308, 20339783267335678230849887801966, 43000304852567094051454667722352, 90919027219072161515013913854258, 192262673250677844613363405294660, 406622185669753685850262730625400, 860086328058471633153115850476418, 1819478390575739483110907431468810, 3849503124428944918282820842535743, 8145437735226519656355610037717643, 17237538113668707793866745981445823, 36482636678271142447880935953755257, 77222969189614909309103051692832831, 163476460252923373972946927393238543, 346107955247186653876780189235941961, 732849440656484758443470646021046294, 1551900875809770990450667231834443936, 3286687931181428521468817497124832957] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {3 r + 1} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {3 r + 1} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {3 r + 1} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {3 r + 1} To make it crystal clear here is such a path of semi-length 8 6+ H + HHHH + H H 5+ HH HH H + HH H H HH + H HH HH H + HH H H HH 4+ H HH HH H + H HH HH H + HH HH H HH 3+ H H H + HH HH + HH HH 2+ 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 3 6 3 4 4 5 3 6 2 4 3 -x P(x) + 5 x P(x) + x P(x) + x P(x) - x P(x) - 4 x P(x) 5 2 2 4 3 2 3 2 2 3 + 4 x P(x) + 5 P(x) x - 7 x P(x) - x P(x) - 2 P(x) x + 8 x P(x) 2 2 2 + 5 x P(x) + 2 P(x) x + P(x) - 8 x P(x) - 2 P(x) + 4 x + 1 = 0 For the sake of the OEIS are the first , 120, terms [1, 0, 1, 1, 1, 3, 3, 6, 12, 15, 35, 58, 95, 206, 334, 640, 1264, 2177, 4374, 8217, 15162, 30275, 56463, 108880, 213718, 404583, 794653, 1544566, 2979451, 5874545, 11414950, 22325982, 43989270, 85921132, 169345781, 333623077, 655837963, 1297353778, 2560081603, 5059584011, 10028296530, 19844296963, 39366704922, 78155048712, 155124568215, 308521354281, 613615306952, 1221211943671, 2433457134974, 4849197885722, 9672144753885, 19304734013124, 38541089676660, 77011049918455, 153940985782844, 307860733257746, 616078877861346, 1233283558166988, 2470091109651973, 4949614521389404, 9921582267677485, 19897562872890742, 39919368513685689, 80117295278390271, 160860745066219799, 323086194251893922, 649147715071083637, 1304737910167783398, 2623242707571418272, 5275945031117756057, 10614443919871535458, 21361085350629506945, 43001395135165717906, 86589256205544959115, 174408395129388249425, 351391329269819121397, 708154156563228878012, 1427506834550025613553, 2878313406193573226555, 5805018849053114682654, 11710467897105744547012, 23629018854392481008665, 47688749390900640506105, 96268281141948007053392, 194376691467345643906073, 392552168244070928475302, 792940320832214492522636, 1602031733021040876386921, 3237335727264747188243532, 6543168325605293835628037, 13227273709855605376883572, 26744401155384253185069481, 54084609134404711608561081, 109393435012677749348043494, 221301283141434787721689484, 447764868223063832054115024, 906124978322690956970928967, 1833988605837100317623713739, 3712565771223125903818907863, 7516563522345594538700503627, 15220563842305646808483967331, 30825284756996796688091532962, 62437733749402206049222785436, 126488071795511115961102420340, 256279132316505804978071391337, 519322294345799988580705209996, 1052493919868323920071054005693, 2133339831093141415256305366518, 4324712266245130360550976968999, 8768192674541949941134000361387, 17779421659769502508479596681087, 36056108960117026035762114629029, 73129535097532287235298885019305, 148340096434975453125811174671133, 300936715823833663046917752445152, 610578896467872253652428453437932, 1238960689230340501084779426735873, 2514325774967111930565565648990551, 5103087698182372309537278936448622, 10358364232329324914441938880009995, 21027866327577679527605908877970836] This concludes this exciting paper with its, 16, theorems that took, 4401.499, to generate. --------------------------------------------------