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 (i) the heights of the peaks are not allowed to take certain values (ii) the heights of the valleys are not allowed to take certain values (iii) the upward runs can't have certain values (iv) the downward runs can't have certain values All the above restictions will be subsets of, {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 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 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions No downward-run can belong to, {1} To make it crystal clear here is such a path of semi-length 8 5+ H + HH H + H HH + HH H 4+ H H H H + H HH HHH HHH + HH H HH H H HH + H HH H HH HH H 3+ H H H H H + HH H H HH + H H HH 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 sequence a(n) satisfies the linear recurrence 2 (n - 1) a(n - 1) 3 (n - 1) a(n - 2) a(n) = ------------------ + ------------------ n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1] Just for fun, a(1000), equals 1530036790419022830094068760617849229908556040379774601663141696520714432010\ 505204701121726795033893282006994307845948795123386656757478216103147793\ 598816422588288234800268711441603480859153836164038767267854510780820952\ 045840116183968093556741601444043981217670681866042373596290010701135538\ 838865417082061461269201435105172255513381628729705648108431316186711898\ 379048365060433595579837015920602409701854829405120869376654505085317762\ 1901271877999637563068542637350933457 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140, 3602118427251, 10331450919456, 29671013856627, 85317692667643, 245613376802185, 707854577312178, 2042162142208813, 5897493615536452, 17047255430494497, 49320944483427000, 142816973618414817, 413887836110423787, 1200394300050487935, 3484084625456932134, 10119592485062548155, 29412628894558563849, 85543870540455597789, 248952602654003411640, 724947137834104063053, 2112261618875209962525, 6157879192714893166503, 17961708307164474879078, 52418979494565497284659, 153054402342387832806318, 447107296039753836151995, 1306709599137475613111808, 3820682066516442811470123, 11176109832763802046866481, 32705601410484246215745189, 95747934502509579263312730, 280418620117853741708024169, 821578511126260089293299449, 2407969409295125052827266131, 7060047856454817331912175136, 20706869494801128932088054675, 60752886013114747805209321971, 178303876727715987264460117881, 523470228309211183146132538770, 1537292873088850037153655419037, 4515968752463518800863883219540, 13270012942708831885430137279857, 39004474517326916925520791131352, 114677148186439520720469807592881, 337252779926837166106515094143507, 992081497804863208806272348440575, 2919102839611001046292805620867782, 8591299535354652688143556684853307, 25291409899803750802286391976502211, 74471367333926485356188553908612137, 219333623772940705482181740240713080, 646127582088681087104424825527569497, 1903821367984370378973123565306390657, 5610824882652789101159297569379125339, 16539320523461975633674292210615157006, 48763733724885023891037362712600616695, 143801214724243338894845383828477461126, 424143211957453170823189308473526283071, 1251252511019022217034672218022874172864, 3691969061033252211450145056818715608239, 10895571836533928224569430533625487349525, 32160232558185513877392752232595140415729, 94943198059462752589589672745512131329394, 280338312871514003720592178984834743192165, 827891507006386759684746014201909924531418, 2445317582470051292788355811433410180110685, 7223813569919277908209909876381273600472448, 21343507566294190307011455122677671120241053, 63071286725499290051879587077009179781061461, 186407292265725088628262974383000850686750119] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 3 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions No upward-run can belong to, {1} To make it crystal clear here is such a path of semi-length 8 4+ H H + HH HH + HH HH HH HH + H H H H + H H H H 3+ H H H H H + H H H H H H + H HH H HH HH H + H H H H H H + H H H HH H 2+ H H H H H + H H H H + H H H H + HH H HH HH + H H H H 1+ H H H + H H + H H + HH HH +H H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The sequence a(n) satisfies the linear recurrence 2 (n - 1) a(n - 1) 3 (n - 1) a(n - 2) a(n) = ------------------ + ------------------ n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1] Just for fun, a(1000), equals 1530036790419022830094068760617849229908556040379774601663141696520714432010\ 505204701121726795033893282006994307845948795123386656757478216103147793\ 598816422588288234800268711441603480859153836164038767267854510780820952\ 045840116183968093556741601444043981217670681866042373596290010701135538\ 838865417082061461269201435105172255513381628729705648108431316186711898\ 379048365060433595579837015920602409701854829405120869376654505085317762\ 1901271877999637563068542637350933457 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140, 3602118427251, 10331450919456, 29671013856627, 85317692667643, 245613376802185, 707854577312178, 2042162142208813, 5897493615536452, 17047255430494497, 49320944483427000, 142816973618414817, 413887836110423787, 1200394300050487935, 3484084625456932134, 10119592485062548155, 29412628894558563849, 85543870540455597789, 248952602654003411640, 724947137834104063053, 2112261618875209962525, 6157879192714893166503, 17961708307164474879078, 52418979494565497284659, 153054402342387832806318, 447107296039753836151995, 1306709599137475613111808, 3820682066516442811470123, 11176109832763802046866481, 32705601410484246215745189, 95747934502509579263312730, 280418620117853741708024169, 821578511126260089293299449, 2407969409295125052827266131, 7060047856454817331912175136, 20706869494801128932088054675, 60752886013114747805209321971, 178303876727715987264460117881, 523470228309211183146132538770, 1537292873088850037153655419037, 4515968752463518800863883219540, 13270012942708831885430137279857, 39004474517326916925520791131352, 114677148186439520720469807592881, 337252779926837166106515094143507, 992081497804863208806272348440575, 2919102839611001046292805620867782, 8591299535354652688143556684853307, 25291409899803750802286391976502211, 74471367333926485356188553908612137, 219333623772940705482181740240713080, 646127582088681087104424825527569497, 1903821367984370378973123565306390657, 5610824882652789101159297569379125339, 16539320523461975633674292210615157006, 48763733724885023891037362712600616695, 143801214724243338894845383828477461126, 424143211957453170823189308473526283071, 1251252511019022217034672218022874172864, 3691969061033252211450145056818715608239, 10895571836533928224569430533625487349525, 32160232558185513877392752232595140415729, 94943198059462752589589672745512131329394, 280338312871514003720592178984834743192165, 827891507006386759684746014201909924531418, 2445317582470051292788355811433410180110685, 7223813569919277908209909876381273600472448, 21343507566294190307011455122677671120241053, 63071286725499290051879587077009179781061461, 186407292265725088628262974383000850686750119] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 4 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions No upward-run can belong to, {1} No downward-run can belong to, {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 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, 100, 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] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 5 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a valley can not belong to , {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+ HH HH H H + H HH H HH H H + HH HH HH HH HH HH 3+ H 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 sequence a(n) satisfies the linear recurrence (7 n - 13) a(n - 1) 2 (7 n - 16) a(n - 2) (7 n - 19) a(n - 3) a(n) = ------------------- - --------------------- + ------------------- n - 1 n - 1 n - 1 2 (2 n - 5) a(n - 4) + -------------------- 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 3289346391626539101813155177572627650945910687625728029306154349919885008424\ 562012779719925592344491191388079707430456180678738568333584620067184234\ 513521592384389380963000499371452185839175905026267522285034926888559531\ 903736341262514195381952881729901941796423040191760323852471411203274149\ 569108108677836711233758950633967492428868260969935951989860441372979505\ 029895048630530489968962629868140382200656574544165511219873615499568672\ 766576537672005908506328820762696090709573416126643680531141550140136744\ 304118233012639564415569873853310741766620633869235964458061462241620851\ 75145927784775161 For the sake of the OEIS here are the first, 100, terms. [1, 1, 2, 4, 9, 22, 58, 163, 483, 1494, 4783, 15740, 52956, 181391, 630533, 2218761, 7888266, 28291588, 102237141, 371884771, 1360527143, 5002837936, 18479695171, 68539149518, 255137783916, 952914971191, 3569834343547, 13410481705795, 50506214531252, 190661396754623, 721309231245930, 2734340902348660, 10384729349891801, 39508833052959062, 150556764433793122, 574604028257812551, 2196133765002623111, 8404921968965752371, 32207692734494651832, 123567904825171570007, 474617269824566355386, 1824933678818837074702, 7024125634258699052147, 27061810866951754785671, 104356677565423473137257, 402775764533193562448982, 1555852247194778679374801, 6014766389029773513342902, 23270147619699743008876442, 90093831591035950206998211, 349054331386847956567890747, 1353257428538389364335407949, 5249831449006596883287218598, 20378710829070480349853765305, 79152379106432483868793868282, 307607755667932328273940701518, 1196099515989815008181990112109, 4653345274135966755121774940981, 18112685962605211418277062361519, 70536220680328737640650868003150, 274818405130762127363775023157511, 1071215083196600681122389714471826, 4177323183244069093685741008136202, 16296848936793099441935749419523779, 63604423103740186283024835074100419, 248338098813162270659452650321497622, 969987771171029999449381574110315199, 3790101265933944939618704480857715284, 14814671741206925284291813349880162932, 57927549942538373437547202127871692979, 226582129078227610530624915866698146289, 886562118118615134989272323449529514677, 3470016654677134080958962113677550103074, 13585913523362049921786656972261958849929, 53208035532322666331381772934235887854662, 208445752260644142910821280376855464645554, 816832150505028367285449929808641793404649, 3201792565891852961532086177745940693859197, 12553676574768161918442923601638547491147259, 49233755168825636040190509798702664485568774, 193137363402581189781843747869732287019888207, 757840984470589034800991146439643751861772044, 2974374049385115360730728310785431473727584884, 11676592865799907305271600189113407813938977097, 45849774529775678994287493317245372378896223759, 180076204941122301719476603297392517178068338299, 707409923937410757893225686357741965383144870722, 2779581290322485827219473017204671948137505116329, 10923927891708038398667186903772046854896908583564, 42940526005207159580738533951311940846400161042252, 168827401527645830488158392515333238343950696104299, 663901382984815930428284363518445433570702229671429, 2611243420694303752657197022109899747540266225714237, 10272412328169638252044717519540824646909475201719354, 40418206582627380727519801114662572244091122051893759, 159059428206188977677275334863625816582883878433966332, 626062804643219538493657461465488203619840743484621724, 2464625148912081487251507784009490002286894109768942799, 9704133613649570792653803635613114442747623661282312917, 38215017094610905301981615724011907881762196971724186529, 150515516977222850615573432724842861091525181107595601954] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 6 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a valley can not belong to , {1} No downward-run can belong to, {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 + HH 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 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 sequence a(n) satisfies the linear recurrence 3 (n - 2) a(n - 1) 2 (n - 4) a(n - 2) 6 (n - 3) a(n - 3) a(n) = ------------------ + ------------------ - ------------------ n - 1 n - 1 n - 1 2 (n - 4) a(n - 4) (5 n - 17) a(n - 5) 3 (n - 4) a(n - 6) - ------------------ + ------------------- + ------------------ n - 1 n - 1 n - 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4, a(6) = 8] Just for fun, a(1000), equals 3763397943187744689557058298717036661701274707108865401916940111974607872077\ 658288045952433378143909073181283205238953536359626707954324027248931203\ 293142036206158332931880545284748241890280047855652032379329135254532027\ 418033699746548607596676475393378221638914474356962386199724649823596587\ 328530039058456194196361496424523167984070089076512580890702546756287815\ 032033874024553898640073004897040106444624152147473336171196216009277955\ 755465619716781799721328921010420649 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 2, 4, 8, 18, 41, 98, 240, 602, 1538, 3990, 10484, 27845, 74636, 201641, 548520, 1501147, 4130169, 11417537, 31697323, 88335563, 247032739, 693016665, 1949776933, 5500153093, 15553283123, 44080461094, 125191586993, 356241890080, 1015542517685, 2899897830889, 8293768547892, 23755451317723, 68136244293124, 195686735756336, 562704829653673, 1619967823913525, 4668866393038729, 13470098409287510, 38901041194789990, 112450505301046743, 325350499795352311, 942134675221160158, 2730415764681587458, 7919228360313768631, 22985836060498323909, 66764735360530456928, 194057426731047586386, 564413570865224960203, 1642620166663351240445, 4783420332146312182912, 13937710312803494005796, 40633684407300598033641, 118526042023024400779817, 345911977622328522715727, 1010028323307390500414420, 2950597469676623473580492, 8623579438992579475081299, 25215028507019728783868248, 73759693396276342547566305, 215854080907620693861830681, 631941720978248049121784338, 1850818211226686502653504084, 5422694078322422657486457016, 15893733753413182801895787348, 46600585250786617171607185753, 136680562222566567550660388647, 401021482382448314332554769888, 1176981830637742252320304842085, 3455485266944898602230379995380, 10148026678529994810685008317507, 29811490327627053532556549200311, 87601537368610156299641801091562, 257491138454528754065273560703219, 757063086930258548848658706013351, 2226475475420250467994521359008779, 6549630223943234361577342672535706, 19271953848944351261094294070549004, 56720754945695480096258405339418098, 166979380329006582686255781263536965, 491683542308681667998212844009195570, 1448131419704670211913722491631048010, 4266063776811701283206969539871248671, 12570178524515842724568644540915080142, 37046572745428956862697268525140367578, 109205610321775427616856875957768924740, 321980889215005203257661276943201041326, 949514174948532341005286932136918262543, 2800638604072808547641255591093610467486, 8262187851536834686256841645171148545066, 24378872289013286125654724617628842666447, 71946711756248222025227206505790090246738, 212366188207300131383966258865261445645756, 626953350753974988907463750838598419202540, 1851223774793914375545886271767185599658694, 5467073315060779063517258382870052587610843, 16148108703282747519769980332748062103004374, 47704326029009105434055253692071275392467484] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 7 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a valley can not belong to , {1} No upward-run can belong to, {1} To make it crystal clear here is such a path of semi-length 8 4+ H + HH + HH HH + H H + H H 3+ H H + H H + H HH + H H + H H 2+ H H H H + HH H H HH + H H H H H H + HH H HH HH H HH + H H H H H H 1+ H H H H H H + H H 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 sequence a(n) satisfies the linear recurrence 3 (n - 2) a(n - 1) 2 (n - 4) a(n - 2) 6 (n - 3) a(n - 3) a(n) = ------------------ + ------------------ - ------------------ n - 1 n - 1 n - 1 2 (n - 4) a(n - 4) (5 n - 17) a(n - 5) 3 (n - 4) a(n - 6) - ------------------ + ------------------- + ------------------ n - 1 n - 1 n - 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4, a(6) = 8] Just for fun, a(1000), equals 3763397943187744689557058298717036661701274707108865401916940111974607872077\ 658288045952433378143909073181283205238953536359626707954324027248931203\ 293142036206158332931880545284748241890280047855652032379329135254532027\ 418033699746548607596676475393378221638914474356962386199724649823596587\ 328530039058456194196361496424523167984070089076512580890702546756287815\ 032033874024553898640073004897040106444624152147473336171196216009277955\ 755465619716781799721328921010420649 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 2, 4, 8, 18, 41, 98, 240, 602, 1538, 3990, 10484, 27845, 74636, 201641, 548520, 1501147, 4130169, 11417537, 31697323, 88335563, 247032739, 693016665, 1949776933, 5500153093, 15553283123, 44080461094, 125191586993, 356241890080, 1015542517685, 2899897830889, 8293768547892, 23755451317723, 68136244293124, 195686735756336, 562704829653673, 1619967823913525, 4668866393038729, 13470098409287510, 38901041194789990, 112450505301046743, 325350499795352311, 942134675221160158, 2730415764681587458, 7919228360313768631, 22985836060498323909, 66764735360530456928, 194057426731047586386, 564413570865224960203, 1642620166663351240445, 4783420332146312182912, 13937710312803494005796, 40633684407300598033641, 118526042023024400779817, 345911977622328522715727, 1010028323307390500414420, 2950597469676623473580492, 8623579438992579475081299, 25215028507019728783868248, 73759693396276342547566305, 215854080907620693861830681, 631941720978248049121784338, 1850818211226686502653504084, 5422694078322422657486457016, 15893733753413182801895787348, 46600585250786617171607185753, 136680562222566567550660388647, 401021482382448314332554769888, 1176981830637742252320304842085, 3455485266944898602230379995380, 10148026678529994810685008317507, 29811490327627053532556549200311, 87601537368610156299641801091562, 257491138454528754065273560703219, 757063086930258548848658706013351, 2226475475420250467994521359008779, 6549630223943234361577342672535706, 19271953848944351261094294070549004, 56720754945695480096258405339418098, 166979380329006582686255781263536965, 491683542308681667998212844009195570, 1448131419704670211913722491631048010, 4266063776811701283206969539871248671, 12570178524515842724568644540915080142, 37046572745428956862697268525140367578, 109205610321775427616856875957768924740, 321980889215005203257661276943201041326, 949514174948532341005286932136918262543, 2800638604072808547641255591093610467486, 8262187851536834686256841645171148545066, 24378872289013286125654724617628842666447, 71946711756248222025227206505790090246738, 212366188207300131383966258865261445645756, 626953350753974988907463750838598419202540, 1851223774793914375545886271767185599658694, 5467073315060779063517258382870052587610843, 16148108703282747519769980332748062103004374, 47704326029009105434055253692071275392467484] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 8 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a valley can not belong to , {1} No upward-run can belong to, {1} No downward-run can belong to, {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+ HH H H + H HH H H + HH HH HH HH 3+ H H H H + HH HH HH HH + HH H HH HH 2+ HH HH HH + H H + HH HH + H H 1+ HH HH + H H +HH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The sequence a(n) satisfies the linear recurrence 3 (n - 2) a(n - 1) (n + 2) a(n - 3) (5 n - 23) a(n - 4) a(n) = ------------------ - ---------------- - ------------------- n - 1 n - 1 n - 1 4 (n - 4) a(n - 6) 3 (n - 5) a(n - 7) (n - 4) a(n - 8) + ------------------ + ------------------ + ---------------- n - 1 n - 1 n - 1 (n - 7) a(n - 9) - ---------------- n - 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 3, a(6) = 6, a(7) = 11, a(8) = 22, a(9) = 45] Just for fun, a(1000), equals 3679329354183413844967318910665361056844937088116723428839314295806782622459\ 761644218855974879746674632247618295119358507952050860861498733985750023\ 320005708147465273668097125048352971348715839972922317712894081221986762\ 455251612196820995096952010222809404836446358288167158230786317499834756\ 181047953984973476127628539919109285982628330840971677694462256535820928\ 7745522713638145938488653748862657454283926779873 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 2, 3, 6, 11, 22, 45, 95, 205, 452, 1013, 2303, 5299, 12318, 28887, 68261, 162378, 388524, 934445, 2257825, 5477978, 13340342, 32597052, 79895596, 196374894, 483913063, 1195304610, 2958976037, 7339834801, 18241094639, 45412924028, 113245700219, 282834394783, 707407654401, 1771727090682, 4443029765522, 11155412690573, 28040604020532, 70559904175088, 177735079073901, 448136569131253, 1130964218420963, 2856730577032510, 7221937035815530, 18271971340356949, 46264602062392922, 117227479522291455, 297244335207374079, 754203530022169492, 1914883646655804475, 4864787119569857793, 12366373073388985492, 31453425461785677412, 80044458790641774203, 203809045620843784774, 519201725396429756541, 1323309312702391048197, 3374362078593316366604, 8608350819607942123095, 21970475292914355350454, 56097532741804671821420, 143293600571198079874492, 366170004247708309164512, 936065320726018453315109, 2393821227622028733131447, 6123989383217901770489560, 15672183956044108406708589, 40121062224202163233919784, 102744544659869498024526596, 263199097281447721431070670, 674443076084351358917512888, 1728771776052830935789889303, 4432592643567142135509390624, 11368476318425902647780179864, 29165378348002562991663729555, 74842906904770854698923268980, 192109239699919575705173539470, 493239045378109676774564459254, 1266704647942467831838666714549, 3253862825667795067086975460886, 8360387768269617869541470016906, 21485939561519119323971592020157, 55230701932447147705776562477159, 142004689399176019947282705368515, 365189625557095661180664282333447, 939346000239253860837716511164830, 2416696053162063667458685953035157, 6218787279970599797897622870739574, 16005697704745345705632449082412180, 41202810360147745584041893709115887, 106086600734727185860399731461973554, 273195725269569579262914425143253384, 703663787334094074112217219749705993, 1812728489668564198964352359374610211, 4670624475445511892818963507039155536, 12036222263015752748284469824403616053, 31022513337880797655272396083908134269, 79971237524146989974840114770529202975] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 9 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} To make it crystal clear here is such a path of semi-length 8 4+ H H H + HH HH HH + HH HH HH HH HH HH + H H H H H H + H H H H H H 3+ H H H H H H + H H H H H H + H HH HH H HH H + H H H H H H + H HH HH H 2+ H H H H + H H + H H + HH HH + H H 1+ H H + H H + H H + HH HH +H H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The sequence a(n) satisfies the linear recurrence (7 n - 5) a(n - 1) (2 n - 1) a(n - 2) a(n) = 1/2 ------------------ + ------------------ n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1] Just for fun, a(1000), equals 9092286347408461381190066458644902332454977875247293311387713927335022651708\ 790591454794080031581991630628884894078589863816755856423465455809978902\ 215379119222272899206264366066173821986022926458407504948455831289366140\ 238545615125470513702613444381026177032665897911379872276676494537250861\ 786577236406823049366761456188177013994590407524775514493010776149916793\ 192693983980293384686624135032669547056492248204325339662817306751885575\ 741928461674191908125700977179251990434492028091611489047246596478022834\ 937256638120591432185377578709965401290745742725035892110974195554730651\ 90163315088837952 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, 1174281, 4260282, 15548694, 57048048, 210295326, 778483932, 2892818244, 10786724388, 40347919626, 151355847012, 569274150156, 2146336125648, 8110508473252, 30711521221376, 116518215264492, 442862000693438, 1686062250699433, 6429286894263738, 24552388991392230, 93891870710425440, 359526085719652662, 1378379704593824300, 5290709340633314596, 20330047491994213884, 78201907647506243758, 301111732041234778316, 1160507655117628665252, 4476705468260134734384, 17283862221822154612428, 66784808491631598524136, 258257655550682547281952, 999430099263282762985884, 3870449306134945313530218, 14999162225528050786449636, 58164368008320657345771132, 225693938585648240354418720, 876283859585256206634677868, 3404250905464530089298069144, 13232458020154047930422174184, 51462706717814193160065835848, 200248505655069639143771836788, 779583055476874615924354019592, 3036436936183999440812652222360, 11832257960295426231716284345152, 46128101164413438900891017233464, 179908446981581773414876213066824, 701971258807269134635948282986036, 2740078349888793257925566282115150, 10699829696578416783892946132079081, 41798010431096781502021219407150522, 163340579722359938988493911653198214, 638538996714279864941997991295333568, 2497071293923016435025958857276905766, 9768326864016750514166296878390022092, 38225298567471767606009671892655543204, 149630101971372103975387060781201540748, 585896003224455083257277558204514001926, 2294836960710825238080831317895275857212, 8991026714499287312424083625179682584244, 35236231325289045264392077003584793150128, 138130323492907137936572107257612170438556, 541632665468735836946094307375174980176232, 2124388132447284037191145950509844740424144, 8334377297181300269010107664288850226412948, 32705433157175579095340022095179239506461326, 128372324009044660179471911967155763878965452, 503993626969145805876080482518755846394324244, 1979148211509587338293580407493688668552665248, 7773718402053594748220780055210983483921784516, 30540361365363299979833635989728831829531710792, 120008544837015909024404413649719867295569784824, 471672579042628963474316122196878295713766809848, 1854203747256947885520189852987014581357492252236, 7290555543704239455774477553887935781005049071352, 28671352521029337457361079966129122840838243094824, 112776402891485729533296180406356262122854564465888, 443679098954434526198051535065092801119803262742456, 1745816567314785079609901018849128354327114208640672, 6870770627588552163759212972464607438843408459597464, 27045052953875931793851675304182520726563160223920268, 106474146282100536687532050659647101139858833632154666, 419249825847663835582536909897646247848685962301374692, 1651096689279145274990666815740800205930410367538659804, 6503416333425215081013105515458116277891272291680547648, 25619970868088071350587297546292370028064729666538031676, 100944429963070639155616121424698241963988476467501507832, 397787758563530428765776974324701195228424522535622200744] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 10 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} No downward-run can belong to, {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 sequence a(n) satisfies the linear recurrence 2 (n - 1) a(n - 1) 3 (n - 1) a(n - 2) a(n) = ------------------ + ------------------ n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1] Just for fun, a(1000), equals 1530036790419022830094068760617849229908556040379774601663141696520714432010\ 505204701121726795033893282006994307845948795123386656757478216103147793\ 598816422588288234800268711441603480859153836164038767267854510780820952\ 045840116183968093556741601444043981217670681866042373596290010701135538\ 838865417082061461269201435105172255513381628729705648108431316186711898\ 379048365060433595579837015920602409701854829405120869376654505085317762\ 1901271877999637563068542637350933457 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140, 3602118427251, 10331450919456, 29671013856627, 85317692667643, 245613376802185, 707854577312178, 2042162142208813, 5897493615536452, 17047255430494497, 49320944483427000, 142816973618414817, 413887836110423787, 1200394300050487935, 3484084625456932134, 10119592485062548155, 29412628894558563849, 85543870540455597789, 248952602654003411640, 724947137834104063053, 2112261618875209962525, 6157879192714893166503, 17961708307164474879078, 52418979494565497284659, 153054402342387832806318, 447107296039753836151995, 1306709599137475613111808, 3820682066516442811470123, 11176109832763802046866481, 32705601410484246215745189, 95747934502509579263312730, 280418620117853741708024169, 821578511126260089293299449, 2407969409295125052827266131, 7060047856454817331912175136, 20706869494801128932088054675, 60752886013114747805209321971, 178303876727715987264460117881, 523470228309211183146132538770, 1537292873088850037153655419037, 4515968752463518800863883219540, 13270012942708831885430137279857, 39004474517326916925520791131352, 114677148186439520720469807592881, 337252779926837166106515094143507, 992081497804863208806272348440575, 2919102839611001046292805620867782, 8591299535354652688143556684853307, 25291409899803750802286391976502211, 74471367333926485356188553908612137, 219333623772940705482181740240713080, 646127582088681087104424825527569497, 1903821367984370378973123565306390657, 5610824882652789101159297569379125339, 16539320523461975633674292210615157006, 48763733724885023891037362712600616695, 143801214724243338894845383828477461126, 424143211957453170823189308473526283071, 1251252511019022217034672218022874172864, 3691969061033252211450145056818715608239, 10895571836533928224569430533625487349525, 32160232558185513877392752232595140415729, 94943198059462752589589672745512131329394, 280338312871514003720592178984834743192165, 827891507006386759684746014201909924531418, 2445317582470051292788355811433410180110685, 7223813569919277908209909876381273600472448, 21343507566294190307011455122677671120241053, 63071286725499290051879587077009179781061461, 186407292265725088628262974383000850686750119] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 11 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} No upward-run can belong to, {1} To make it crystal clear here is such a path of semi-length 8 4+ H H + HH HH + HH HH HH HH + H H H H + H H H H 3+ H H H H + H H H H + H HH HH H + H H H H + H H H H 2+ 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 sequence a(n) satisfies the linear recurrence 2 (n - 1) a(n - 1) 3 (n - 1) a(n - 2) a(n) = ------------------ + ------------------ n + 1 n + 1 subject to the initial conditions [a(1) = 0, a(2) = 1] Just for fun, a(1000), equals 1530036790419022830094068760617849229908556040379774601663141696520714432010\ 505204701121726795033893282006994307845948795123386656757478216103147793\ 598816422588288234800268711441603480859153836164038767267854510780820952\ 045840116183968093556741601444043981217670681866042373596290010701135538\ 838865417082061461269201435105172255513381628729705648108431316186711898\ 379048365060433595579837015920602409701854829405120869376654505085317762\ 1901271877999637563068542637350933457 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140, 3602118427251, 10331450919456, 29671013856627, 85317692667643, 245613376802185, 707854577312178, 2042162142208813, 5897493615536452, 17047255430494497, 49320944483427000, 142816973618414817, 413887836110423787, 1200394300050487935, 3484084625456932134, 10119592485062548155, 29412628894558563849, 85543870540455597789, 248952602654003411640, 724947137834104063053, 2112261618875209962525, 6157879192714893166503, 17961708307164474879078, 52418979494565497284659, 153054402342387832806318, 447107296039753836151995, 1306709599137475613111808, 3820682066516442811470123, 11176109832763802046866481, 32705601410484246215745189, 95747934502509579263312730, 280418620117853741708024169, 821578511126260089293299449, 2407969409295125052827266131, 7060047856454817331912175136, 20706869494801128932088054675, 60752886013114747805209321971, 178303876727715987264460117881, 523470228309211183146132538770, 1537292873088850037153655419037, 4515968752463518800863883219540, 13270012942708831885430137279857, 39004474517326916925520791131352, 114677148186439520720469807592881, 337252779926837166106515094143507, 992081497804863208806272348440575, 2919102839611001046292805620867782, 8591299535354652688143556684853307, 25291409899803750802286391976502211, 74471367333926485356188553908612137, 219333623772940705482181740240713080, 646127582088681087104424825527569497, 1903821367984370378973123565306390657, 5610824882652789101159297569379125339, 16539320523461975633674292210615157006, 48763733724885023891037362712600616695, 143801214724243338894845383828477461126, 424143211957453170823189308473526283071, 1251252511019022217034672218022874172864, 3691969061033252211450145056818715608239, 10895571836533928224569430533625487349525, 32160232558185513877392752232595140415729, 94943198059462752589589672745512131329394, 280338312871514003720592178984834743192165, 827891507006386759684746014201909924531418, 2445317582470051292788355811433410180110685, 7223813569919277908209909876381273600472448, 21343507566294190307011455122677671120241053, 63071286725499290051879587077009179781061461, 186407292265725088628262974383000850686750119] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 12 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} No upward-run can belong to, {1} No downward-run can belong to, {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 H + HH H HH HH + HH HH H HH 2+ HH HH H HH + H H HH H + HH HH H HH + H H HH H 1+ HH H HH + H H +HH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 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, 100, 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] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 13 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} The elevation of a valley can not belong to , {1} To make it crystal clear here is such a path of semi-length 8 5+ H + H HH + HH H + H HH 4+ H H H H + HHH HHH HH H + HH H HH H H HH + H HH H HH H H 3+ H 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 sequence a(n) satisfies the linear recurrence (5 n - 11) a(n - 1) 2 (2 n - 5) a(n - 2) a(n) = ------------------- - -------------------- - a(n - 3) n - 1 n - 1 2 (2 n - 5) a(n - 4) + -------------------- n - 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 3] Just for fun, a(1000), equals 1675978308135788135555412396405303632928466859340501442364100837069866375756\ 143830236932569333704797901522480611549720329590326987171892098531904771\ 466453107768098182871283916076007024057272453507131637619369572309468876\ 130987772391909302723877633064871393981999037109914838987914425332911519\ 447650360295622958355268349302968204433902311876460210104211735640135872\ 892108675519457654191767687303809099792690765881222743803945419489542083\ 349449221136431928180499606284456123753574096873116913480230599918574454\ 325396127287685991259538575058218293841337429219756301763767131838531848\ 55225615857545571 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 3, 7, 20, 59, 184, 593, 1964, 6642, 22845, 79667, 281037, 1001092, 3595865, 13009673, 47366251, 173415176, 638044203, 2357941142, 8748646386, 32576869203, 121701491701, 456012458965, 1713339737086, 6453584646837, 24364925260024, 92185136438942, 349479503542465, 1327356794933809, 5050158160587171, 19245314696271615, 73452022778386004, 280737995030041943, 1074436722483501092, 4117270194612416350, 15796330585442827899, 60672698187581069171, 233289290779975354221, 897918331924508326712, 3459372676013419366361, 13340001976871342146160, 51486513556851277778688, 198880620085923210073027, 768840737702048561014907, 2974472078222445356489939, 11515920169669695536463232, 44615853189158693861877815, 172969279353105613983379776, 671005604363053056501525116, 2604651408930055016263421757, 10116467800091265787510858137, 39314629141500838681151750533, 152867849188353217915442174656, 594711099416215423575540825943, 2314811086883533455886868951382, 9014400165540053735521085241038, 35120641922898690216190765327759, 136894291125137460793802215188457, 533824886087174392788924573314531, 2082555208760395745259506587025668, 8127788876220113934952785219053547, 31733701733178566367875319192012328, 123946997083190150410551197551366785, 484298378082786695954607455045860188, 1892983249500527798459222030097713210, 7401717836977650383042586538395491525, 28951144480851381150446531697406581287, 113277085230311139078172950331009976577, 443360869903549464251914157247673109752, 1735831833842980353591409802740496073065, 6798124673258774773932177046404551812838, 26631654193064625172609261457411519728786, 104359311724299022660226089287020292540221, 409058065362143569023830203759424874754623, 1603822065599457755679981664309975485816857, 6289871684238462644348141783417819654301156, 24673956345686203650535672858745939972796573, 96815377891619204354545843049083293726315316, 379975587382645641164481547295156241336406390, 1491661208984295709445578751441077758031223757, 5857135881080996987554274205898127647804563181, 23003745309315128181124933176518627042864391071, 90366525233111027179567406459746196427818373414, 355066840391425148220655595543016635200685090673, 1395416798004383856012567320409974466880924104122, 5485130346327797563347695742121135728881857045028, 21565378340601799212196185107341005237048762349295, 84803222128360329726680255273077212232849373506173, 333542250086033328687286000309797723590514888487745, 1312111472545786311404489065738998582715927216089250, 5162620484001430667095662383229270880257109522606877, 20316436056407286745536703346697816388680525761954732, 79965201119201916185594777861788466697934327453303482, 314795926153277490687414892102035918823958045418926205, 1239453288074298411794484059210277699272508277891875523, 4880931291361050881172759822727735892284080647817266341, 19224064721337348827502222777282732735173077553298095236, 75727969502864408197895439326115311369921300900162830713] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 14 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} The elevation of a valley can not belong to , {1} No downward-run can belong to, {1} To make it crystal clear here is such a path of semi-length 8 7+ HH + H HH + HH HH 6+ H HH + H HH + HH HH 5+ HH HH + H HH + HH HH 4+ H H HH + HH HH HH HH 3+ HH HHH HH + HH HH + HH HH 2+ HH HH + HH HH + H H 1+ HH HH + HH HH + HH HH -**+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+**- 2 4 6 8 10 12 14 16 The sequence a(n) satisfies the linear recurrence 3 (n - 2) a(n - 1) 2 (n - 4) a(n - 2) 6 (n - 3) a(n - 3) a(n) = ------------------ + ------------------ - ------------------ n - 1 n - 1 n - 1 2 (n - 4) a(n - 4) (5 n - 17) a(n - 5) 3 (n - 4) a(n - 6) - ------------------ + ------------------- + ------------------ n - 1 n - 1 n - 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4, a(6) = 8] Just for fun, a(1000), equals 3763397943187744689557058298717036661701274707108865401916940111974607872077\ 658288045952433378143909073181283205238953536359626707954324027248931203\ 293142036206158332931880545284748241890280047855652032379329135254532027\ 418033699746548607596676475393378221638914474356962386199724649823596587\ 328530039058456194196361496424523167984070089076512580890702546756287815\ 032033874024553898640073004897040106444624152147473336171196216009277955\ 755465619716781799721328921010420649 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 2, 4, 8, 18, 41, 98, 240, 602, 1538, 3990, 10484, 27845, 74636, 201641, 548520, 1501147, 4130169, 11417537, 31697323, 88335563, 247032739, 693016665, 1949776933, 5500153093, 15553283123, 44080461094, 125191586993, 356241890080, 1015542517685, 2899897830889, 8293768547892, 23755451317723, 68136244293124, 195686735756336, 562704829653673, 1619967823913525, 4668866393038729, 13470098409287510, 38901041194789990, 112450505301046743, 325350499795352311, 942134675221160158, 2730415764681587458, 7919228360313768631, 22985836060498323909, 66764735360530456928, 194057426731047586386, 564413570865224960203, 1642620166663351240445, 4783420332146312182912, 13937710312803494005796, 40633684407300598033641, 118526042023024400779817, 345911977622328522715727, 1010028323307390500414420, 2950597469676623473580492, 8623579438992579475081299, 25215028507019728783868248, 73759693396276342547566305, 215854080907620693861830681, 631941720978248049121784338, 1850818211226686502653504084, 5422694078322422657486457016, 15893733753413182801895787348, 46600585250786617171607185753, 136680562222566567550660388647, 401021482382448314332554769888, 1176981830637742252320304842085, 3455485266944898602230379995380, 10148026678529994810685008317507, 29811490327627053532556549200311, 87601537368610156299641801091562, 257491138454528754065273560703219, 757063086930258548848658706013351, 2226475475420250467994521359008779, 6549630223943234361577342672535706, 19271953848944351261094294070549004, 56720754945695480096258405339418098, 166979380329006582686255781263536965, 491683542308681667998212844009195570, 1448131419704670211913722491631048010, 4266063776811701283206969539871248671, 12570178524515842724568644540915080142, 37046572745428956862697268525140367578, 109205610321775427616856875957768924740, 321980889215005203257661276943201041326, 949514174948532341005286932136918262543, 2800638604072808547641255591093610467486, 8262187851536834686256841645171148545066, 24378872289013286125654724617628842666447, 71946711756248222025227206505790090246738, 212366188207300131383966258865261445645756, 626953350753974988907463750838598419202540, 1851223774793914375545886271767185599658694, 5467073315060779063517258382870052587610843, 16148108703282747519769980332748062103004374, 47704326029009105434055253692071275392467484] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 15 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} The elevation of a valley can not belong to , {1} No upward-run can belong to, {1} To make it crystal clear here is such a path of semi-length 8 7+ HHH + H HH + HH HH 6+ HH H H + H HH H H + HH HH HH HH 5+ HH H HH + H H + HH HH 4+ H H + HH HH 3+ HH HH + HH HH + HH HH 2+ HH HH + HH HH + H H 1+ HH HH + HH HH + HH HH -**+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+**- 2 4 6 8 10 12 14 16 The sequence a(n) satisfies the linear recurrence 3 (n - 2) a(n - 1) 2 (n - 4) a(n - 2) 6 (n - 3) a(n - 3) a(n) = ------------------ + ------------------ - ------------------ n - 1 n - 1 n - 1 2 (n - 4) a(n - 4) (5 n - 17) a(n - 5) 3 (n - 4) a(n - 6) - ------------------ + ------------------- + ------------------ n - 1 n - 1 n - 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4, a(6) = 8] Just for fun, a(1000), equals 3763397943187744689557058298717036661701274707108865401916940111974607872077\ 658288045952433378143909073181283205238953536359626707954324027248931203\ 293142036206158332931880545284748241890280047855652032379329135254532027\ 418033699746548607596676475393378221638914474356962386199724649823596587\ 328530039058456194196361496424523167984070089076512580890702546756287815\ 032033874024553898640073004897040106444624152147473336171196216009277955\ 755465619716781799721328921010420649 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 2, 4, 8, 18, 41, 98, 240, 602, 1538, 3990, 10484, 27845, 74636, 201641, 548520, 1501147, 4130169, 11417537, 31697323, 88335563, 247032739, 693016665, 1949776933, 5500153093, 15553283123, 44080461094, 125191586993, 356241890080, 1015542517685, 2899897830889, 8293768547892, 23755451317723, 68136244293124, 195686735756336, 562704829653673, 1619967823913525, 4668866393038729, 13470098409287510, 38901041194789990, 112450505301046743, 325350499795352311, 942134675221160158, 2730415764681587458, 7919228360313768631, 22985836060498323909, 66764735360530456928, 194057426731047586386, 564413570865224960203, 1642620166663351240445, 4783420332146312182912, 13937710312803494005796, 40633684407300598033641, 118526042023024400779817, 345911977622328522715727, 1010028323307390500414420, 2950597469676623473580492, 8623579438992579475081299, 25215028507019728783868248, 73759693396276342547566305, 215854080907620693861830681, 631941720978248049121784338, 1850818211226686502653504084, 5422694078322422657486457016, 15893733753413182801895787348, 46600585250786617171607185753, 136680562222566567550660388647, 401021482382448314332554769888, 1176981830637742252320304842085, 3455485266944898602230379995380, 10148026678529994810685008317507, 29811490327627053532556549200311, 87601537368610156299641801091562, 257491138454528754065273560703219, 757063086930258548848658706013351, 2226475475420250467994521359008779, 6549630223943234361577342672535706, 19271953848944351261094294070549004, 56720754945695480096258405339418098, 166979380329006582686255781263536965, 491683542308681667998212844009195570, 1448131419704670211913722491631048010, 4266063776811701283206969539871248671, 12570178524515842724568644540915080142, 37046572745428956862697268525140367578, 109205610321775427616856875957768924740, 321980889215005203257661276943201041326, 949514174948532341005286932136918262543, 2800638604072808547641255591093610467486, 8262187851536834686256841645171148545066, 24378872289013286125654724617628842666447, 71946711756248222025227206505790090246738, 212366188207300131383966258865261445645756, 626953350753974988907463750838598419202540, 1851223774793914375545886271767185599658694, 5467073315060779063517258382870052587610843, 16148108703282747519769980332748062103004374, 47704326029009105434055253692071275392467484] ------------------------------------------------------------ ------------------------------------------------------------ Theorem Number, 16 Theorem: Let a(n) be the number of Dyck paths of semi-length n obeying the f\ ollowing restrictions The elevation of a peak can not belong to , {1} The elevation of a valley can not belong to , {1} No upward-run can belong to, {1} No downward-run can belong to, {1} To make it crystal clear here is such a path of semi-length 8 5+ H + H HH + HH H + H HH 4+ H H + HH H + H HH + H H 3+ H H H + HH H HH HH + H HH H H + HH H HH HH 2+ H H H H + H HH H H + HH H HH HH + H HH H H 1+ H H H H + HH H HH HH + H HH H H +HH HHH HH -*-+-+-+-++-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The sequence a(n) satisfies the linear recurrence 3 (n - 2) a(n - 1) (n + 2) a(n - 3) (5 n - 23) a(n - 4) a(n) = ------------------ - ---------------- - ------------------- n - 1 n - 1 n - 1 4 (n - 4) a(n - 6) 3 (n - 5) a(n - 7) (n - 4) a(n - 8) + ------------------ + ------------------ + ---------------- n - 1 n - 1 n - 1 (n - 7) a(n - 9) - ---------------- n - 1 subject to the initial conditions [a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 3, a(6) = 6, a(7) = 11, a(8) = 22, a(9) = 45] Just for fun, a(1000), equals 3679329354183413844967318910665361056844937088116723428839314295806782622459\ 761644218855974879746674632247618295119358507952050860861498733985750023\ 320005708147465273668097125048352971348715839972922317712894081221986762\ 455251612196820995096952010222809404836446358288167158230786317499834756\ 181047953984973476127628539919109285982628330840971677694462256535820928\ 7745522713638145938488653748862657454283926779873 For the sake of the OEIS here are the first, 100, terms. [1, 0, 1, 1, 2, 3, 6, 11, 22, 45, 95, 205, 452, 1013, 2303, 5299, 12318, 28887, 68261, 162378, 388524, 934445, 2257825, 5477978, 13340342, 32597052, 79895596, 196374894, 483913063, 1195304610, 2958976037, 7339834801, 18241094639, 45412924028, 113245700219, 282834394783, 707407654401, 1771727090682, 4443029765522, 11155412690573, 28040604020532, 70559904175088, 177735079073901, 448136569131253, 1130964218420963, 2856730577032510, 7221937035815530, 18271971340356949, 46264602062392922, 117227479522291455, 297244335207374079, 754203530022169492, 1914883646655804475, 4864787119569857793, 12366373073388985492, 31453425461785677412, 80044458790641774203, 203809045620843784774, 519201725396429756541, 1323309312702391048197, 3374362078593316366604, 8608350819607942123095, 21970475292914355350454, 56097532741804671821420, 143293600571198079874492, 366170004247708309164512, 936065320726018453315109, 2393821227622028733131447, 6123989383217901770489560, 15672183956044108406708589, 40121062224202163233919784, 102744544659869498024526596, 263199097281447721431070670, 674443076084351358917512888, 1728771776052830935789889303, 4432592643567142135509390624, 11368476318425902647780179864, 29165378348002562991663729555, 74842906904770854698923268980, 192109239699919575705173539470, 493239045378109676774564459254, 1266704647942467831838666714549, 3253862825667795067086975460886, 8360387768269617869541470016906, 21485939561519119323971592020157, 55230701932447147705776562477159, 142004689399176019947282705368515, 365189625557095661180664282333447, 939346000239253860837716511164830, 2416696053162063667458685953035157, 6218787279970599797897622870739574, 16005697704745345705632449082412180, 41202810360147745584041893709115887, 106086600734727185860399731461973554, 273195725269569579262914425143253384, 703663787334094074112217219749705993, 1812728489668564198964352359374610211, 4670624475445511892818963507039155536, 12036222263015752748284469824403616053, 31022513337880797655272396083908134269, 79971237524146989974840114770529202975] ------------------------------------------------------------ This concludes this exciting paper with its, 16, theorems that took, 14.001, to generate. --------------------------------------------------