Systematic Enumeration of Two-Dimensional Lattice Walks Confined to the Firs\ t Quadrant with, 5, Short Steps With Holonomic Complexity Not Exceeding, 16 By Shalosh B. Ekhad In this article we will attempt to enumerate, in the context of the Holonomi\ c Ansatz, lattice walks in the Two Dimensional Non-negative Square Lattice N^2 that st\ art at the origin, [0,0], (in other words an infinite chessboard, starting at the bottom-left corner) where N={0,1,2, ...} is the set of non-negative integers. We will try to do it for all possible subsets with, 5, elements of the 2^8=2\ 56 set of king-steps {[+-1,+-1], and [1,0],[0,1],[0,1],[1,0]}, and try and find holonomic representations, i.e., linear recurrence equation\ s with polynomial coefficients whose complexity is <=, 16, , in other words, the order of the recurrence plus the highest degree of the c\ oefficients of the recurrence, in the discrete variable, n, is <=, 16 We will try to enumerate both those walks that start and return to the origi\ n, and the total number of walks, (still starting at the origin) regardless of final destination. We will discard obviously trivial cases, where the enumerating sequence is e\ ventually a constant. This work reproduces, from the perspective of Doron Zeilberger's semi-rigoro\ us and non-rigorous philosophy, interesting, "rigorous" investigations by smart humans like Marni Mishna, M\ ireille Bousquet-Melou, Manuel Kauers, Christoph Koutschan my beloved master Dr. Z. , and other people. ------------------------------------------------------------------------- Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1]} We have Theorem , 1, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) f(n) - -------------- + f(n + 2) = 0 4 + n subject to the initial conditions f(1) = 0, f(2) = 1 the recurrence in Maple input notation is -4*(1+n)/(4+n)*f(n)+f(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845] We also have the following theorem. Theorem , 1A, : Let g(n) be the number of n-step walks, starting at [0,0], al\ ways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) g(n) 2 g(1 + n) - -------------- - ---------- + g(n + 2) = 0 3 + n 3 + n subject to the initial conditions g(1) = 1, g(2) = 2 the recurrence in Maple input notation is -4*(1+n)/(3+n)*g(n)-2/(3+n)*g(1+n)+g(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520] Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [0, -1], [1, -1]} This case is trivial Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [0, -1], [1, 0]} Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [0, -1], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, -1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 0]} Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1]} We have Theorem , 2, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) f(n) - -------------- + f(n + 2) = 0 4 + n subject to the initial conditions f(1) = 0, f(2) = 1 the recurrence in Maple input notation is -4*(1+n)/(4+n)*f(n)+f(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845] We also have the following theorem. Theorem , 2A, : Let g(n) be the number of n-step walks, starting at [0,0], al\ ways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 55 (1 + n) g(n) (-14 + n) g(1 + n) (25 + 7 n) g(n + 2) --------------- - ------------------ - ------------------- + g(3 + n) = 0 4 + n 4 + n 4 + n subject to the initial conditions g(1) = 2, g(2) = 7, g(3) = 23 the recurrence in Maple input notation is 55*(1+n)/(4+n)*g(n)-(-14+n)/(4+n)*g(1+n)-(25+7*n)/(4+n)*g(n+2)+g(3+n) = 0 For the sake of the OEIS, here are the first 31 terms [1, 2, 7, 23, 85, 314, 1207, 4682, 18493, 73688, 296671, 1202849, 4910689, 20158436, 83169871, 344628527, 1433631973, 5984532728, 25060514887, 105240685511, 443102517025, 1870054761632, 7909539602647, 33521289826778, 142330494633985, 605375433105734, 2578988979186127, 11003364185437517, 47012236086805213, 201125820203417690, 861513024099550879] Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [1, -1], [1, 1]} We have Theorem , 3, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 0], [-1, 1], [1, -1], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 192 (15 n + 98) (n + 5) (3 + n) (n + 2) (1 + n) f(n) ---------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 2 160 (n + 5) (4 + n) (3 + n) (15 n + 137 n + 256) f(n + 2) + ---------------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 3 2 (n + 5) (465 n + 7658 n + 41256 n + 72640) f(4 + n) - ----------------------------------------------------- + f(n + 6) = 0 2 (n + 7) (15 n + 68) (n + 8) subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 0, f(4) = 6, f(5) = 0, f(6) = 55 the recurrence in Maple input notation is 192*(15*n+98)*(n+5)*(3+n)*(n+2)*(1+n)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n)+160*(n +5)*(4+n)*(3+n)*(15*n^2+137*n+256)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n+2)-(n+5)*( 465*n^3+7658*n^2+41256*n+72640)/(n+7)/(15*n+68)/(n+8)^2*f(4+n)+f(n+6) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 6, 0, 55, 0, 644, 0, 8694, 0, 128964, 0, 2045901, 0, 34136960, 0, 592493044, 0, 10614366568, 0, 195164993478, 0, 3667395504304, 0, 70199379387700 , 0, 1365217425954360, 0, 26918993235702735] Invesigating the set of steps, {[-1, -1], [-1, 0], [-1, 1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [0, -1], [0, 1], [1, -1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [0, -1], [0, 1], [1, 0]} Invesigating the set of steps, {[-1, -1], [-1, 0], [0, -1], [0, 1], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [0, -1], [1, -1], [1, 0]} We have Theorem , 4, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 0], [0, -1], [1, -1], [1, 0]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) f(n) - -------------- + f(n + 2) = 0 4 + n subject to the initial conditions f(1) = 0, f(2) = 1 the recurrence in Maple input notation is -4*(1+n)/(4+n)*f(n)+f(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845] We also have the following theorem. Theorem , 4A, : Let g(n) be the number of n-step walks, starting at [0,0], al\ ways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[-1, -1], [-1, 0], [0, -1], [1, -1], [1, 0]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) g(n) 2 g(1 + n) - -------------- - ---------- + g(n + 2) = 0 3 + n 3 + n subject to the initial conditions g(1) = 1, g(2) = 2 the recurrence in Maple input notation is -4*(1+n)/(3+n)*g(n)-2/(3+n)*g(1+n)+g(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520] Invesigating the set of steps, {[-1, -1], [-1, 0], [0, -1], [1, -1], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [0, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [0, 1], [1, -1], [1, 0]} We have Theorem , 5, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 0], [0, 1], [1, -1], [1, 0]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 2 48 (4 + n) (3 + n) (n + 2) (1 + n) (12 n + 128 n + 337) f(n) - ------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 16 (n + 2) (3 + n) (4 + n) (84 n + 1196 n + 5565 n + 8446) f(1 + n) - --------------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 4 3 2 24 (3 + n) (4 + n) (36 n + 676 n + 4721 n + 14536 n + 16652) f(n + 2) - ------------------------------------------------------------------------ (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 4 (4 + n) (2 n + 11) (12 n + 170 n + 799 n + 1242) f(3 + n) - ------------------------------------------------------------- (n + 8) (n + 7) (n + 6) %1 3 2 (4 + n) (12 n + 212 n + 1197 n + 2161) f(4 + n) + ------------------------------------------------- + f(n + 5) = 0 (n + 7) (n + 8) %1 2 %1 := 12 n + 104 n + 221 subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 3, f(4) = 4, f(5) = 20 the recurrence in Maple input notation is -48*(4+n)*(3+n)*(n+2)*(1+n)*(12*n^2+128*n+337)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+ 104*n+221)*f(n)-16*(n+2)*(3+n)*(4+n)*(84*n^3+1196*n^2+5565*n+8446)/(n+5)/(n+8)/ (n+7)/(n+6)/(12*n^2+104*n+221)*f(1+n)-24*(3+n)*(4+n)*(36*n^4+676*n^3+4721*n^2+ 14536*n+16652)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(n+2)-4*(4+n)*(2*n+ 11)*(12*n^3+170*n^2+799*n+1242)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(3+n)+(4+ n)*(12*n^3+212*n^2+1197*n+2161)/(n+7)/(n+8)/(12*n^2+104*n+221)*f(4+n)+f(n+5) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 3, 4, 20, 65, 175, 742, 2604, 9072, 36960, 139392, 538824, 2198625, 8735727, 35456850, 146812952, 604215326, 2521642266, 10617725768, 44760668160, 190357768328, 813800295880, 3490232753680, 15055389124320, 65193213272800, 283254330047520, 1235731377864960, 5407996483238160, 23738772386435985] We also have the following theorem. Theorem , 5A, : Let g(n) be the number of n-step walks, starting at [0,0], al\ ways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[-1, -1], [-1, 0], [0, 1], [1, -1], [1, 0]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 3 - 1440 (4 + n) (3 + n) (n + 2) (1 + n) (9906709063384557513 n 2 + 179921041721431674932 n + 1056202767973180759464 n / 2 + 2026696297043592211005) g(n) / ((n + 10) (n + 7) %1 (9 + n) ) - 48 / 4 (n + 2) (3 + n) (4 + n) (686800557790311050802 n 3 2 + 14113888482339414079471 n + 102110475496866227482093 n / + 304856196348141757586304 n + 306332970239242314930300) g(1 + n) / ( / 2 (n + 10) (n + 7) %1 (9 + n) ) - 8 (3 + n) (4 + n) ( 5 4 2425527134980587222714 n + 54991475007847038819634 n 3 2 + 445212751232454631806213 n + 1477592501747295442522412 n / + 1328148852729749958161049 n - 1441594674757134217686390) g(n + 2) / ( / 2 6 (n + 10) (n + 7) %1 (9 + n) ) + 4 (4 + n) (216217887892500857028 n 5 4 + 14728276605276494774084 n + 337813725866661196673629 n 3 2 + 3647873296020920711705792 n + 20370316597509327509274743 n / + 57046726490253645695767052 n + 63474817532538354872781408) g(3 + n) / / 2 ((n + 10) (n + 7) %1 (9 + n) ) + 2 (233374792160368111213128576 5 6 + 609494596482947611405518 n + 36021489234571937948208 n 2 + 264397248793353820729011616 n + 128797047090164900223277758 n 3 4 + 35249916074668496115615839 n + 5904061575269706430579518 n 7 / 2 + 937942302194377689567 n ) g(4 + n) / ((n + 10) (n + 7) %1 (9 + n) ) + / 2 (-3036586476800367793950716 n + 3620857957580329082679404 n 3 4 + 2862025298278822490235485 n + 845763625692666715067785 n 5 6 + 125464317523984284027765 n + 9324758085365464693755 n 7 / - 8592701011595429714256624 + 276201465441869171226 n ) g(n + 5) / ( / 2 (n + 10) (n + 7) %1 (9 + n) ) - (73184329634315608682917584 2 + 73793776723356428744345864 n + 31073694742887838026075142 n 3 4 + 7083821354797352755827685 n + 945080998298895973248799 n 5 6 + 73963383515453609486133 n + 3159374786081020410739 n 7 / 2 + 57346436706807893574 n ) g(n + 6) / ((n + 10) (n + 7) %1 (9 + n) ) - ( / 6 5 22899812320112195370 n + 827494157198300205393 n 4 3 + 12591248064735141140688 n + 103518420241797662824541 n 2 + 484568275101179666003640 n + 1219181904569062963898692 n + 1280431639150021001185296) g(n + 7)/((n + 10) (9 + n) (n + 7) %1) + g(n + 8) = 0 3 2 %1 := 3086394193343080344 n + 65513399280235398443 n + 403497360223328115712 n + 768661105507998292164 subject to the initial conditions g(1) = 2, g(2) = 6, g(3) = 21, g(4) = 76, g(5) = 290, g(6) = 1148, g(7) = 4627, g(8) = 19038 the recurrence in Maple input notation is -1440*(4+n)*(3+n)*(n+2)*(1+n)*(9906709063384557513*n^3+179921041721431674932*n^ 2+1056202767973180759464*n+2026696297043592211005)/(n+10)/(n+7)/( 3086394193343080344*n^3+65513399280235398443*n^2+403497360223328115712*n+ 768661105507998292164)/(9+n)^2*g(n)-48*(n+2)*(3+n)*(4+n)*(686800557790311050802 *n^4+14113888482339414079471*n^3+102110475496866227482093*n^2+ 304856196348141757586304*n+306332970239242314930300)/(n+10)/(n+7)/( 3086394193343080344*n^3+65513399280235398443*n^2+403497360223328115712*n+ 768661105507998292164)/(9+n)^2*g(1+n)-8*(3+n)*(4+n)*(2425527134980587222714*n^5 +54991475007847038819634*n^4+445212751232454631806213*n^3+ 1477592501747295442522412*n^2+1328148852729749958161049*n-\ 1441594674757134217686390)/(n+10)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)/(9+n)^2 *g(n+2)+4*(4+n)*(216217887892500857028*n^6+14728276605276494774084*n^5+ 337813725866661196673629*n^4+3647873296020920711705792*n^3+ 20370316597509327509274743*n^2+57046726490253645695767052*n+ 63474817532538354872781408)/(n+10)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)/(9+n)^2 *g(3+n)+2*(233374792160368111213128576+609494596482947611405518*n^5+ 36021489234571937948208*n^6+264397248793353820729011616*n+ 128797047090164900223277758*n^2+35249916074668496115615839*n^3+ 5904061575269706430579518*n^4+937942302194377689567*n^7)/(n+10)/(n+7)/( 3086394193343080344*n^3+65513399280235398443*n^2+403497360223328115712*n+ 768661105507998292164)/(9+n)^2*g(4+n)+(-3036586476800367793950716*n+ 3620857957580329082679404*n^2+2862025298278822490235485*n^3+ 845763625692666715067785*n^4+125464317523984284027765*n^5+ 9324758085365464693755*n^6-8592701011595429714256624+276201465441869171226*n^7) /(n+10)/(n+7)/(3086394193343080344*n^3+65513399280235398443*n^2+ 403497360223328115712*n+768661105507998292164)/(9+n)^2*g(n+5)-( 73184329634315608682917584+73793776723356428744345864*n+ 31073694742887838026075142*n^2+7083821354797352755827685*n^3+ 945080998298895973248799*n^4+73963383515453609486133*n^5+3159374786081020410739 *n^6+57346436706807893574*n^7)/(n+10)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)/(9+n)^2 *g(n+6)-(22899812320112195370*n^6+827494157198300205393*n^5+ 12591248064735141140688*n^4+103518420241797662824541*n^3+ 484568275101179666003640*n^2+1219181904569062963898692*n+ 1280431639150021001185296)/(n+10)/(9+n)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)*g(n+7)+ g(n+8) = 0 For the sake of the OEIS, here are the first 31 terms [1, 2, 6, 21, 76, 290, 1148, 4627, 19038, 79554, 336112, 1435522, 6184704, 26838474, 117247440, 515135847, 2274656290, 10090187786, 44940868940, 200897459804, 901082056408, 4053912011322, 18289272082952, 82724956638634, 375064515961744, 1704237546984170, 7759645793395368, 35398085705004882, 161766978394221568, 740496668415453898, 3394960486231275480] Invesigating the set of steps, {[-1, -1], [-1, 0], [0, 1], [1, -1], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [0, 1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 0], [1, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 1], [0, -1], [0, 1], [1, -1]} Invesigating the set of steps, {[-1, -1], [-1, 1], [0, -1], [0, 1], [1, 0]} We have Theorem , 6, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 1], [0, -1], [0, 1], [1, 0]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 2 48 (4 + n) (3 + n) (n + 2) (1 + n) (12 n + 128 n + 337) f(n) - ------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 16 (n + 2) (3 + n) (4 + n) (84 n + 1196 n + 5565 n + 8446) f(1 + n) - --------------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 4 3 2 24 (3 + n) (4 + n) (36 n + 676 n + 4721 n + 14536 n + 16652) f(n + 2) - ------------------------------------------------------------------------ (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 4 (4 + n) (2 n + 11) (12 n + 170 n + 799 n + 1242) f(3 + n) - ------------------------------------------------------------- (n + 8) (n + 7) (n + 6) %1 3 2 (4 + n) (12 n + 212 n + 1197 n + 2161) f(4 + n) + ------------------------------------------------- + f(n + 5) = 0 (n + 7) (n + 8) %1 2 %1 := 12 n + 104 n + 221 subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 3, f(4) = 4, f(5) = 20 the recurrence in Maple input notation is -48*(4+n)*(3+n)*(n+2)*(1+n)*(12*n^2+128*n+337)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+ 104*n+221)*f(n)-16*(n+2)*(3+n)*(4+n)*(84*n^3+1196*n^2+5565*n+8446)/(n+5)/(n+8)/ (n+7)/(n+6)/(12*n^2+104*n+221)*f(1+n)-24*(3+n)*(4+n)*(36*n^4+676*n^3+4721*n^2+ 14536*n+16652)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(n+2)-4*(4+n)*(2*n+ 11)*(12*n^3+170*n^2+799*n+1242)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(3+n)+(4+ n)*(12*n^3+212*n^2+1197*n+2161)/(n+7)/(n+8)/(12*n^2+104*n+221)*f(4+n)+f(n+5) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 3, 4, 20, 65, 175, 742, 2604, 9072, 36960, 139392, 538824, 2198625, 8735727, 35456850, 146812952, 604215326, 2521642266, 10617725768, 44760668160, 190357768328, 813800295880, 3490232753680, 15055389124320, 65193213272800, 283254330047520, 1235731377864960, 5407996483238160, 23738772386435985] We also have the following theorem. Theorem , 6A, : Let g(n) be the number of n-step walks, starting at [0,0], al\ ways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[-1, -1], [-1, 1], [0, -1], [0, 1], [1, 0]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 3 - 1440 (4 + n) (3 + n) (n + 2) (1 + n) (9906709063384557513 n 2 + 179921041721431674932 n + 1056202767973180759464 n / 2 + 2026696297043592211005) g(n) / ((n + 10) (n + 7) %1 (9 + n) ) - 48 / 4 (n + 2) (3 + n) (4 + n) (686800557790311050802 n 3 2 + 14113888482339414079471 n + 102110475496866227482093 n / + 304856196348141757586304 n + 306332970239242314930300) g(1 + n) / ( / 2 (n + 10) (n + 7) %1 (9 + n) ) - 8 (3 + n) (4 + n) ( 5 4 2425527134980587222714 n + 54991475007847038819634 n 3 2 + 445212751232454631806213 n + 1477592501747295442522412 n / + 1328148852729749958161049 n - 1441594674757134217686390) g(n + 2) / ( / 2 6 (n + 10) (n + 7) %1 (9 + n) ) + 4 (4 + n) (216217887892500857028 n 5 4 + 14728276605276494774084 n + 337813725866661196673629 n 3 2 + 3647873296020920711705792 n + 20370316597509327509274743 n / + 57046726490253645695767052 n + 63474817532538354872781408) g(3 + n) / / 2 ((n + 10) (n + 7) %1 (9 + n) ) + 2 (233374792160368111213128576 5 6 + 609494596482947611405518 n + 36021489234571937948208 n 2 + 264397248793353820729011616 n + 128797047090164900223277758 n 3 4 + 35249916074668496115615839 n + 5904061575269706430579518 n 7 / 2 + 937942302194377689567 n ) g(4 + n) / ((n + 10) (n + 7) %1 (9 + n) ) + / 2 (-3036586476800367793950716 n + 3620857957580329082679404 n 3 4 + 2862025298278822490235485 n + 845763625692666715067785 n 5 6 + 125464317523984284027765 n + 9324758085365464693755 n 7 / - 8592701011595429714256624 + 276201465441869171226 n ) g(n + 5) / ( / 2 (n + 10) (n + 7) %1 (9 + n) ) - (73184329634315608682917584 2 + 73793776723356428744345864 n + 31073694742887838026075142 n 3 4 + 7083821354797352755827685 n + 945080998298895973248799 n 5 6 + 73963383515453609486133 n + 3159374786081020410739 n 7 / 2 + 57346436706807893574 n ) g(n + 6) / ((n + 10) (n + 7) %1 (9 + n) ) - ( / 6 5 22899812320112195370 n + 827494157198300205393 n 4 3 + 12591248064735141140688 n + 103518420241797662824541 n 2 + 484568275101179666003640 n + 1219181904569062963898692 n + 1280431639150021001185296) g(n + 7)/((n + 10) (9 + n) (n + 7) %1) + g(n + 8) = 0 3 2 %1 := 3086394193343080344 n + 65513399280235398443 n + 403497360223328115712 n + 768661105507998292164 subject to the initial conditions g(1) = 2, g(2) = 6, g(3) = 21, g(4) = 76, g(5) = 290, g(6) = 1148, g(7) = 4627, g(8) = 19038 the recurrence in Maple input notation is -1440*(4+n)*(3+n)*(n+2)*(1+n)*(9906709063384557513*n^3+179921041721431674932*n^ 2+1056202767973180759464*n+2026696297043592211005)/(n+10)/(n+7)/( 3086394193343080344*n^3+65513399280235398443*n^2+403497360223328115712*n+ 768661105507998292164)/(9+n)^2*g(n)-48*(n+2)*(3+n)*(4+n)*(686800557790311050802 *n^4+14113888482339414079471*n^3+102110475496866227482093*n^2+ 304856196348141757586304*n+306332970239242314930300)/(n+10)/(n+7)/( 3086394193343080344*n^3+65513399280235398443*n^2+403497360223328115712*n+ 768661105507998292164)/(9+n)^2*g(1+n)-8*(3+n)*(4+n)*(2425527134980587222714*n^5 +54991475007847038819634*n^4+445212751232454631806213*n^3+ 1477592501747295442522412*n^2+1328148852729749958161049*n-\ 1441594674757134217686390)/(n+10)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)/(9+n)^2 *g(n+2)+4*(4+n)*(216217887892500857028*n^6+14728276605276494774084*n^5+ 337813725866661196673629*n^4+3647873296020920711705792*n^3+ 20370316597509327509274743*n^2+57046726490253645695767052*n+ 63474817532538354872781408)/(n+10)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)/(9+n)^2 *g(3+n)+2*(233374792160368111213128576+609494596482947611405518*n^5+ 36021489234571937948208*n^6+264397248793353820729011616*n+ 128797047090164900223277758*n^2+35249916074668496115615839*n^3+ 5904061575269706430579518*n^4+937942302194377689567*n^7)/(n+10)/(n+7)/( 3086394193343080344*n^3+65513399280235398443*n^2+403497360223328115712*n+ 768661105507998292164)/(9+n)^2*g(4+n)+(-3036586476800367793950716*n+ 3620857957580329082679404*n^2+2862025298278822490235485*n^3+ 845763625692666715067785*n^4+125464317523984284027765*n^5+ 9324758085365464693755*n^6-8592701011595429714256624+276201465441869171226*n^7) /(n+10)/(n+7)/(3086394193343080344*n^3+65513399280235398443*n^2+ 403497360223328115712*n+768661105507998292164)/(9+n)^2*g(n+5)-( 73184329634315608682917584+73793776723356428744345864*n+ 31073694742887838026075142*n^2+7083821354797352755827685*n^3+ 945080998298895973248799*n^4+73963383515453609486133*n^5+3159374786081020410739 *n^6+57346436706807893574*n^7)/(n+10)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)/(9+n)^2 *g(n+6)-(22899812320112195370*n^6+827494157198300205393*n^5+ 12591248064735141140688*n^4+103518420241797662824541*n^3+ 484568275101179666003640*n^2+1219181904569062963898692*n+ 1280431639150021001185296)/(n+10)/(9+n)/(n+7)/(3086394193343080344*n^3+ 65513399280235398443*n^2+403497360223328115712*n+768661105507998292164)*g(n+7)+ g(n+8) = 0 For the sake of the OEIS, here are the first 31 terms [1, 2, 6, 21, 76, 290, 1148, 4627, 19038, 79554, 336112, 1435522, 6184704, 26838474, 117247440, 515135847, 2274656290, 10090187786, 44940868940, 200897459804, 901082056408, 4053912011322, 18289272082952, 82724956638634, 375064515961744, 1704237546984170, 7759645793395368, 35398085705004882, 161766978394221568, 740496668415453898, 3394960486231275480] Invesigating the set of steps, {[-1, -1], [-1, 1], [0, -1], [0, 1], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 1], [0, -1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, -1], [-1, 1], [0, -1], [1, -1], [1, 1]} We have Theorem , 7, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 1], [0, -1], [1, -1], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 192 (15 n + 98) (n + 5) (3 + n) (n + 2) (1 + n) f(n) ---------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 2 160 (n + 5) (4 + n) (3 + n) (15 n + 137 n + 256) f(n + 2) + ---------------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 3 2 (n + 5) (465 n + 7658 n + 41256 n + 72640) f(4 + n) - ----------------------------------------------------- + f(n + 6) = 0 2 (n + 7) (15 n + 68) (n + 8) subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 0, f(4) = 6, f(5) = 0, f(6) = 55 the recurrence in Maple input notation is 192*(15*n+98)*(n+5)*(3+n)*(n+2)*(1+n)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n)+160*(n +5)*(4+n)*(3+n)*(15*n^2+137*n+256)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n+2)-(n+5)*( 465*n^3+7658*n^2+41256*n+72640)/(n+7)/(15*n+68)/(n+8)^2*f(4+n)+f(n+6) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 6, 0, 55, 0, 644, 0, 8694, 0, 128964, 0, 2045901, 0, 34136960, 0, 592493044, 0, 10614366568, 0, 195164993478, 0, 3667395504304, 0, 70199379387700 , 0, 1365217425954360, 0, 26918993235702735] Invesigating the set of steps, {[-1, -1], [-1, 1], [0, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 1], [0, 1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, -1], [-1, 1], [0, 1], [1, -1], [1, 1]} We have Theorem , 8, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 1], [0, 1], [1, -1], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 192 (15 n + 98) (n + 5) (3 + n) (n + 2) (1 + n) f(n) ---------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 2 160 (n + 5) (4 + n) (3 + n) (15 n + 137 n + 256) f(n + 2) + ---------------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 3 2 (n + 5) (465 n + 7658 n + 41256 n + 72640) f(4 + n) - ----------------------------------------------------- + f(n + 6) = 0 2 (n + 7) (15 n + 68) (n + 8) subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 0, f(4) = 6, f(5) = 0, f(6) = 55 the recurrence in Maple input notation is 192*(15*n+98)*(n+5)*(3+n)*(n+2)*(1+n)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n)+160*(n +5)*(4+n)*(3+n)*(15*n^2+137*n+256)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n+2)-(n+5)*( 465*n^3+7658*n^2+41256*n+72640)/(n+7)/(15*n+68)/(n+8)^2*f(4+n)+f(n+6) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 6, 0, 55, 0, 644, 0, 8694, 0, 128964, 0, 2045901, 0, 34136960, 0, 592493044, 0, 10614366568, 0, 195164993478, 0, 3667395504304, 0, 70199379387700 , 0, 1365217425954360, 0, 26918993235702735] Invesigating the set of steps, {[-1, -1], [-1, 1], [0, 1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, -1], [-1, 1], [1, -1], [1, 0], [1, 1]} We have Theorem , 9, :Let f(n) be the number of n-step walks, starting and ending at \ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [-1, 1], [1, -1], [1, 0], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 192 (15 n + 98) (n + 5) (3 + n) (n + 2) (1 + n) f(n) ---------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 2 160 (n + 5) (4 + n) (3 + n) (15 n + 137 n + 256) f(n + 2) + ---------------------------------------------------------- 2 (15 n + 68) (n + 7) (n + 6) (n + 8) 3 2 (n + 5) (465 n + 7658 n + 41256 n + 72640) f(4 + n) - ----------------------------------------------------- + f(n + 6) = 0 2 (n + 7) (15 n + 68) (n + 8) subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 0, f(4) = 6, f(5) = 0, f(6) = 55 the recurrence in Maple input notation is 192*(15*n+98)*(n+5)*(3+n)*(n+2)*(1+n)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n)+160*(n +5)*(4+n)*(3+n)*(15*n^2+137*n+256)/(15*n+68)/(n+7)/(n+6)/(n+8)^2*f(n+2)-(n+5)*( 465*n^3+7658*n^2+41256*n+72640)/(n+7)/(15*n+68)/(n+8)^2*f(4+n)+f(n+6) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 6, 0, 55, 0, 644, 0, 8694, 0, 128964, 0, 2045901, 0, 34136960, 0, 592493044, 0, 10614366568, 0, 195164993478, 0, 3667395504304, 0, 70199379387700 , 0, 1365217425954360, 0, 26918993235702735] Invesigating the set of steps, {[-1, -1], [0, -1], [0, 1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, -1], [0, -1], [0, 1], [1, -1], [1, 1]} Invesigating the set of steps, {[-1, -1], [0, -1], [0, 1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, -1], [0, -1], [1, -1], [1, 0], [1, 1]} We have Theorem , 10, :Let f(n) be the number of n-step walks, starting and ending at\ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, -1], [0, -1], [1, -1], [1, 0], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) f(n) - -------------- + f(n + 2) = 0 4 + n subject to the initial conditions f(1) = 0, f(2) = 1 the recurrence in Maple input notation is -4*(1+n)/(4+n)*f(n)+f(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845] We also have the following theorem. Theorem , 10A, : Let g(n) be the number of n-step walks, starting at [0,0], a\ lways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[-1, -1], [0, -1], [1, -1], [1, 0], [1, 1]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 55 (1 + n) g(n) (-14 + n) g(1 + n) (25 + 7 n) g(n + 2) --------------- - ------------------ - ------------------- + g(3 + n) = 0 4 + n 4 + n 4 + n subject to the initial conditions g(1) = 2, g(2) = 7, g(3) = 23 the recurrence in Maple input notation is 55*(1+n)/(4+n)*g(n)-(-14+n)/(4+n)*g(1+n)-(25+7*n)/(4+n)*g(n+2)+g(3+n) = 0 For the sake of the OEIS, here are the first 31 terms [1, 2, 7, 23, 85, 314, 1207, 4682, 18493, 73688, 296671, 1202849, 4910689, 20158436, 83169871, 344628527, 1433631973, 5984532728, 25060514887, 105240685511, 443102517025, 1870054761632, 7909539602647, 33521289826778, 142330494633985, 605375433105734, 2578988979186127, 11003364185437517, 47012236086805213, 201125820203417690, 861513024099550879] Invesigating the set of steps, {[-1, -1], [0, 1], [1, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, -1], [0, 1], [1, 0]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, -1], [0, 1], [1, 1]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, -1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, -1], [1, -1], [1, 1]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, -1], [1, 0], [1, 1]} We have Theorem , 11, :Let f(n) be the number of n-step walks, starting and ending at\ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, 0], [-1, 1], [0, -1], [1, 0], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 2 48 (4 + n) (3 + n) (n + 2) (1 + n) (12 n + 128 n + 337) f(n) - ------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 16 (n + 2) (3 + n) (4 + n) (84 n + 1196 n + 5565 n + 8446) f(1 + n) - --------------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 4 3 2 24 (3 + n) (4 + n) (36 n + 676 n + 4721 n + 14536 n + 16652) f(n + 2) - ------------------------------------------------------------------------ (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 4 (4 + n) (2 n + 11) (12 n + 170 n + 799 n + 1242) f(3 + n) - ------------------------------------------------------------- (n + 8) (n + 7) (n + 6) %1 3 2 (4 + n) (12 n + 212 n + 1197 n + 2161) f(4 + n) + ------------------------------------------------- + f(n + 5) = 0 (n + 7) (n + 8) %1 2 %1 := 12 n + 104 n + 221 subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 3, f(4) = 4, f(5) = 20 the recurrence in Maple input notation is -48*(4+n)*(3+n)*(n+2)*(1+n)*(12*n^2+128*n+337)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+ 104*n+221)*f(n)-16*(n+2)*(3+n)*(4+n)*(84*n^3+1196*n^2+5565*n+8446)/(n+5)/(n+8)/ (n+7)/(n+6)/(12*n^2+104*n+221)*f(1+n)-24*(3+n)*(4+n)*(36*n^4+676*n^3+4721*n^2+ 14536*n+16652)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(n+2)-4*(4+n)*(2*n+ 11)*(12*n^3+170*n^2+799*n+1242)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(3+n)+(4+ n)*(12*n^3+212*n^2+1197*n+2161)/(n+7)/(n+8)/(12*n^2+104*n+221)*f(4+n)+f(n+5) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 3, 4, 20, 65, 175, 742, 2604, 9072, 36960, 139392, 538824, 2198625, 8735727, 35456850, 146812952, 604215326, 2521642266, 10617725768, 44760668160, 190357768328, 813800295880, 3490232753680, 15055389124320, 65193213272800, 283254330047520, 1235731377864960, 5407996483238160, 23738772386435985] Invesigating the set of steps, {[-1, 0], [-1, 1], [0, 1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, 1], [1, -1], [1, 1]} Invesigating the set of steps, {[-1, 0], [-1, 1], [0, 1], [1, 0], [1, 1]} We have Theorem , 12, :Let f(n) be the number of n-step walks, starting and ending at\ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, 0], [-1, 1], [0, 1], [1, 0], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) f(n) - -------------- + f(n + 2) = 0 4 + n subject to the initial conditions f(1) = 0, f(2) = 1 the recurrence in Maple input notation is -4*(1+n)/(4+n)*f(n)+f(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845] We also have the following theorem. Theorem , 12A, : Let g(n) be the number of n-step walks, starting at [0,0], a\ lways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[-1, 0], [-1, 1], [0, 1], [1, 0], [1, 1]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 15 (1 + n) g(n) 2 (4 + n) g(1 + n) - --------------- - ------------------ + g(n + 2) = 0 3 + n 3 + n subject to the initial conditions g(1) = 3, g(2) = 13 the recurrence in Maple input notation is -15*(1+n)/(3+n)*g(n)-2*(4+n)/(3+n)*g(1+n)+g(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 3, 13, 55, 249, 1131, 5253, 24543, 115825, 549331, 2620029, 12543367, 60270697, 290423355, 1403088885, 6793370415, 32956254945, 160152588195, 779470975725, 3798948989655, 18538237315545, 90565618791435, 442899758973285, 2167985089576575, 10621425660150609, 52078139149834611, 255533719072119133, 1254693927664943143, 6164579030486373705, 30305844983647709659, 149069869587581483221] Invesigating the set of steps, {[-1, 0], [-1, 1], [1, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, 0], [0, -1], [0, 1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, 0], [0, -1], [0, 1], [1, -1], [1, 1]} We have Theorem , 13, :Let f(n) be the number of n-step walks, starting and ending at\ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[-1, 0], [0, -1], [0, 1], [1, -1], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 2 48 (4 + n) (3 + n) (n + 2) (1 + n) (12 n + 128 n + 337) f(n) - ------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 16 (n + 2) (3 + n) (4 + n) (84 n + 1196 n + 5565 n + 8446) f(1 + n) - --------------------------------------------------------------------- (n + 5) (n + 8) (n + 7) (n + 6) %1 4 3 2 24 (3 + n) (4 + n) (36 n + 676 n + 4721 n + 14536 n + 16652) f(n + 2) - ------------------------------------------------------------------------ (n + 5) (n + 8) (n + 7) (n + 6) %1 3 2 4 (4 + n) (2 n + 11) (12 n + 170 n + 799 n + 1242) f(3 + n) - ------------------------------------------------------------- (n + 8) (n + 7) (n + 6) %1 3 2 (4 + n) (12 n + 212 n + 1197 n + 2161) f(4 + n) + ------------------------------------------------- + f(n + 5) = 0 (n + 7) (n + 8) %1 2 %1 := 12 n + 104 n + 221 subject to the initial conditions f(1) = 0, f(2) = 1, f(3) = 3, f(4) = 4, f(5) = 20 the recurrence in Maple input notation is -48*(4+n)*(3+n)*(n+2)*(1+n)*(12*n^2+128*n+337)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+ 104*n+221)*f(n)-16*(n+2)*(3+n)*(4+n)*(84*n^3+1196*n^2+5565*n+8446)/(n+5)/(n+8)/ (n+7)/(n+6)/(12*n^2+104*n+221)*f(1+n)-24*(3+n)*(4+n)*(36*n^4+676*n^3+4721*n^2+ 14536*n+16652)/(n+5)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(n+2)-4*(4+n)*(2*n+ 11)*(12*n^3+170*n^2+799*n+1242)/(n+8)/(n+7)/(n+6)/(12*n^2+104*n+221)*f(3+n)+(4+ n)*(12*n^3+212*n^2+1197*n+2161)/(n+7)/(n+8)/(12*n^2+104*n+221)*f(4+n)+f(n+5) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 3, 4, 20, 65, 175, 742, 2604, 9072, 36960, 139392, 538824, 2198625, 8735727, 35456850, 146812952, 604215326, 2521642266, 10617725768, 44760668160, 190357768328, 813800295880, 3490232753680, 15055389124320, 65193213272800, 283254330047520, 1235731377864960, 5407996483238160, 23738772386435985] Invesigating the set of steps, {[-1, 0], [0, -1], [0, 1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, 0], [0, -1], [1, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, 0], [0, 1], [1, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, 1], [0, -1], [0, 1], [1, -1], [1, 0]} Invesigating the set of steps, {[-1, 1], [0, -1], [0, 1], [1, -1], [1, 1]} Invesigating the set of steps, {[-1, 1], [0, -1], [0, 1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, 1], [0, -1], [1, -1], [1, 0], [1, 1]} Invesigating the set of steps, {[-1, 1], [0, 1], [1, -1], [1, 0], [1, 1]} This case is trivial Invesigating the set of steps, {[0, -1], [0, 1], [1, -1], [1, 0], [1, 1]} We have Theorem , 14, :Let f(n) be the number of n-step walks, starting and ending at\ [0,0], always staying in the first quarant, i.e. the region x>=0, y>=0, and always using one of the following steps {[0, -1], [0, 1], [1, -1], [1, 0], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 4 (1 + n) f(n) - -------------- + f(n + 2) = 0 4 + n subject to the initial conditions f(1) = 0, f(2) = 1 the recurrence in Maple input notation is -4*(1+n)/(4+n)*f(n)+f(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845] We also have the following theorem. Theorem , 14A, : Let g(n) be the number of n-step walks, starting at [0,0], a\ lways staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, and always using one of t\ he following steps {[0, -1], [0, 1], [1, -1], [1, 0], [1, 1]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 15 (1 + n) g(n) 2 (4 + n) g(1 + n) - --------------- - ------------------ + g(n + 2) = 0 3 + n 3 + n subject to the initial conditions g(1) = 3, g(2) = 13 the recurrence in Maple input notation is -15*(1+n)/(3+n)*g(n)-2*(4+n)/(3+n)*g(1+n)+g(n+2) = 0 For the sake of the OEIS, here are the first 31 terms [1, 3, 13, 55, 249, 1131, 5253, 24543, 115825, 549331, 2620029, 12543367, 60270697, 290423355, 1403088885, 6793370415, 32956254945, 160152588195, 779470975725, 3798948989655, 18538237315545, 90565618791435, 442899758973285, 2167985089576575, 10621425660150609, 52078139149834611, 255533719072119133, 1254693927664943143, 6164579030486373705, 30305844983647709659, 149069869587581483221] ---------------------------------------------- We have discovered, 22, exciting theorems in enumerative combinatorics. We di\ dn't bother with proofs, since we know how it could be done so why bother? We note that, 2, cases were trivial, 40, cases do not have a holonomic representation of complexity <=, 16, for the enuemrating sequence of walks that start and end at the origin, and, 46, cases do not have such re\ presentations for enumerating walks that start at the origin and end anywhere in the first quardrat (of course staying all the time in th\ at quardrant.) We also note that the enumerating sequence for walks that end anywhere with \ the following set of set of steps {{[-1, -1], [-1, 0], [-1, 1], [0, -1], [1, 0]}, {[-1, -1], [-1, 0], [-1, 1], [0 , -1], [1, 1]}, {[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, -1]}, {[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 0]}, {[-1, -1], [-1, 0], [-1, 1], [1, -1], [1, 0]}, {[ -1, -1], [-1, 0], [-1, 1], [1, -1], [1, 1]}, {[-1, -1], [-1, 0], [-1, 1], [1, 0 ], [1, 1]}, {[-1, -1], [-1, 0], [0, -1], [0, 1], [1, -1]}, {[-1, -1], [-1, 0], [0, -1], [0, 1], [1, 0]}, {[-1, -1], [-1, 0], [0, -1], [0, 1], [1, 1]}, {[-1, -\ 1], [-1, 0], [0, -1], [1, -1], [1, 1]}, {[-1, -1], [-1, 0], [0, -1], [1, 0], [1 , 1]}, {[-1, -1], [-1, 0], [0, 1], [1, -1], [1, 1]}, {[-1, -1], [-1, 0], [0, 1] , [1, 0], [1, 1]}, {[-1, -1], [-1, 0], [1, -1], [1, 0], [1, 1]}, {[-1, -1], [-1 , 1], [0, -1], [0, 1], [1, -1]}, {[-1, -1], [-1, 1], [0, -1], [0, 1], [1, 1]}, {[-1, -1], [-1, 1], [0, -1], [1, -1], [1, 0]}, {[-1, -1], [-1, 1], [0, -1], [1, -1], [1, 1]}, {[-1, -1], [-1, 1], [0, -1], [1, 0], [1, 1]}, {[-1, -1], [-1, 1], [0, 1], [1, -1], [1, 0]}, {[-1, -1], [-1, 1], [0, 1], [1, -1], [1, 1]}, {[-1, -\ 1], [-1, 1], [0, 1], [1, 0], [1, 1]}, {[-1, -1], [-1, 1], [1, -1], [1, 0], [1, 1]}, {[-1, -1], [0, -1], [0, 1], [1, -1], [1, 0]}, {[-1, -1], [0, -1], [0, 1], [1, -1], [1, 1]}, {[-1, -1], [0, -1], [0, 1], [1, 0], [1, 1]}, {[-1, -1], [0, 1 ], [1, -1], [1, 0], [1, 1]}, {[-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1]}, {[-1 , 0], [-1, 1], [0, -1], [0, 1], [1, 0]}, {[-1, 0], [-1, 1], [0, -1], [0, 1], [1 , 1]}, {[-1, 0], [-1, 1], [0, -1], [1, -1], [1, 0]}, {[-1, 0], [-1, 1], [0, -1] , [1, -1], [1, 1]}, {[-1, 0], [-1, 1], [0, -1], [1, 0], [1, 1]}, {[-1, 0], [-1, 1], [0, 1], [1, -1], [1, 0]}, {[-1, 0], [-1, 1], [0, 1], [1, -1], [1, 1]}, {[-1 , 0], [-1, 1], [1, -1], [1, 0], [1, 1]}, {[-1, 0], [0, -1], [0, 1], [1, -1], [1 , 0]}, {[-1, 0], [0, -1], [0, 1], [1, -1], [1, 1]}, {[-1, 0], [0, -1], [0, 1], [1, 0], [1, 1]}, {[-1, 0], [0, -1], [1, -1], [1, 0], [1, 1]}, {[-1, 0], [0, 1], [1, -1], [1, 0], [1, 1]}, {[-1, 1], [0, -1], [0, 1], [1, -1], [1, 0]}, {[-1, 1] , [0, -1], [0, 1], [1, -1], [1, 1]}, {[-1, 1], [0, -1], [0, 1], [1, 0], [1, 1]} , {[-1, 1], [0, -1], [1, -1], [1, 0], [1, 1]}} do not have a holonomic representation of complexity <=, 16, and are possibly non-holonomic. ---------------------------------------------- The whole thing took, 10617.509, seconds.