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, 4 r + 3 (ii) the heights of the valleys are not allowed to take certain values, 4 r + 3 (iii) the upward runs can't have certain values, 4 r + 3 (iv) the downward runs can't have certain values, 4 r + 3 ------------------------------------------------------------ Theorem Number, 1 Let a(n) be the number of Dyck paths of semi-length n To make it crystal clear here is such a path of semi-length 8 5+ H H + HH H H HH + H HH HH H + HH H H HH 4+ H H H H H + HHH H HH HH H + HH H HH H H HH + H HH H HH H H 3+ H H H H + HH HH + H H + HH HH 2+ H H + H H + HH HH + H H 1+ H H + HH HH + H H +HH HH -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 2 (2 n - 1) a(n - 1) a(n) = -------------------- n + 1 subject to the initial conditions [a(1) = 1] Just for fun, a(1000), equals 2046105521468021692642519982997827217179245642339057975844538099572176010191\ 891863964968026156453752449015750569428595097318163634370154637380666882\ 886375203359653243390929717431080443509007504772912973142253209352126946\ 839844796747697638537600100637918819326569730982083021538057087711176285\ 777909275869648636874856805956580057673173655666887003493944650164153396\ 910927037406301799052584663611016897272893305532116292143271037140718751\ 625839812072682464343153792956281748582435751481498598087586998603921577\ 523657477775758899987954012641033870640665444651660246024318184109046864\ 244732001962029120 For the sake of the OEIS here are the first, 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 , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 5+ H H + HH H H HH + H H HH H + HH HHH HH 4+ H H H + H H + HH HH + H H 3+ H H + HH HH + H H + HH HH 2+ H H H + HHH H H + HH H HH HH + H HH H H 1+ H H H H + HH H HH HH + H HH H H +HH HHH HH -*-+-+-+-+*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 5 4 2 2 P(x) x + P(x) x + P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 5 a(n) = 1/20 (5483321745761692629154053764810456758825936 n 4 - 107242566323822704692204511711156433619864678 n 3 + 932936394089247532276679481829728806893454807 n 2 - 4475850240656363222517866297863276130500791388 n + 11432336984329082960333534428241635534502575061 n - 11981628935569213384384583065109742970251559830) a(n - 1)/((n + 1) %1) 6 - 1/16 (21933286983046770516616215059241827035303744 n 5 - 543839208220945341507928575432537290607770708 n 4 + 5575062036448110791168661913092801332492331992 n 3 - 29963903134430476464454115975713151923302299023 n 2 + 88037590954429496455068426666140859845164606788 n - 131996049371239468461872545267816184589028709385 n + 76930657583545876086661472738444760948494415900) a(n - 2)/(n (n + 1) %1) 7 + 1/64 (65799860949140311549848645177725481105911232 n 6 - 1974420421782164543261636140533972996722689384 n 5 + 23879263756829823089374428497016527499643263028 n 4 - 152780810711526582116986138006676779662273014010 n 3 + 562577350730416554147339073654394927218433561555 n 2 - 1198234593732908055162294457315267572173159318606 n + 1372629755952343710874031490020600374628730741165 n - 654829981137629738999251840340059577389825490820) a(n - 3)/((n - 1) n 8 (n + 1) %1) + 1/128 (307066017762654787232627010829385578494252416 n 7 - 9132126337156641771565979000847360221435248600 n 6 + 119794144546419500243764846213627276986511542080 n 5 - 898914250417405815404381379076633603092800672506 n 4 + 4190153337753580883321101881756805755319158084926 n 3 - 12343416518776377281097694499663825071630263182053 n 2 + 22312920525555024749757307838579418541801668937797 n - 22516534813597583069956584877931855147979317064372 n + 9667337459113593718987779814152925359120387738240) a(n - 4)/((n + 1) n (n - 1) (n - 2) %1) - 3/1280 ( 8 1995929115457256117012075570391006260212640704 n 7 - 66160898749049139986480168949214865802672575128 n 6 + 944310749413307850571882099694108165012215566788 n 5 - 7576650019854270338341880537521566895311867084110 n 4 + 37348420581258791724985555041094653377748227118571 n 3 - 115694256273647880446574943914250719574202607915492 n 2 + 219598671463362405551986361534172484244537191551677 n - 233036557407332560260942387395131352681899602275130 n + 105571579875577293855058598063461913575848026461800) a(n - 5)/((n + 1) n (n - 1) (n - 2) %1) - 3/256 (n - 5) ( 7 87733147932187082066464860236967308141214976 n 6 - 2590659207919704770707684675036094964874237305 n 5 + 32147309501415073816648519304905164557734178362 n 4 - 216893696995080841868571630070204532057594170509 n 3 + 857333356054355764640236335052303996739253914740 n 2 - 1980000074632472405300458060503872262865026509454 n + 2465744364562580837234378976399267416098643558964 n - 1272295578861168876730230484336777256468936052240) a(n - 6)/((n + 1) n (n - 1) (n - 2) %1) - 9/5120 (n - 5) (n - 6) (3 n - 19) (3 n - 17) ( 4 5483321745761692629154053764810456758825936 n 3 - 71034560194292428996270569121491060912590082 n 2 + 332487940414430914252979376259145605949082839 n - 664868188357252409486709571582730819348869788 n + 477754291216482694679555269855753286529458400) a(n - 7)/((n + 1) n (n - 1) (n - 2) %1) 3 %1 := 241085330738483432247606488232496516398107 n 2 - 3046457570007701888795053916389984897796060 n + 12727193124852547487834402787656089422830411 n - 17589763246583488220785042747391382999042042 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10, a(5) = 27, a(6) = 79, a(7) = 239] Just for fun, a(1000), equals 1729792209381059928071124060305298341618770164870061397841331259541710014323\ 357313925081560921726983769208839820740181801865438228324781028993051751\ 160314152762941145116412706451577260113752197413314467523109029746967829\ 440415801993563422338079707389273616524317519040876734050013809194789285\ 739036994265972782133563655483329307037437393007391151593529587660988736\ 656552806098026681569884480838425265176592325727898763439222359881254975\ 407691488624100062123165056714498442795461762279185147354971129361104234\ 182598477436298966531068595940750413684619747444838241178 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 4, 10, 27, 79, 239, 742, 2342, 7501, 24322, 79727, 263798, 879925, 2955636, 9988566, 33938122, 115863636, 397251260, 1367284685, 4722485625, 16363037475, 56861697469, 198122610163, 692013701387, 2422592718149, 8498823135604, 29873434453117, 105196539032193, 371069619633133, 1310991084282103, 4638650063641446, 16435844728096486, 58313005463102576, 207147291604186192, 736722082236767156, 2623078403671799534, 9349249042055618914, 33356210640023134646, 119121348535404147533, 425789918193784437369, 1523264828201501616806, 5453965707439294162606, 19542953334297404315155, 70079939349292318378500, 251483140364404936133265, 903072189981734143515570, 3245055431115988570856067, 11667994212821767188487695, 41979164937092517231451686, 151120924258440914901766092, 544325806427680364413384797, 1961677517235054104257676838, 7073299152195619708879725154, 25517256775703045185914236534, 92099176884662821991199933789, 332567639351059334958568202833, 1201433521735294739342538701758, 4342185955668442471211110370834, 15700002912477308731007093757741, 56789457837306948460039518906414, 205497578227996943686707391817077, 743894384407241183673748378012276, 2693867819276988067415501157377958, 9758808472691803516362914643357302, 35364548723392729815227180396300332, 128199335214825881195622699003423784, 464884924156076347837965999509481568, 1686332014830058929275540484056004830, 6118919113291798635346783883491686670, 22209387468940503692152823325254390390, 80635277436896724643802730279342286860, 292844292501304898728828152456413742908, 1063820366583308242368415457106771305714, 3865596390491811695045008196055728672676, 14050064645194819461967520936907949945506, 51079990084645243843986671657513425809952, 185750983983940791404452366441502931778246, 675641871665525621091802178742647256533252, 2458127942431201102948528205114994067894237, 8945247908371475936306717837367395965962509, 32559506752682482539908748267386174903565574, 118538232583905709270434444574255820953091080, 431650265144414364675125026186816011881820878, 1572158504888526184282172363398102247342820251, 5727291592000771702921962673411548429124612273, 20868386680776642238798153231243335776669476887, 76052432214650632760456555339338671777008000847, 277217149878699850676351908051500294138131021999, 1010666801921236763512076496359115497304499062359, 3685318711537710103558094883889386722621094214384, 13440627138200097142364209825874772071143250571433, 49027503857774871358237107592531386298421853031127, 178868634506053369933736434403219413566002979385265, 652681349550071761285241705338159876594183934599765, 2381986563475448173779647984770950595816228444383795, 8694548663598212376469665801376237649081867214235155, 31741174360604512151820416888552132555038311140226466, 115895287437686570794991825099295571627103326535630556, 423227683511107274019560390904173534391267332599632110, 1545776027325456888623689796760500490105469015897152725, 5646534966595902907933065813363953980532581679378804025, 20629049121120300813793810183653426298810809311970729009, 75376670036139611035946788584614380443011033795081655433, 275457171287633255580181694770803174994921111766705555125, 1006768223120490917149966277126949827118182023140139781915, 3680121086101267771995101634600877839031843717615388509060, 13453982347735163170952373941403061958598444332732580984482, 49192025692355239948949300993666261324148334849879090996472, 179884054773124611778070174527145809504335929976756502372990, 657875579146475410510367796941051727712217418404761866274412, 2406284926729584142390185073467014219459467917501320581840205, 8802410182436750518472952071599927774159195434011508860400093, 32203755665133813993528373180687675722385476703089884736407726, 117831372964949881535769478021047532065398116172572047462917296, 431185349329368825410482027823848168298733495720905102195260262, 1578028589314008360107536053500192784513340554834401544464095507, 5775807923625897050099774616971875574679361458301591826553351389, 21142524031332175119399742701854581006544261629174263305512886015, 77400964123512591466928220970407365222964636341727377715856905385] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H H H H + HH HH HH HH HH + HH HH HH HH HH + H H H H H H H H H H + H H H H H H H H H H 1.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 1+ H H H H H H H H + H H H H H H + H H H H H H + H H H H H H + H H H H H H 0.5+ HH H H H H HH + H H H H H H + H H H H H H +H HH HH H +H HH HH H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+*-+-+-+-+-++-+-+-+-*+-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 5 4 2 2 P(x) x + P(x) x + P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence 5 a(n) = 1/20 (5483321745761692629154053764810456758825936 n 4 - 107242566323822704692204511711156433619864678 n 3 + 932936394089247532276679481829728806893454807 n 2 - 4475850240656363222517866297863276130500791388 n + 11432336984329082960333534428241635534502575061 n - 11981628935569213384384583065109742970251559830) a(n - 1)/((n + 1) %1) 6 - 1/16 (21933286983046770516616215059241827035303744 n 5 - 543839208220945341507928575432537290607770708 n 4 + 5575062036448110791168661913092801332492331992 n 3 - 29963903134430476464454115975713151923302299023 n 2 + 88037590954429496455068426666140859845164606788 n - 131996049371239468461872545267816184589028709385 n + 76930657583545876086661472738444760948494415900) a(n - 2)/(n (n + 1) %1) 7 + 1/64 (65799860949140311549848645177725481105911232 n 6 - 1974420421782164543261636140533972996722689384 n 5 + 23879263756829823089374428497016527499643263028 n 4 - 152780810711526582116986138006676779662273014010 n 3 + 562577350730416554147339073654394927218433561555 n 2 - 1198234593732908055162294457315267572173159318606 n + 1372629755952343710874031490020600374628730741165 n - 654829981137629738999251840340059577389825490820) a(n - 3)/((n - 1) n 8 (n + 1) %1) + 1/128 (307066017762654787232627010829385578494252416 n 7 - 9132126337156641771565979000847360221435248600 n 6 + 119794144546419500243764846213627276986511542080 n 5 - 898914250417405815404381379076633603092800672506 n 4 + 4190153337753580883321101881756805755319158084926 n 3 - 12343416518776377281097694499663825071630263182053 n 2 + 22312920525555024749757307838579418541801668937797 n - 22516534813597583069956584877931855147979317064372 n + 9667337459113593718987779814152925359120387738240) a(n - 4)/((n + 1) n (n - 1) (n - 2) %1) - 3/1280 ( 8 1995929115457256117012075570391006260212640704 n 7 - 66160898749049139986480168949214865802672575128 n 6 + 944310749413307850571882099694108165012215566788 n 5 - 7576650019854270338341880537521566895311867084110 n 4 + 37348420581258791724985555041094653377748227118571 n 3 - 115694256273647880446574943914250719574202607915492 n 2 + 219598671463362405551986361534172484244537191551677 n - 233036557407332560260942387395131352681899602275130 n + 105571579875577293855058598063461913575848026461800) a(n - 5)/((n + 1) n (n - 1) (n - 2) %1) - 3/256 (n - 5) ( 7 87733147932187082066464860236967308141214976 n 6 - 2590659207919704770707684675036094964874237305 n 5 + 32147309501415073816648519304905164557734178362 n 4 - 216893696995080841868571630070204532057594170509 n 3 + 857333356054355764640236335052303996739253914740 n 2 - 1980000074632472405300458060503872262865026509454 n + 2465744364562580837234378976399267416098643558964 n - 1272295578861168876730230484336777256468936052240) a(n - 6)/((n + 1) n (n - 1) (n - 2) %1) - 9/5120 (n - 5) (n - 6) (3 n - 19) (3 n - 17) ( 4 5483321745761692629154053764810456758825936 n 3 - 71034560194292428996270569121491060912590082 n 2 + 332487940414430914252979376259145605949082839 n - 664868188357252409486709571582730819348869788 n + 477754291216482694679555269855753286529458400) a(n - 7)/((n + 1) n (n - 1) (n - 2) %1) 3 %1 := 241085330738483432247606488232496516398107 n 2 - 3046457570007701888795053916389984897796060 n + 12727193124852547487834402787656089422830411 n - 17589763246583488220785042747391382999042042 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10, a(5) = 27, a(6) = 79, a(7) = 239] Just for fun, a(1000), equals 1729792209381059928071124060305298341618770164870061397841331259541710014323\ 357313925081560921726983769208839820740181801865438228324781028993051751\ 160314152762941145116412706451577260113752197413314467523109029746967829\ 440415801993563422338079707389273616524317519040876734050013809194789285\ 739036994265972782133563655483329307037437393007391151593529587660988736\ 656552806098026681569884480838425265176592325727898763439222359881254975\ 407691488624100062123165056714498442795461762279185147354971129361104234\ 182598477436298966531068595940750413684619747444838241178 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 4, 10, 27, 79, 239, 742, 2342, 7501, 24322, 79727, 263798, 879925, 2955636, 9988566, 33938122, 115863636, 397251260, 1367284685, 4722485625, 16363037475, 56861697469, 198122610163, 692013701387, 2422592718149, 8498823135604, 29873434453117, 105196539032193, 371069619633133, 1310991084282103, 4638650063641446, 16435844728096486, 58313005463102576, 207147291604186192, 736722082236767156, 2623078403671799534, 9349249042055618914, 33356210640023134646, 119121348535404147533, 425789918193784437369, 1523264828201501616806, 5453965707439294162606, 19542953334297404315155, 70079939349292318378500, 251483140364404936133265, 903072189981734143515570, 3245055431115988570856067, 11667994212821767188487695, 41979164937092517231451686, 151120924258440914901766092, 544325806427680364413384797, 1961677517235054104257676838, 7073299152195619708879725154, 25517256775703045185914236534, 92099176884662821991199933789, 332567639351059334958568202833, 1201433521735294739342538701758, 4342185955668442471211110370834, 15700002912477308731007093757741, 56789457837306948460039518906414, 205497578227996943686707391817077, 743894384407241183673748378012276, 2693867819276988067415501157377958, 9758808472691803516362914643357302, 35364548723392729815227180396300332, 128199335214825881195622699003423784, 464884924156076347837965999509481568, 1686332014830058929275540484056004830, 6118919113291798635346783883491686670, 22209387468940503692152823325254390390, 80635277436896724643802730279342286860, 292844292501304898728828152456413742908, 1063820366583308242368415457106771305714, 3865596390491811695045008196055728672676, 14050064645194819461967520936907949945506, 51079990084645243843986671657513425809952, 185750983983940791404452366441502931778246, 675641871665525621091802178742647256533252, 2458127942431201102948528205114994067894237, 8945247908371475936306717837367395965962509, 32559506752682482539908748267386174903565574, 118538232583905709270434444574255820953091080, 431650265144414364675125026186816011881820878, 1572158504888526184282172363398102247342820251, 5727291592000771702921962673411548429124612273, 20868386680776642238798153231243335776669476887, 76052432214650632760456555339338671777008000847, 277217149878699850676351908051500294138131021999, 1010666801921236763512076496359115497304499062359, 3685318711537710103558094883889386722621094214384, 13440627138200097142364209825874772071143250571433, 49027503857774871358237107592531386298421853031127, 178868634506053369933736434403219413566002979385265, 652681349550071761285241705338159876594183934599765, 2381986563475448173779647984770950595816228444383795, 8694548663598212376469665801376237649081867214235155, 31741174360604512151820416888552132555038311140226466, 115895287437686570794991825099295571627103326535630556, 423227683511107274019560390904173534391267332599632110, 1545776027325456888623689796760500490105469015897152725, 5646534966595902907933065813363953980532581679378804025, 20629049121120300813793810183653426298810809311970729009, 75376670036139611035946788584614380443011033795081655433, 275457171287633255580181694770803174994921111766705555125, 1006768223120490917149966277126949827118182023140139781915, 3680121086101267771995101634600877839031843717615388509060, 13453982347735163170952373941403061958598444332732580984482, 49192025692355239948949300993666261324148334849879090996472, 179884054773124611778070174527145809504335929976756502372990, 657875579146475410510367796941051727712217418404761866274412, 2406284926729584142390185073467014219459467917501320581840205, 8802410182436750518472952071599927774159195434011508860400093, 32203755665133813993528373180687675722385476703089884736407726, 117831372964949881535769478021047532065398116172572047462917296, 431185349329368825410482027823848168298733495720905102195260262, 1578028589314008360107536053500192784513340554834401544464095507, 5775807923625897050099774616971875574679361458301591826553351389, 21142524031332175119399742701854581006544261629174263305512886015, 77400964123512591466928220970407365222964636341727377715856905385] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {4 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {4 r + 3} 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 HH H 2+ H H H H H H H + HH HH HH H H HH + H H H H H H H H H H 1.5+ HH HH HH HH HH HH HH HH HH HH + H H H H H H H H H H + H H H H H H H H H H 1+ H H H H H H + H H + H H + H H 0.5+ H H + H H +H H -*-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 1, 2, 4, 9, 21, 56, 153, 431, 1242, 3653, 10900, 32951, 100677, 310361, 963994, 3013849, 9476385, 29946599, 95059390, 302959071, 969042643, 3109749638, 10009333286, 32305175654, 104527356748, 338995431373, 1101763782673, 3587954098469, 11706013424892, 38257889077380, 125237446875715, 410586434740126, 1348007125934635, 4431599905945442, 14587349050029742, 48073880424258808, 158610137455528653, 523860761822081818, 1731969200711308911, 5731678433027473070, 18985429851710999670, 62941499651272933117, 208840231399831659026, 693482123206750160540, 2304544469729403911070, 7663891150341468350335, 25504369044704164718436, 84931405013646205562403, 283008004630089871330714, 943614794750057875597466, 3148081397213296492826784, 10508543683853278185635709, 35097422265856187832006214, 117283053804611042091304776, 392115850071028908309113322, 1311610214559356891931730023, 4389338037463581911691126463, 14695693381921347977674846388, 49223362519397332007107517880, 164943906596401229905495838452, 552941327738200246854329914751, 1854359213512015578721872741977, 6221215718633576460283984442285, 20879400639961756985235803047786, 70099868352686978542485415026421, 235433383944946002828300885764400, 790980957199407989819220362269888, 2658317340622034401897325255986479, 8936887569634717945274684743607051, 30053875047023617772717358679027683, 101098701177013807715197048875791088, 340187191193866803730057566153697601, 1145022796819428460934902186951067445, 3855056598577611523001269718389824369, 12982688041798562782326424616713762153, 43733339121136763977937608663800856862, 147357363472447907259801274076517270107, 496637358420392902821488914759205425443, 1674219993163000228452735359963342727171, 5645320706725626262324874011749539081789, 19039920417921607104232727675782468030404, 64230248889283359072159561733415065380048, 216725337052120228443969054620668658257585, 731430556193186096254033376561741304947804, 2469037275350893978654531021546266740747593, 8336259196620446694324159440360862424545513, 28151513101402570325403739047860660680569533, 95086151305229291344979590107240110758184128, 321229839340784957754327171656730007676596196, 1085414777978068700255545750603913464502411198, 3668217120329264698542020759926494521863594112, 12399154268512508025340980366060941932519535748, 41918443584456097051270978258397396497657711409, 141740079685772048222564103909637672906642389753, 479350370371417491404233268542407129651995220305, 1621380014144211491738554641675212552071217265236, 5485123952856254376756779895493368891536955959644, 18559083849647465279939819681629817784071427474714, 62804924218196036567183485909682515340235233262070, 212567366037167209497520095027404287532861064665589, 719554872410637812937996386694119947617095126550304, 2436096088431949332831077451931369304132492339475731, 8248725534819553017264633664813846016899877827727667, 27934444790826308291449307265447091044477186758312575, 94613439276417985507162540789464076527556606333733882, 320497086881010434886991106477160822783916609342400622, 1085807210715985714611052978431703497464419556726199989, 3679066793737067848620669021844207595142083943655538250, 12467457796633394846087438091997185993610264561685303544, 42254446702104697791086263258171442123604657503712420470, 143225462148753596348912471962530967606477925833013330360, 485534835300505888557408632349237927694345068210241070108, 1646159752429307976614123655326305266541418667844435637207, 5581797606084049973627725445349550794271091845536548080399, 18928919900726687924471080408629675512160340188312558742206, 64198719949901926521167264930582803252949652486525306380006, 217758370174405296408943617818049461703579454624457274133901, 738704061145066609932266826661827556448472035998386489557859, 2506181181219284425664495576642160757469257208283871644544119, 8503545090744510961492124037954424310626143224043902833097517] ------------------------------------------------------------ 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 , {4 r + 3} 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 + HH HH + H H + HH HH 2+ H H H H + HHH HHH H H + HH H HH H HH HH + H HH H HH H H 1+ H H H H H + HH H HH HH + H HH H H +HH HHH HH -*-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 3 2 2 2 P(x) x - P(x) x + 2 P(x) x - 3 P(x) x + P(x) + 2 x - 1 = 0 The sequence a(n) satisfies the linear recurrence a(n) = 2 (3 n + 2) a(n - 1) (9 n - 4) a(n - 2) 4 a(n - 3) 4 (n - 3) a(n - 4) -------------------- - ------------------ + ---------- + ------------------ n + 2 n + 2 n + 2 n + 2 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 5, a(4) = 14] Just for fun, a(1000), equals 2065221682188448617501334235840658436696171690594546644140031438025641280355\ 676504552593268774503564957349753065795082361069953501573040074860513711\ 867477133103083603128754625180095306260838676975086502007732879810267596\ 087157441605492446260901138702422965826921847355032301507210210963058443\ 952988855230594231727030924975595801592696189036204436971542375237345594\ 043984279966370792137459754669153115748019086762242776073757490776884673\ 418210091095653011350130289467571347114567006856772800762074246037831535\ 3489423007903433685720275687676482555880 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 5, 14, 41, 123, 375, 1158, 3615, 11393, 36209, 115940, 373709, 1211740, 3949969, 12937612, 42558745, 140547051, 465799527, 1548766044, 5164917003, 17271369744, 57900615135, 194558333460, 655168354935, 2210681734671, 7473262879749, 25307621729472, 85842204632337, 291618279724185, 992094024337947, 3379702654932858, 11528112138291315, 39369615715500587, 134604371184959873, 460708363966718072, 1578475739751182237, 5413427707160837308, 18582696963832198465, 63845155625044698748, 219539221807749890617, 755517683845219865457, 2602016074484282826507, 8967959528352172617432, 30930151593603845634735, 106748669698000019848819, 368657401696543608647821, 1273949679722490633670918, 4404938482116230579039653, 15239675402252181761096045, 52753403493960712601354663, 182707037196308257988799392, 633113682229092670087362971, 2194935772117091131566477846, 7613215192774614003216585075, 26418821139644084770420257336, 91717252197364867528700060139, 318547702562894266066370322255, 1106821657331884458031767864921, 3847288305221337530802574661544, 13378277190572350525405762438581, 46538110109324271720495793467546, 161947913145387324176565899044749, 563761254138077183575779185349960, 1963196444427337537305295879724229, 6838747547494128564451174060047291, 23830297751484238783258093091612211, 83065069665552651848499204242076636, 289627383930338405176180658368319511, 1010158093188359543721472837681758630, 3524228664962953973558887675029591087, 12298734522621057727647797592569399808, 42931408542012623500141191464202776439, 149901191920682382087783494819521565619, 523536867453235663305902831381318540685, 1828937238938433136557644200269473589024, 6390824726153783996234026242487700329641, 22336694787644717177309792430468546678753, 78087629429197369130961102047730369260643, 273051404198482459786293323530963023986610, 954999286925287616275556444613800008783563, 3340841210760345860643933760392106273547667, 11689624290004023660136106297860958977106985, 40910525592305504646287965977918493749643008, 143204703456396587407004550216698975100152757, 501377941708902702208806394810543749813415578, 1755726845057982626294005647545286145956675453, 6149369566882676508635972133519364873013989992, 21541917156346196102930497775753976547118269125, 75477320578693733531602585851932668733716932537, 264499754447175744182613982879499947317330422343, 927062707981081861244457146911120866732281020488, 3249873114626000175225777456506375086527401434923, 11394509090582608274402525778938320526742975842898, 39957220184702845378289618102174961317477899301115, 140140578663817078127608647937260044631721841990976, 491586718019714562101287797850570657413555351080259, 1724656513359998286937081017070287716476052329889421, 6051597138330428910319859598589704026250436609557189, 21237385558575102757838116792590809978818461967533732, 74540877670475171067312926675557444581501306558148929, 261667121272297523981433534662207483590329317986234122, 918679121324637609490296414713902650427376936437706409, 3225799985306012911392886273830777422377117505479487232, 11328406393384778085832807285843053822977052819007316577, 39788441446065100365074689858703712863777568154770824285, 139765735388204825217597452433168958770941400459944400971, 491019979752005394760087115157756961810976406269481867536, 1725247038550656232652234412569642142565856826521005176719, 6062561155737741977721072423838856100525774651788571485257, 21306531403478731678382192313070793571110903229501917282977, 74889381822079005666670282543514960816341596256027617781114, 263255661152340577258659472284891194402962641542624258110969, 925516809736267635581399768085944716188405806603253427729605, 3254162076110712750037567747114124674943779464820967847400299, 11443042325253980143152637879400958429587303716789736513651928, 40243012710198190588643933567803479250295095405262255311973679, 141542005419379388925221533234815452298776519875666374990222826, 497880733073961310138975419272146612176437498841799329358284463, 1751498104699634602675654459460685106592666002428888038324222848] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {4 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {4 r + 3} 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 H 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 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 4 6 3 6 3 5 3 4 2 5 2 4 5 P(x) x - 2 P(x) x + P(x) x - P(x) x + 2 P(x) x - 2 P(x) x - P(x) x 2 3 4 2 2 3 2 2 + 2 P(x) x + P(x) x - P(x) x - P(x) x + 3 P(x) x - 3 P(x) x - x + P(x) + 2 x - 1 = 0 For the sake of the OEIS are the first , 120, terms [1, 1, 2, 4, 10, 26, 72, 202, 577, 1665, 4861, 14329, 42617, 127713, 385280, 1169048, 3565503, 10924453, 33610071, 103790391, 321598658, 999564782, 3115544971, 9736073477, 30498077025, 95746257319, 301205088491, 949361560599, 2997600957164, 9480654223112, 30031662585640, 95269853091506, 302641752209190, 962642145725154, 3065716186721282, 9774645714914614, 31199338113974051, 99687421915037167, 318832948718898167, 1020687454619926339, 3270465200541699661, 10488062481209034941, 33661466590613445465, 108120247779276908217, 347538160702203101481, 1117906855946257598223, 3598350426167350753015, 11590011381727619998177, 37353855569392786648289, 120461271541869667088291, 388695739371287485038264, 1254910974989715456209930, 4053665041883764565191618, 13101050059713988755106284, 42362308161257520675840391, 137044235258472585733678461, 443549769416045070811210466, 1436208607047181137750999278, 4652429172810661367162363832, 15077276951297803563022049088, 48881111371771339070466025090, 158536275147644906687296509608, 514375547163841185337920313960, 1669517513556690160162492823476, 5420705227604158395371171907890, 17606381866173018689761329391128, 57204412272986012411150089839189, 185921574971776831193912209016659, 604459003192430342414236942292950, 1965788686608418495244377081422392, 6394933240908412333634963148632232, 20809461360409074435617579639027508, 67734181197411425215942500245661593, 220533146493102091915982151047321975, 718216957942964298945467992749958145, 2339646275226360027647679014039486525, 7623503552426977603615182169608415898, 24846548618023165226919618975153341652, 80999418292369962588650625080659767059, 264118914454023377088635050112419102743, 861422843761958174929452897094706886734, 2810154103172978082534114993972948476322, 9169347663093268300318304738328579255531, 29925337487003555811221499344017028148125, 97685438257707369964485181658757436397819, 318939767032543686802049516464866714169633, 1041534294487968504552680270179552317608943, 3401908202060700868523593240287208918559651, 11113576438956219854818903549102775690461224, 36313282584984639278797677107208633348877170, 118674070269387104700181445948564162549198935, 387902989481857258160162929900701110852649473, 1268135701349117253501592715601348803730264653, 4146503651994308824614574558784530043718377827, 13560339161078999787089662214185005525857390183, 44353687544259872756948958699609394338031931577, 145096903718256582376382668982765097672348251193, 474738423394908138574429338321193824867013492251, 1553520842421069319998005851109759955612455904078, 5084461061397340373394910482180324399833744056116, 16643192033440998857044527887480289407150289701190, 54486753747194805783547916063442574957201268076210, 178404845300574208609393319723104261023965758452882, 584228290112102434495465777206621792020262705024696, 1913452147925472449149722906503166861099293521735173, 6267734679904389559055187533534992416696759262148061, 20533382593734216589197318974407527398752086777640016, 67276942026884230520891697275870869212523046417060506, 220458483259296096968826286697171885264831824990706441, 722505609858655658110537580906600605299628520743029031, 2368146156142110504746987047105337958259715858858638691, 7762966503800228188030365257965086785147593471952726467, 25450594874574406042302866938432009372566555159671781295, 83448452680379082704698872445883720173124156473433572913, 273645238502288610499379980718998417280665138480263988098, 897441016430485934081860452331477069760768404499721462424, 2943550702195773040546689353756702182052601278209040849983, 9655703284038577259489977015300733791297753877585851015641, 31676873028409518968933686690893081384949348547042683280704, 103931198164137382626864139338562236822128102629920504674770, 341031156449218498871510448234202170778567244273152740383849] ------------------------------------------------------------ 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 , {4 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H H H H + HH HH HH HH HH + HH HH HH HH HH + H H H H H H H H H H + H H H H H H H H H H 1.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 1+ H H H H H H H H + H H H H H + H H H H H H + H H H H H H + H H H H H H 0.5+ HH H H H H HH + H H H H H H + H H H H H H +H HH HH 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 6 3 6 3 5 3 4 2 5 2 4 5 P(x) x - 2 P(x) x + P(x) x - P(x) x + 2 P(x) x - 2 P(x) x - P(x) x 2 3 4 2 2 3 2 2 + 2 P(x) x + P(x) x - P(x) x - P(x) x + 3 P(x) x - 3 P(x) x - x + P(x) + 2 x - 1 = 0 For the sake of the OEIS are the first , 120, terms [1, 1, 2, 4, 10, 26, 72, 202, 577, 1665, 4861, 14329, 42617, 127713, 385280, 1169048, 3565503, 10924453, 33610071, 103790391, 321598658, 999564782, 3115544971, 9736073477, 30498077025, 95746257319, 301205088491, 949361560599, 2997600957164, 9480654223112, 30031662585640, 95269853091506, 302641752209190, 962642145725154, 3065716186721282, 9774645714914614, 31199338113974051, 99687421915037167, 318832948718898167, 1020687454619926339, 3270465200541699661, 10488062481209034941, 33661466590613445465, 108120247779276908217, 347538160702203101481, 1117906855946257598223, 3598350426167350753015, 11590011381727619998177, 37353855569392786648289, 120461271541869667088291, 388695739371287485038264, 1254910974989715456209930, 4053665041883764565191618, 13101050059713988755106284, 42362308161257520675840391, 137044235258472585733678461, 443549769416045070811210466, 1436208607047181137750999278, 4652429172810661367162363832, 15077276951297803563022049088, 48881111371771339070466025090, 158536275147644906687296509608, 514375547163841185337920313960, 1669517513556690160162492823476, 5420705227604158395371171907890, 17606381866173018689761329391128, 57204412272986012411150089839189, 185921574971776831193912209016659, 604459003192430342414236942292950, 1965788686608418495244377081422392, 6394933240908412333634963148632232, 20809461360409074435617579639027508, 67734181197411425215942500245661593, 220533146493102091915982151047321975, 718216957942964298945467992749958145, 2339646275226360027647679014039486525, 7623503552426977603615182169608415898, 24846548618023165226919618975153341652, 80999418292369962588650625080659767059, 264118914454023377088635050112419102743, 861422843761958174929452897094706886734, 2810154103172978082534114993972948476322, 9169347663093268300318304738328579255531, 29925337487003555811221499344017028148125, 97685438257707369964485181658757436397819, 318939767032543686802049516464866714169633, 1041534294487968504552680270179552317608943, 3401908202060700868523593240287208918559651, 11113576438956219854818903549102775690461224, 36313282584984639278797677107208633348877170, 118674070269387104700181445948564162549198935, 387902989481857258160162929900701110852649473, 1268135701349117253501592715601348803730264653, 4146503651994308824614574558784530043718377827, 13560339161078999787089662214185005525857390183, 44353687544259872756948958699609394338031931577, 145096903718256582376382668982765097672348251193, 474738423394908138574429338321193824867013492251, 1553520842421069319998005851109759955612455904078, 5084461061397340373394910482180324399833744056116, 16643192033440998857044527887480289407150289701190, 54486753747194805783547916063442574957201268076210, 178404845300574208609393319723104261023965758452882, 584228290112102434495465777206621792020262705024696, 1913452147925472449149722906503166861099293521735173, 6267734679904389559055187533534992416696759262148061, 20533382593734216589197318974407527398752086777640016, 67276942026884230520891697275870869212523046417060506, 220458483259296096968826286697171885264831824990706441, 722505609858655658110537580906600605299628520743029031, 2368146156142110504746987047105337958259715858858638691, 7762966503800228188030365257965086785147593471952726467, 25450594874574406042302866938432009372566555159671781295, 83448452680379082704698872445883720173124156473433572913, 273645238502288610499379980718998417280665138480263988098, 897441016430485934081860452331477069760768404499721462424, 2943550702195773040546689353756702182052601278209040849983, 9655703284038577259489977015300733791297753877585851015641, 31676873028409518968933686690893081384949348547042683280704, 103931198164137382626864139338562236822128102629920504674770, 341031156449218498871510448234202170778567244273152740383849] ------------------------------------------------------------ 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 , {4 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {4 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H + HH + HH + H H + H H 1.5+ H H + H H + H H + H H + H H 1+ H H H H H H H H + H H H H H H H H + H H H H H H H H H H H H H H + H H H H H H H H H H H H H H + H H H H H H H H H H H H H H 0.5+ HH H HH H H H H H H H H H H HH + H H H H H H H H H H H H H H + H H H H H H H H H H H H H H +H HH HH HH HH HH HH H +H HH HH HH HH HH HH H -*-+-+-+-+*-+-+-+-++-+-+-+-+*-+-+-+-+*-+-+-+-+-*+-+-+-+-*+-+-+-+-*+-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 1, 2, 4, 9, 20, 51, 129, 338, 898, 2438, 6686, 18565, 51994, 146805, 417196, 1192669, 3426879, 9891454, 28666550, 83382997, 243337942, 712271590, 2090601103, 6151616825, 18143182847, 53625079188, 158812616432, 471198989313, 1400463616947, 4169065251960, 12429705343174, 37110623106695, 110946729780127, 332105719001436, 995298477192432, 2986190467189683, 8968981344980565, 26965374377334973, 81149447077474076, 244433163590415915, 736904622605868552, 2223419858189721514, 6713892554676856904, 20288724947758650074, 61354770399337453788, 185670023883567406044, 562241150915702084763, 1703645025052323490875, 5165355396343563020062, 15670236384503257726234, 47565859819065394445288, 144460926740709030309133, 438967101364977820910146, 1334540772677226875073335, 4059216596654911240740672, 12352524594552785031107030, 37606710957103558828505989, 114541919443840354060723105, 349017118954026073134184727, 1063913131728593428678586868, 3244419976159692166861581272, 9897693090749735831495303845, 30205896843179139288610039125, 92215808504439913539996110835, 281624344500510858743794660521, 860362897751059043295478787142, 2629271950694914242031907163625, 8037621967470715497756160817689, 24578418344142500074926240218809, 75181467230859296087250909819347, 230035334254245467592931827630911, 704047108666561491112464262548805, 2155405428271244583067212101755263, 6600443392357396651849023774868930, 20217668085965513448039061679700426, 61944089632422386503074850746074118, 189835184314921514404203468099590023, 581914034929152506562740476661495160, 1784200334263870989801727006637990724, 5471778770635709911214416198495492700, 16784605333192736389042738570614466064, 51497847470578574950775839186142370924, 158037478231571359730314210875342464003, 485089629641062670362465346054053359088, 1489267331993300531296709555704451334536, 4573093399241775494592682604530759767584, 14045339660247194551878972170636170833108, 43145676747333063340135780553800379396954, 132563313052477003625413064122016069408213, 407369640941878003261508808256678096379758, 1252078323506989949657102466036578905993339, 3849020236589281058698047891000449080074649, 11834315431646854045362270005611340874402370, 36392238896014882312685927438476555550296604, 111929762938272612676214393835700163908326874, 344311955316565526495807743589786649305366712, 1059319361555440972858491540528943334717241550, 3259632418273496485744007090349436423364019615, 10031731990280778143249720628123806663286333165, 30877881127151922973004940279978553119217908073, 95056556940647205941421953487801329916823541223, 292670173323441955726748163043181072733777017746, 901229625459163828713432201689432267125614393535, 2775568249707779571391890480979021943277980417056, 8549224040483639391549216138722511296973191006420, 26336540882184607808423962337609291323979724692145, 81142233100691853860871725696569974542758668581823, 250028973003095589906124122528943743947983578529658, 770527024552237367358456443803501668323358710429631, 2374863188460738695086870612706844462334145468649899, 7320513570327260801076598714325767056943667197608436, 22568142464240779965716651789814618505842835531742785, 69582574080744771418487360069112382513944473788498599, 214562935481266752088022235270994753553129114961524219, 661694609082086744569371497571176820479983876685388443, 2040837106379895743934552670351775513637273184650857452, 6295150667383007970557804812870466341727137559830328848, 19420042120464537535383154241599987627070427010584169562, 59915568974038790126690692495244803994732009179587423457, 184873191683467717698976410247407441975164409666140109877] ------------------------------------------------------------ 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 , {4 r + 3} 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 HH + H H + H H 2+ H H H + H H HH + H H H H + HH HH 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 2 3 2 2 2 P(x) x + P(x) x - P(x) x - P(x) x + P(x) + x - 1 = 0 The sequence a(n) satisfies the linear recurrence (7 n - 2) a(n - 1) 2 (7 n - 11) a(n - 2) 3 (n - 5) a(n - 3) a(n) = ------------------ - --------------------- + ------------------ n + 1 n + 1 n + 1 (13 n - 38) a(n - 4) 4 (n - 5) a(n - 5) 4 (n - 5) a(n - 6) + -------------------- - ------------------ - ------------------ n + 1 n + 1 n + 1 subject to the initial conditions [a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 9, a(5) = 22, a(6) = 58] Just for fun, a(1000), equals 6525149745809409102504669569729393322980149298842960359850236964400658318408\ 013826477583147950746669527794860024655989142255351657825100726414773329\ 839763363043775654682660563759430749417798978319402555674702776455053605\ 441761437247128565351644499339672192157636901011126366385343764784699930\ 974440199918391812718834873391986403943617149849152968898888686129223202\ 144310784812735827312469989738840263156150364459028620047401503439798314\ 224481739110656619675692099634372108436295617694518767177675943722779358\ 601261001239330370750104920348604225238 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 4, 9, 22, 58, 162, 472, 1417, 4346, 13541, 42703, 135975, 436447, 1410453, 4585129, 14983225, 49189487, 162161018, 536602981, 1781730516, 5934484456, 19822667713, 66386397560, 222866783598, 749863202633, 2528243365967, 8540687713678, 28903289929368, 97978560545911, 332657925567127, 1131112230726800, 3851378786888838, 13130900500974095, 44823782865072205, 153189438835505586, 524117214482335990, 1795074029102305741, 6154143210994296802, 21118486496767963700, 72535088368974760785, 249347641048447916354, 857861191454892651979, 2953707223142403529383, 10177511868465185972287, 35093411156859262518973, 121089441129720622705344, 418091584285123474023319, 1444473303440791121751760, 4993553690119654541143814, 17272763913696396844951966, 59780045695524582226354398, 207006443311568524458751093, 717193134039877518783669070, 2486021667239444504721535038, 8621494221936844895155311337, 29913121836045760167080518636, 103833047115703387820515632776, 360576619317278546525266413528, 1252683621201972126311179588970, 4353726888408703745607252799121, 15137399394961688866521620165128, 52650959202122313807218903993214, 183198161633147055129810629735545, 637662461827959228336242820033970, 2220295813750366637195570144143784, 7733509378645116892677691144500816, 26945355396385593748680180320209520, 93913636689099123706598982615174761, 327421306350270470782960617061627156, 1141865652297390733034851778990241036, 3983357530422255633655227233399700649, 13899729040377750120778988929929750406, 48515760590191571526927610034962827686, 169385273009239080235348902320211367272, 591536709131983932980395848916971170024, 2066322353626420486467486120125337585635, 7219746549973755279124264011260535496276, 25231938965091108946667516319366719431023, 88202620156617516179443089947889077509189, 308398333890993715781442827750488451666179, 1078548836774416388450149038781214513972321, 3772789094500468348599969182310009230402604, 13200121010518562536542290758560076447934243, 46193811407320511871294119620927620450872870, 161688110281930157168552994618268178249316862, 566055159941756783841648958833040573413452553, 1982092173572766865095401206186051147806029290, 6941790055339217531279016650993170448276796382, 24316429818375503990668943499413833270187104805, 85193623296062258950620048226585695905062564599, 298532486982919773592300388753566807758863159210, 1046289063812888149604763601011773423078876321954, 3667631957440726237178384299360594450632859895599, 12858556997210222485959896222804313313927310625528, 45088900048771185827025372845401548555295093979344, 158130815525095641062304298903290945183466347294733, 554665854929764310863008821662003106520594950363360, 1945866465795143676761106339785011110766558276467255, 6827472945695338611006893742966430527061537506498383, 23959127831735156135286257276752547590396121140942181, 84090092889330563055767960902685612720140503238055761, 295175464322888072105174826166088199319364635807083135, 1036277557264558720669805667120468978876552757496611183, 3638573885568822094677570352403431950145657962345475141, 12777457850912145989787297031536177329622146033369915669, 44876066789161290363706749956800268320568319331478898518, 157630818582213161206016809562801691557354297670022390873, 553761129735175021112213222244189962917957622811038755956, 1945619007116039020210377329218876835230192340732584456012, 6836694254038299786391428562732280756108067788811189520506, 24026283508895328507262925781183095061923388707257119774238, 84445828181533902281942444574359543063262149522594009792881, 296838391020690802381194560096918871711806583516447769896974, 1043545367786151762985877300472331936560511898099670949308491, 3669029025181287679823239839597430767027692139833833138876159, 12901454642110706835924187272356596458231728289902272754436279, 45370454052236204961238722800356548045967212118208624691634189, 159570901403528110133740509739725117552680364878515017124319615, 561280083110346236308733118577412825476308555962856596184015441] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {4 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {4 r + 3} 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 + HHH H HH HHH + 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 H + HH HH 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 4 4 4 3 3 4 4 2 3 3 3 2 P(x) x - 2 P(x) x + 2 P(x) x + P(x) x - 4 P(x) x + 2 P(x) x 2 3 2 2 3 2 2 + P(x) x - 4 P(x) x + P(x) x + 4 P(x) x - 2 P(x) - P(x) x + 2 P(x) - x = 0 For the sake of the OEIS are the first , 120, terms [1, 1, 2, 4, 9, 21, 53, 140, 385, 1084, 3108, 9028, 26515, 78596, 234862, 706748, 2139868, 6514225, 19926509, 61216972, 188798485, 584320967, 1814232241, 5649404516, 17639071677, 55210216539, 173201602706, 544502925760, 1715138869382, 5412410572426, 17108895736914, 54168339558636, 171758522816836, 545382415711243, 1734036771311080, 5520229531455232, 17594124846501067, 56138701206452978, 179314675696266504, 573329992646791220, 1834877862110685718, 5877643405134422962, 18844048470325901931, 60464814722698386516, 194165732400124041196, 623977133721781100912, 2006674181922883422117, 6457789983729889356584, 20795886015039691768261, 67010945487371226507975, 216061762518730885690798, 697049504703317772423936, 2250055092630733048526799, 7267036324369847040762038, 23482671219612803335768943, 75919870774727088096835800, 245568956556491176915713173, 794683442850095341854153750, 2572827039414681689358509685, 8333282990001233503122435416, 27002532436254140853782958271, 87532576718289868825370335144, 283861237611942226372407606483, 920890970725853110669665995300, 2988621502091113743772757364331, 9702625540041064818837707211450, 31510737867006218089527880149923, 102370383364571105401551769009628, 332684253202905291732648960287176, 1081504197926761927423512630163321, 3516885985142792976201024942858582, 11439807472692653799775483180338236, 37222529044581762376855855242522348, 121148017452607264407378705473780927, 394408888809455721982302005498777983, 1284380888489810896978181022314636320, 4183643481708341946035788656287319225, 13630953881063123763231682580569376562, 44422780952467985218691643180469201453, 144807289843303014532934929167906678672, 472147476876072601708134621938437088717, 1539802282626351830684385964501996698739, 5022845837327172046410865166671829479315, 16388152472947611208183365126658222580436, 53481445546070720692297131031587913655533, 174568986151497196500381062331129296154099, 569927674387167171301934622232354775774102, 1861054412752850207700113118431079043003584, 6078313554696263352222121310156462114656330, 19855916259234066725304226271718356637958535, 64875054131232596863450420643029179363557724, 212004327491787144890994502779301038187547168, 692929726309648868889431839015749395321229052, 2265215219167677224866567174289958542455876044, 7406345207505320979824477237100523853312373345, 24219829012476112085714395167922002726412772704, 79215346683806425129170550782120481025098848445, 259129734518339939929433509303150882611201235579, 847800019777873547129014812651174049533570116086, 2774191699061309428049176726671259577555404681396, 9079147083795743541951515083231760393418860668087, 29717883697775974883212101742150204817201648738269, 97286749100974615183996618198711676784890640653947, 318530680235310065195236472047453516044766405146892, 1043060324245307149715885366186699794795371651775927, 3416071961213760193457083311787204501659197046087346, 11189299632159149713833183193691285728501452281180794, 36655235762442181064158342593828142331262722769987520, 120095101440713392236333327222909802537415487977381692, 393522622230439282603278357249752567681912569004979638, 1289639263637439311034683014363971247731623561536953801, 4226880307306862743093227848318161595937299961232151300, 13855553040376720913540630411446563754613535168303793351, 45423340509384646832743479130956991230075538452209863360, 148930849116856765550242310620233080415987379159470375516, 488359654372952085966273950152151294212165052929845645048, 1601561254929153256940542909309153211655680182018898412638, 5252851984490128150657656176819479209985172172215802822476, 17230338006564418975779314747188626326893824517679557793173, 56524752032119404866085084905828981169928810374072143502068, 185450923481704160552386993480812973548510672749282425234409] ------------------------------------------------------------ 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 , {4 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H H H H + HH HH HH HH HH + HH HH HH HH HH + H H H H H H H H H H + H H H H H H H H H H 1.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 1+ H H H H H H H H + H H H H H H + H H H H H H + H H H H H H + H H H H H H 0.5+ HH H H H H HH + H H H H H H + H H H H H H +H HH HH 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 4 4 3 3 4 4 2 3 3 3 2 P(x) x - 2 P(x) x + 2 P(x) x + P(x) x - 4 P(x) x + 2 P(x) x 2 3 2 2 3 2 2 + P(x) x - 4 P(x) x + P(x) x + 4 P(x) x - 2 P(x) - P(x) x + 2 P(x) - x = 0 For the sake of the OEIS are the first , 120, terms [1, 1, 2, 4, 9, 21, 53, 140, 385, 1084, 3108, 9028, 26515, 78596, 234862, 706748, 2139868, 6514225, 19926509, 61216972, 188798485, 584320967, 1814232241, 5649404516, 17639071677, 55210216539, 173201602706, 544502925760, 1715138869382, 5412410572426, 17108895736914, 54168339558636, 171758522816836, 545382415711243, 1734036771311080, 5520229531455232, 17594124846501067, 56138701206452978, 179314675696266504, 573329992646791220, 1834877862110685718, 5877643405134422962, 18844048470325901931, 60464814722698386516, 194165732400124041196, 623977133721781100912, 2006674181922883422117, 6457789983729889356584, 20795886015039691768261, 67010945487371226507975, 216061762518730885690798, 697049504703317772423936, 2250055092630733048526799, 7267036324369847040762038, 23482671219612803335768943, 75919870774727088096835800, 245568956556491176915713173, 794683442850095341854153750, 2572827039414681689358509685, 8333282990001233503122435416, 27002532436254140853782958271, 87532576718289868825370335144, 283861237611942226372407606483, 920890970725853110669665995300, 2988621502091113743772757364331, 9702625540041064818837707211450, 31510737867006218089527880149923, 102370383364571105401551769009628, 332684253202905291732648960287176, 1081504197926761927423512630163321, 3516885985142792976201024942858582, 11439807472692653799775483180338236, 37222529044581762376855855242522348, 121148017452607264407378705473780927, 394408888809455721982302005498777983, 1284380888489810896978181022314636320, 4183643481708341946035788656287319225, 13630953881063123763231682580569376562, 44422780952467985218691643180469201453, 144807289843303014532934929167906678672, 472147476876072601708134621938437088717, 1539802282626351830684385964501996698739, 5022845837327172046410865166671829479315, 16388152472947611208183365126658222580436, 53481445546070720692297131031587913655533, 174568986151497196500381062331129296154099, 569927674387167171301934622232354775774102, 1861054412752850207700113118431079043003584, 6078313554696263352222121310156462114656330, 19855916259234066725304226271718356637958535, 64875054131232596863450420643029179363557724, 212004327491787144890994502779301038187547168, 692929726309648868889431839015749395321229052, 2265215219167677224866567174289958542455876044, 7406345207505320979824477237100523853312373345, 24219829012476112085714395167922002726412772704, 79215346683806425129170550782120481025098848445, 259129734518339939929433509303150882611201235579, 847800019777873547129014812651174049533570116086, 2774191699061309428049176726671259577555404681396, 9079147083795743541951515083231760393418860668087, 29717883697775974883212101742150204817201648738269, 97286749100974615183996618198711676784890640653947, 318530680235310065195236472047453516044766405146892, 1043060324245307149715885366186699794795371651775927, 3416071961213760193457083311787204501659197046087346, 11189299632159149713833183193691285728501452281180794, 36655235762442181064158342593828142331262722769987520, 120095101440713392236333327222909802537415487977381692, 393522622230439282603278357249752567681912569004979638, 1289639263637439311034683014363971247731623561536953801, 4226880307306862743093227848318161595937299961232151300, 13855553040376720913540630411446563754613535168303793351, 45423340509384646832743479130956991230075538452209863360, 148930849116856765550242310620233080415987379159470375516, 488359654372952085966273950152151294212165052929845645048, 1601561254929153256940542909309153211655680182018898412638, 5252851984490128150657656176819479209985172172215802822476, 17230338006564418975779314747188626326893824517679557793173, 56524752032119404866085084905828981169928810374072143502068, 185450923481704160552386993480812973548510672749282425234409] ------------------------------------------------------------ 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 , {4 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {4 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H H + HH HH HH + HH HH HH + 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 1+ H H H H H H H H + H H H H H H H H + H H H H H H H H H H + H H H H H H H H H H + H H H H H H H H H H 0.5+ HH H H H H H H H H HH + H H H H H H H H H H + H H H H H H H H H H +H HH HH HH HH H +H HH HH HH HH H -*-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-+*-+-+-+-+-++-+-+-+-*+-+-+-+-*+-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 1, 2, 4, 9, 20, 49, 124, 325, 864, 2334, 6374, 17601, 49046, 137798, 389861, 1109853, 3176673, 9136501, 26391426, 76531091, 222711979, 650192799, 1903762186, 5589201853, 16449790444, 48524625574, 143443897510, 424868657700, 1260728126710, 3747395846162, 11156588649954, 33264713654691, 99322442609705, 296952099043895, 888930992435029, 2664172218237838, 7993583720906572, 24009344723439380, 72186360408128099, 217242259857891300, 654376449570243649, 1972815551464099797, 5952554335730598195, 17974718312134006235, 54318467779758338221, 164265159780659551931, 497098763052510184921, 1505312762917367896779, 4561271996804187261889, 13829592645246892804153, 41955283914992473489290, 127352672470780737718505, 386780345428542307437893, 1175295269960764806337849, 3573120243507540663234911, 10868223454881377923832898, 33072910221801342114195561, 100689042368294916855384101, 306677086609913793571534926, 934465930890992285186340032, 2848542179688330754372987297, 8686667106213958170917698137, 26500228448089906924561775351, 80873604449814033338421674942, 246899260647271565258594128600, 754021755697448756921131051238, 2303533652353097397183344715977, 7039592842013231887835291517390, 21519823280537742786421162575421, 65805789002986905712757331289757, 201288965467350338932488702133236, 615889337847456633490709107393535, 1884988853325061437410878208902643, 5770785634844080572390874285342610, 17671684845120849957674057820020026, 54129593365756227171245198481153168, 165845011501673400645189916780232558, 508250794203834485137405470321168432, 1557969657104592439058053784593508917, 4776860663991765341161344852047396535, 14649617030406992017487069063948767469, 44937370043447334343955675133860352198, 137874631565354818814512124422190451992, 423110833514722989827295988541058416816, 1298717842882179721530789202939780080519, 3987165300254365043505020040635941095642, 12243354082032087209243874952548752689356, 37602900476202313330266857445072745995625, 115511479499686600795155936908935163135802, 354903248831165769616112623082834658615056, 1090621495348970407428630853970726400242145, 3352089926264538691916203799845180954672480, 10304647355750632381849425294222918101256382, 31682895210101624080397585194164325709864718, 97429232423096102235046365511678144549928621, 299657314053413350619624550680796939046640492, 921786195328066418913715515955569601732983703, 2835984238050147696659200542130015143345265301, 8726585412771017366340214808716808771912862201, 26856564485978825746707447182255100896620382249, 82664844780472140863617795384667941250164984202, 254480365197539648379265581372041303042935377889, 783518957551896743401405514528279387023482469142, 2412711289906614679172549154593840261743943855611, 7430545009189695948047198965805818078787488570361, 22887287593394874992388528189754073067661385498837, 70505864247933018134449198087046183345720426952477, 217226273180156626691643759233980672123885005693447, 669352099344383847387074973172018058296158409808751, 2062771271940777756728557043040590062627913359129386, 6357709945464567007931984071999778204046196419910778, 19597586476522068956811741816303803337595462089092784, 60416531406844935397636012543583816152330698553428718, 186277074025772895144710080815614837028627029572780952, 574397540793543474119430127588099182803697552645370739, 1771390976643077401026905578201321018504154297992952348, 5463414425393044562263287741350572818561690613996756903, 16852367165327902234237394857979042259533103611092167872, 51988099461070711524527489173840491324339953800111725027, 160395603757481051790961966334362321460316471180307254419] ------------------------------------------------------------ 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 , {4 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 4+ H + HH + HH HH + H H + H H 3+ H H + H H + H H + H H + H H 2+ H H H + HH H H + H H H H + HH H HH HH + H H H H 1+ H H H H H H + H H H H H H H H + H H H H H H H H + HH HH HH HH HH HH HH HH +H HH HH HH H -*-+-+-+-++-+-+-+-+*-+-+-+-+*-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-*+-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 2 2 P(x) x + P(x) x - P(x) + 1 = 0 The sequence a(n) satisfies the linear recurrence (2 n + 1) a(n - 1) 3 (n - 1) a(n - 2) a(n) = ------------------ + ------------------ n + 2 n + 2 subject to the initial conditions [a(1) = 1, a(2) = 2] Just for fun, a(1000), equals 6113276597677185504356904766347702612354574971465608501154658923615549572276\ 696990107943183029388971134843974419526697509491161299179783336635341085\ 951686706984893024288224904033483357682387428696232998837169493679543025\ 183026827681506943202019217503411671799888555630269575896218409691887122\ 093560366976953000654462569519440192461932987949316582488835710972517056\ 497520791693103466653417515528995390532609891053412869321468991714009337\ 7138459245912955193770266157466468457 For the sake of the OEIS here are the first, 120, terms. [1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, 1697385471211, 4859761676391, 13933569346707, 40002464776083, 114988706524270, 330931069469828, 953467954114363, 2750016719520991, 7939655757745265, 22944749046030949, 66368199913921497, 192137918101841817, 556704809728838604, 1614282136160911722, 4684478925507420069, 13603677110519480289, 39532221379621112004, 114956499435014161638, 334496473194459009429, 973899740488107474693, 2837208756709314025578, 8270140811590103129028, 24119587499879368045581, 70380687801729972163737, 205473381836953330090977, 600161698382141668958313, 1753816895177229449263803, 5127391665653918424581931, 14996791899280244858336604, 43881711243248048262611670, 128453535912993825479057919, 376166554620363320971336899, 1101997131244113831001323618, 3229547920421385142120565580, 9468017265749942384739441267, 27766917351255946264000229811, 81459755507915876737297376646, 239056762740830735069669439852, 701774105036927170410592656651, 2060763101398061220299787957807, 6053261625552368838017538638577, 17785981695172350686294020499397, 52274487460035748810950928411209, 153681622703766437645990598724233, 451929928113276686826984901736388, 1329334277731700374912787442584082, 3911184337415864255099077969308357, 11510402374965653734436362305721089, 33882709435158403490429948661355518, 99762777233730236158474945885114348, 293804991106867190838370294149325217, 865461205861621792586606565768282577, 2549948950073051466077548390833960154, 7514646250637159480132421134685515996, 22150145406114764734833589779994282345, 65303054248346999524711654923215773701, 192564948449128362785882746541078077821, 567944426681696509718034692302003744197, 1675395722976475387857861526496400455935, 4943221572052274428484817274841589781103, 14587540897567180436019575590444202957764, 43055804394719442101962182766220627765254, 127103430617648266466982424978107271745123, 375281510930976756310181851730346874521559, 1108229819877900763405338193186744667723583, 3273209089476438052473101825635320104642103, 9669131152389329200998265687814683780583133, 28567321136213468215221364999058944720713501, 84414794291793480358891042199686850901302514, 249478578991224378680142561460010030467811580, 737415571391164350797051905752637361193303669, 2179989657182268706949944711706683431675573969, 6445526902441229646310051859066530999375612263, 19060008608601035820122512539133495685366451171, 56369902000490155161466142878589232802345778151, 166736186990532204812594206164411016589993382759, 493253027399423689823559267775695878392662135604, 1459371636273993893967616514973002909449910595158, 4318344244242469812948502806410363711951592224347, 12779763960737611807939007796892996356569096666335, 37825235742770534271327510185799474362588759112692, 111967696262665849903769091543433376818806152053282, 331478378609143895971053565694243287254152991197499, 981449894682881651766048471053798615807057357319435, 2906234450266204129212174643462658253439431024500886, 8606803606778108365401717262737377633765146862076508, 25491831573907963336583054018749373611049855273869763, 75510488025438261304679120183518573236529303339176631, 223696821203921358836246695367291099954466200770942903, 662762421725143382344788171386348329048337151787800671, 1963815645947208854505196881559285819544210551279398181] ------------------------------------------------------------ ------------------------------------------------------------ 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 , {4 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {4 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H H H + HH HH HH HH + HH HH HH HH + H H H H H H H H + H H H H H H H H 1.5+ H H H H H H H H + H H H H H H H H + H H H H H H H H + H H H H H H H H + H H H H H H H 1+ H H H H H H H H + H H H H H H H + H H H H H H H H + H H H H H H H H + H H H H H H H H 0.5+ HH H HH H H H H HH + H H H H H H H H + H H H H H H H H +H HH HH HH H +H HH HH HH H -*-+-+-+-+*-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-+-++-+-+-+-*+-+-+-+-++-+-+-+-*- 2 4 6 8 10 12 14 16 The ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 4 5 3 5 3 4 3 3 2 4 4 2 2 P(x) x - 2 P(x) x + 4 P(x) x - 2 P(x) x + P(x) x - P(x) x + P(x) x 3 2 2 + 2 P(x) x - 2 P(x) x + 2 P(x) x + x - P(x) - x + 1 = 0 For the sake of the OEIS are the first , 120, terms [1, 1, 2, 4, 9, 20, 47, 112, 275, 683, 1722, 4380, 11250, 29107, 75841, 198756, 523661, 1386071, 3684274, 9829976, 26317521, 70678992, 190360281, 514042932, 1391461399, 3774953888, 10262438555, 27952747536, 76274050688, 208476097147, 570711518509, 1564645319952, 4295521133073, 11808142946791, 32499838135808, 89554072141056, 247039879658423, 682184000343592, 1885670312386915, 5217212320117236, 14447744506553077, 40043503161716727, 111075297719117474, 308347485329231096, 856615606584321052, 2381443617391520367, 6625068250672795467, 18442675713858225932, 51372364223000812653, 143184641919279199293, 399313897476728476660, 1114227667430607616200, 3110755921210085186390, 8689241712807776375621, 24283634332338439919479, 67897487705674778021036, 189930490463005807764801, 531532421840130305497226, 1488169453542808720107867, 4168274963131514190391520, 11679810009035444508637828, 32740478446568324659897685, 91811849348039084132182401, 257556084912918321884698652, 722768786708997225878736517, 2028975519039031805216279865, 5697700606496456945708060716, 16005291692714660934103652624, 44974324292996507046720912327, 126415082774876716959017568146, 355436974325453130570126736717, 999659741229489313873866350988, 2812316934678703434873060266179, 7913989905595534981028565977129, 22276283317583023972982781593686, 62719552191857271516010967181528, 176633560157432673334126049813980, 497566058543407063057528698542649, 1401950962211536459711820186160865, 3951089342497924313585055505981340, 11137823328977508870741580387040687, 31403701032446696201469371450454363, 88563761253536556928437749240636324, 249818005345887351102985942920087940, 704825683937177753779270504630625945, 1988968559467329274949126656195367508, 5613843593797830651754745540201647747, 15848090549637144249333376761725594296, 44748238069568667315603943686629071115, 126373343339369448799722417150661283638, 356955262075339311896230008433993025215, 1008437936260749808290799278494239679772, 2849443073184570546553956388687826821530, 8052757503743489669625773646847614438977, 22761534460754068052924897567123311391267, 64347137500988761275029485022028479856364, 181939189085584230174796349381212301511309, 514506891401588975073190189333640431564803, 1455200014151145064446716782909091563386390, 4116417461764728160399275349459757736793716, 11646088194930405657818141241467853166146117, 32953642844965109731607254726626558856318594, 93258465893096655998860356484099501532142489, 263957135644661093636211537990758859050984936, 747201450596530008156105433802902435148909521, 2115436793185589224674313331173165187480788332, 5989897189284214975670679484081256425305357171, 16962685083346475552795743693620041059624733676, 48042403361271504011668849205875194533549912100, 136084528096777332102318803213143311031170736881, 385518932928815054562333357828141088002400446125, 1092281712230939810470294869070249437662890119908, 3095100024063830665905539795034946495122330450819, 8771318822830995440070783671021519671654328939595, 24860188575205471964998525811609000971896505860300, 70468074687271138793218970498675251763133883381680, 199768971553872666890033036378551070270217681725740, 566383375740667791343375791568868622553067977081385, 1605975860898650863605070748649522382236821164278605, 4554207516640755773772681706434224162924197515657820, 12916092882188711272045772172576587293099351667055815] ------------------------------------------------------------ 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 , {4 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {4 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 6+ H + HHHH + H H 5+ H HH HH + HH H HH H + H HH H H + HH HHH HH 4+ H H H + H H + HH HH 3+ H H + HH HH + HH HH 2+ HH HH H + H H HHH + 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 ordinary generating function of the sequence a(n), let's call it, P(x), satisfies the algebraic equation 4 5 3 5 3 4 3 3 2 4 4 2 2 P(x) x - 2 P(x) x + 4 P(x) x - 2 P(x) x + P(x) x - P(x) x + P(x) x 3 2 2 + 2 P(x) x - 2 P(x) x + 2 P(x) x + x - P(x) - x + 1 = 0 For the sake of the OEIS are the first , 120, terms [1, 1, 2, 4, 9, 20, 47, 112, 275, 683, 1722, 4380, 11250, 29107, 75841, 198756, 523661, 1386071, 3684274, 9829976, 26317521, 70678992, 190360281, 514042932, 1391461399, 3774953888, 10262438555, 27952747536, 76274050688, 208476097147, 570711518509, 1564645319952, 4295521133073, 11808142946791, 32499838135808, 89554072141056, 247039879658423, 682184000343592, 1885670312386915, 5217212320117236, 14447744506553077, 40043503161716727, 111075297719117474, 308347485329231096, 856615606584321052, 2381443617391520367, 6625068250672795467, 18442675713858225932, 51372364223000812653, 143184641919279199293, 399313897476728476660, 1114227667430607616200, 3110755921210085186390, 8689241712807776375621, 24283634332338439919479, 67897487705674778021036, 189930490463005807764801, 531532421840130305497226, 1488169453542808720107867, 4168274963131514190391520, 11679810009035444508637828, 32740478446568324659897685, 91811849348039084132182401, 257556084912918321884698652, 722768786708997225878736517, 2028975519039031805216279865, 5697700606496456945708060716, 16005291692714660934103652624, 44974324292996507046720912327, 126415082774876716959017568146, 355436974325453130570126736717, 999659741229489313873866350988, 2812316934678703434873060266179, 7913989905595534981028565977129, 22276283317583023972982781593686, 62719552191857271516010967181528, 176633560157432673334126049813980, 497566058543407063057528698542649, 1401950962211536459711820186160865, 3951089342497924313585055505981340, 11137823328977508870741580387040687, 31403701032446696201469371450454363, 88563761253536556928437749240636324, 249818005345887351102985942920087940, 704825683937177753779270504630625945, 1988968559467329274949126656195367508, 5613843593797830651754745540201647747, 15848090549637144249333376761725594296, 44748238069568667315603943686629071115, 126373343339369448799722417150661283638, 356955262075339311896230008433993025215, 1008437936260749808290799278494239679772, 2849443073184570546553956388687826821530, 8052757503743489669625773646847614438977, 22761534460754068052924897567123311391267, 64347137500988761275029485022028479856364, 181939189085584230174796349381212301511309, 514506891401588975073190189333640431564803, 1455200014151145064446716782909091563386390, 4116417461764728160399275349459757736793716, 11646088194930405657818141241467853166146117, 32953642844965109731607254726626558856318594, 93258465893096655998860356484099501532142489, 263957135644661093636211537990758859050984936, 747201450596530008156105433802902435148909521, 2115436793185589224674313331173165187480788332, 5989897189284214975670679484081256425305357171, 16962685083346475552795743693620041059624733676, 48042403361271504011668849205875194533549912100, 136084528096777332102318803213143311031170736881, 385518932928815054562333357828141088002400446125, 1092281712230939810470294869070249437662890119908, 3095100024063830665905539795034946495122330450819, 8771318822830995440070783671021519671654328939595, 24860188575205471964998525811609000971896505860300, 70468074687271138793218970498675251763133883381680, 199768971553872666890033036378551070270217681725740, 566383375740667791343375791568868622553067977081385, 1605975860898650863605070748649522382236821164278605, 4554207516640755773772681706434224162924197515657820, 12916092882188711272045772172576587293099351667055815] ------------------------------------------------------------ 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 , {4 r + 3} The height of a valley can't be (for a non-negative integer r) equal to som\ ething of the form , {4 r + 3} No upward-run can be in (for a non-negative integer r) equal to something\ of the form , {4 r + 3} No downward-run can be in (for a non-negative integer r) equal to somethi\ ng of the form , {4 r + 3} To make it crystal clear here is such a path of semi-length 8 2+ H H H H H + HH HH HH HH HH + HH HH HH HH HH + H H H H H H H H H H + H H H H H H H H H H 1.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 1+ H H H H H H H H + H H H H H + H H H H H H + H H H H H H + H H H H H H 0.5+ HH H H H H HH + H H H H H H + H H H H H H +H HH HH H +H HH HH H -*-+-+-+-++-+-+-+-+*-+-+-+-++-+-+-+-++-+-+-+-+-++-+-+-+-++-+-+-+-*+-+-+-+-*- 2 4 6 8 10 12 14 16 The first , 120, terms of the sequence are [1, 1, 2, 4, 9, 19, 44, 102, 246, 595, 1466, 3630, 9094, 22915, 58190, 148504, 381098, 982132, 2541878, 6602105, 17206555, 44978453, 117906749, 309866843, 816285752, 2155031525, 5700947061, 15109743814, 40117266373, 106688682982, 284167368266, 757979280281, 2024561329842, 5414529439364, 14498253947714, 38865759716112, 104301087705078, 280192426045652, 753437789047297, 2027874332835392, 5462834192460053, 14728563263693917, 39742156013786729, 107318733647545245, 290013465066371626, 784270096538816860, 2122292523422168422, 5746784807667470792, 15570890908333331344, 42214361443952723009, 114513117074888847944, 310805775879041397169, 844020250070389474300, 2293180231366995504876, 6233573688450317084653, 16952824308719376058503, 46126015468925332310435, 125557297805530493892757, 341919356331669622069906, 931504601208005392959059, 2538750915013312148964126, 6921869576807954290422260, 18879464932183215639571037, 51512647007332404173561463, 140601891234881972560527564, 383898998286220811094721754, 1048544654314897018784624651, 2864816587667050099263767293, 7829655276681676390603268912, 21405261758343511929102907830, 58536512535076601862140118351, 160124584253073652330030657669, 438137743537754337103464089196, 1199172193751117110366972712110, 3282974728549995019952281607773, 8990123069700842083812158165341, 24624813900593230127645638633420, 67466273886749837123638484119325, 184886103928947081509972921434645, 506784149395932908073455107460367, 1389442264874654433918686893375663, 3810257536592862478723705915380588, 10451104686021703740747628654839044, 28672257420998027551002070464683370, 78677627611399202104857997707060491, 215937583350664774119306190324505247, 592776300122952519201709443207999449, 1627560388055913040702629181869650074, 4469564513839935758253294368356345356, 12276464856362270894676066534095845040, 33725602007775208505569996158581818313, 92666482760324876480156826996139932984, 254659919077912439089752415597780049669, 699957837255767973734377422523363512812, 1924221212851129416112410146137861501537, 5290643079475500280165094919566993097903, 14548922766869274797526248959410889229758, 40014806928556700038681720824708320639703, 110071978287846643431414139990812738340876, 302829140188154190084329889015592167091977, 833263052665161177833662799239044958631716, 2293131288748437722195599521186380222288711, 6311561899175088334663971185016451844045928, 17374196741879254882370650413167978081864584, 47833422244587987889459955592735378852521709, 131709135453306752483887522687630947647249249, 362707887268458521881129883485945113088426893, 998972914739159105159235193243809318236792144, 2751724980379886967691887993998895767710712635, 7580711217344079722857216410422003791480177949, 20886589566248578524173237832870911973637063022, 57554174870399032139383478917879255056883753008, 158612328651468985022460428466950003116198538847, 437166600636981684905168735426117171346070831964, 1205052781232264063693263761335191182757774705072, 3322105230566113717123322003657876175345226836785, 9159422708146785552051827880421837450244629912386, 25256282264035038093084535561185560223219561629961, 69649269797546869316215393420966335538759501454124, 192091778829652234542202975532928825924838902356502, 529840697830894179198069571026996009684587677877261] This concludes this exciting paper with its, 16, theorems that took, 8054.403, to generate. --------------------------------------------------