#Kreweras walks Theorem: 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], [1, 1]} Then f(n) satisfies the following linear recurrence equation with polynomial\ coefficients 54 (n + 2) (n + 1) f(n) - ----------------------- + f(n + 3) = 0 (n + 6) (2 n + 9) subject to the initial conditions f(1) = 0, f(2) = 0, f(3) = 2 the recurrence in Maple input notation is -54*(n+2)*(n+1)/(n+6)/(2*n+9)*f(n)+f(n+3) = 0 For the sake of the OEIS, here are the first 31 terms [1, 0, 0, 2, 0, 0, 16, 0, 0, 192, 0, 0, 2816, 0, 0, 46592, 0, 0, 835584, 0, 0, 15876096, 0, 0, 315031552, 0, 0, 6466437120, 0, 0, 136383037440] We also have the following theorem. Theorem: Let g(n) be the number of n-step walks, starting at [0,0], always \ staying in the first quarant, i.e. the region x>=0, y>=0, and ending whenever they want there, always using one of the fo\ llowing steps {[-1, 0], [0, -1], [1, 1]} Then g(n) satisfies the following linear recurrence equation with polynomial\ coefficients 486 (n + 4) (7 n + 41) (n + 2) (n + 1) g(n) - ------------------------------------------- (7 n + 34) (n + 7) (n + 6) (2 n + 13) 3 2 162 (n + 2) (7 n + 90 n + 382 n + 545) g(n + 1) - ------------------------------------------------- (7 n + 34) (n + 7) (n + 6) (2 n + 13) 3 2 54 (n + 3) (35 n + 443 n + 1787 n + 2309) g(n + 2) + ---------------------------------------------------- (7 n + 34) (n + 7) (n + 6) (2 n + 13) 3 2 9 (n + 4) (28 n + 311 n + 897 n + 304) g(n + 3) - ------------------------------------------------- (7 n + 34) (n + 7) (n + 6) (2 n + 13) 2 3 4 (24070 + 5123 n + 626 n + 28 n + 18281 n) g(n + 4) + 3/2 ----------------------------------------------------- (7 n + 34) (n + 7) (n + 6) (2 n + 13) 3 2 (140 n + 2402 n + 13687 n + 25843) g(n + 5) - 1/2 --------------------------------------------- + g(n + 6) = 0 (7 n + 34) (n + 7) (2 n + 13) subject to the initial conditions g(1) = 1, g(2) = 3, g(3) = 7, g(4) = 17, g(5) = 47, g(6) = 125 the recurrence in Maple input notation is -486*(n+4)*(7*n+41)*(n+2)*(n+1)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(n)-162*(n+2)*(7 *n^3+90*n^2+382*n+545)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(n+1)+54*(n+3)*(35*n^3+ 443*n^2+1787*n+2309)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(n+2)-9*(n+4)*(28*n^3+311*n ^2+897*n+304)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(n+3)+3/2*(24070+5123*n^2+626*n^3+ 28*n^4+18281*n)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(n+4)-1/2*(140*n^3+2402*n^2+ 13687*n+25843)/(7*n+34)/(n+7)/(2*n+13)*g(n+5)+g(n+6) = 0 For the sake of the OEIS, here are the first 31 terms [1, 1, 3, 7, 17, 47, 125, 333, 939, 2597, 7183, 20505, 57859, 163201, 469795, 1341775, 3830529, 11092823, 31940165, 91927379, 267406401, 774447755, 2242022721, 6544458687, 19036737381, 55354815639, 162028272261, 472921269031, 1379896701413, 4048204328607, 11848014062621] ---------------------------------- Sketch of proof Let w(n,a,b) be the number of walks of length n with step-set, {[-1, 0], [0, -1], [1, 1]}, that start at [0,0] and end at [a,b] and always staying in the first-quadrant. Let F(t,x,y) be the three-variable\ generating function, i.e.: infinity ------- /infinity /infinity \\ \ | ----- | ----- || \ | \ | \ n a b|| F(t, x, y) = ) | ) | ) w(n, a, b) t x y || / | / | / || / | ----- | ----- || ------- \ a = 0 \ b = 0 // n = 0 It is readily seen that F(t,x,y) satisfies the following Functional Equation\ that uniquely determines it: t (F(t, x, y) - F(t, 0, y)) t (F(t, x, y) - F(t, x, 0)) F(t, x, y) = 1 + --------------------------- + --------------------------- x y + t x y F(t, x, y) Solving for F(t,x,y), this is equivalent to t F(t, 0, y) x - y x + t F(t, x, 0) y F(t, x, y) = ------------------------------------- 2 2 -y x + t y + t x + t x y It is possible to guess, from the initial values, a linear recurrence equati\ on with polynomial coefficients (in t and x) for the sequence of polynomials in x given by the coefficients, in t, of F(t\ ,x,0) of order, 5, and degree of coefficients, 5 This immediately implies that F(t,x,0) is most probably D-finite and it is e\ asy to find the linear differential equation in t, with polynomial coeff\ icients in t and x (so far conjecturally) satisfied by it. It is also possible to guess, from the initial values, a linear recurrence e\ quation with polynomial coefficients (in t and y) for the sequence of polynomials in y given by the coefficients, in t, of F(t\ ,0,y) of order, 5, and degree of coefficients, 5 This immediately implies that F(t,0,y) is most probably D-finite and it is e\ asy to find the linear differential equation in t, with polynomial coeff\ icients in t and y (so far conjecturally) satisfied by it. Now let's go backwards! Let f1(t,x) and f2(t,y) be the unique formal power s\ eries in t that satisfy the above-mentioned guessed differential equation and define t f2(t, y) x - y x + t f1(t, x) y G(t, x, y) = --------------------------------- 2 2 -y x + t y + t x + t x y it is purely routine to find a differential equation with polynomial coeffic\ ients satisfied by G(t,x,y). It is also purely routine to check (still in the holonomic ansatz in the sin\ gle-variable t, that the defining functional equation for F(t,x,y) is satisfied by the newly\ arrived G(t,x,y). Hence by uniqueness, F(t,x,y)=G(t,x,y), and the above-mentioned differential\ equation in t is satisfied by F(t,x,y). Now plugging-in x=0, y=0, gives us a differential equation satisfied by F(t,\ 0,0) and plugging-in x=1, y=1 gives us a differential equation satisfied by F(t,1,1) that translate to the recurrenes claimed in the above \ two theorems. QED! (modulo purely routine calculations) This took, 16.294, seconds.