#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.