Systematic Enumeration of Two-Dimensional Lattice Walks Confined to the Firs\
t Quadrant with, 3, Short Steps
With Holonomic Complexity Not Exceeding, 12
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, 3, 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 <=, 12, ,
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 <=, 12
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]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [-1, 0], [0, -1]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [-1, 0], [0, 1]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [-1, 0], [1, -1]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [-1, 0], [1, 0]}
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, 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 , 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, 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], [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]}
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]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 3, g(3) = 5
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 3, 5, 15, 29, 87, 181, 543, 1181, 3543, 7941, 23823, 54573, 163719,
381333, 1143999, 2699837, 8099511, 19319845, 57959535, 139480397, 418441191,
1014536117, 3043608351, 7426790749, 22280372247, 54669443141, 164008329423,
404388938349, 1213166815047]
Invesigating the set of steps, {[-1, -1], [-1, 1], [0, -1]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [-1, 1], [0, 1]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [-1, 1], [1, -1]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [-1, 1], [1, 0]}
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, 1], [1, 0]}
Then f(n) satisfies the following linear recurrence equation with polynomial\
coefficients
64 (4 + n) (3 + n) (n + 2) f(1 + n)
- ----------------------------------- + f(n + 5) = 0
(n + 5) (9 + n) (n + 7)
subject to the initial conditions
f(1) = 0, f(2) = 0, f(3) = 0, f(4) = 2, f(5) = 0
the recurrence in Maple input notation is
-64*(4+n)*(3+n)*(n+2)/(n+5)/(9+n)/(n+7)*f(1+n)+f(n+5) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 0, 0, 0, 2, 0, 0, 0, 28, 0, 0, 0, 660, 0, 0, 0, 20020, 0, 0, 0, 705432, 0,
0, 0, 27457584, 0, 0, 0, 1147334760, 0, 0]
We also have the following theorem.
Theorem , 3A, : 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], [1, 0]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
2
192 (3 + n) (n + 2) (1 + n) (5012210197 n + 68668508136 n + 230397973787) g(n)
/ 2
/ ((n + 8) %1 (9 + n) ) + 64 (n + 2) (3 + n)
/
3 2
(12031015463 n + 209462653977 n + 1146827473951 n + 1955605395651)
/ 2 4
g(1 + n) / ((n + 8) %1 (9 + n) ) - 16 (3 + n) (14697920604 n
/
3 2
+ 226338254429 n + 977125198318 n + 242221348307 n - 3899034005754)
/ 2 2
g(n + 2) / ((n + 8) %1 (9 + n) ) - 16 (3900084475166 n + 2224613598953 n
/
3 4 5
+ 551265919667 n + 62767040545 n + 2675460092 n + 1908560904639)
/ 2 2
g(3 + n) / ((n + 8) %1 (9 + n) ) - (105752729453220 n + 37627970037136 n
/
3 4 5
+ 6344144026813 n + 505383296280 n + 15036630591 n + 112202053775136)
/ 2 4
g(4 + n) / ((n + 8) %1 (9 + n) ) - (n + 7) (12031015463 n
/
3 2
+ 316412618049 n + 3011375310906 n + 12300203797052 n + 18131468268624)
/ 2 4 3
g(n + 5) / ((n + 8) %1 (9 + n) ) + (3674480151 n + 78716122010 n
/
2 /
+ 579315351097 n + 1595303734430 n + 950207236512) g(n + 6) / (%1
/
2
(9 + n) ) + g(n + 7) = 0
2
%1 := 668865023 n + 7997673634 n + 24168042764
subject to the initial conditions
g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 8, g(5) = 15, g(6) = 39, g(7) = 77
the recurrence in Maple input notation is
192*(3+n)*(n+2)*(1+n)*(5012210197*n^2+68668508136*n+230397973787)/(n+8)/(
668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(n)+64*(n+2)*(3+n)*(
12031015463*n^3+209462653977*n^2+1146827473951*n+1955605395651)/(n+8)/(
668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(1+n)-16*(3+n)*(14697920604*n^
4+226338254429*n^3+977125198318*n^2+242221348307*n-3899034005754)/(n+8)/(
668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(n+2)-16*(3900084475166*n+
2224613598953*n^2+551265919667*n^3+62767040545*n^4+2675460092*n^5+1908560904639
)/(n+8)/(668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(3+n)-(
105752729453220*n+37627970037136*n^2+6344144026813*n^3+505383296280*n^4+
15036630591*n^5+112202053775136)/(n+8)/(668865023*n^2+7997673634*n+24168042764)
/(9+n)^2*g(4+n)-(n+7)*(12031015463*n^4+316412618049*n^3+3011375310906*n^2+
12300203797052*n+18131468268624)/(n+8)/(668865023*n^2+7997673634*n+24168042764)
/(9+n)^2*g(n+5)+(3674480151*n^4+78716122010*n^3+579315351097*n^2+1595303734430*
n+950207236512)/(668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(n+6)+g(n+7)
= 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 2, 3, 8, 15, 39, 77, 216, 459, 1265, 2739, 7842, 17641, 49854, 113175,
327604, 761787, 2182833, 5101595, 14868582, 35338401, 102146176, 243510453,
713019480, 1721265625, 5005198029, 12105626337, 35565979706, 86870058279,
253706973975]
Invesigating the set of steps, {[-1, -1], [-1, 1], [1, 1]}
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, 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 , 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, 1], [1, 1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 3, g(3) = 5
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 3, 5, 15, 29, 87, 181, 543, 1181, 3543, 7941, 23823, 54573, 163719,
381333, 1143999, 2699837, 8099511, 19319845, 57959535, 139480397, 418441191,
1014536117, 3043608351, 7426790749, 22280372247, 54669443141, 164008329423,
404388938349, 1213166815047]
Invesigating the set of steps, {[-1, -1], [0, -1], [0, 1]}
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], [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 , 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], [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], [0, -1], [1, -1]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [0, -1], [1, 0]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [0, -1], [1, 1]}
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], [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 , 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], [0, -1], [1, 1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 3, g(3) = 5
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 3, 5, 15, 29, 87, 181, 543, 1181, 3543, 7941, 23823, 54573, 163719,
381333, 1143999, 2699837, 8099511, 19319845, 57959535, 139480397, 418441191,
1014536117, 3043608351, 7426790749, 22280372247, 54669443141, 164008329423,
404388938349, 1213166815047]
Invesigating the set of steps, {[-1, -1], [0, 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], [0, 1], [1, -1]}
Then f(n) satisfies the following linear recurrence equation with polynomial\
coefficients
64 (3 + n) (n + 2) (1 + n) f(n)
- ------------------------------- + f(4 + n) = 0
(4 + n) (n + 8) (n + 6)
subject to the initial conditions
f(1) = 0, f(2) = 0, f(3) = 0, f(4) = 2
the recurrence in Maple input notation is
-64*(3+n)*(n+2)*(1+n)/(4+n)/(n+8)/(n+6)*f(n)+f(4+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 0, 0, 0, 2, 0, 0, 0, 28, 0, 0, 0, 660, 0, 0, 0, 20020, 0, 0, 0, 705432, 0,
0, 0, 27457584, 0, 0, 0, 1147334760, 0, 0]
We also have the following theorem.
Theorem , 7A, : 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], [0, 1], [1, -1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
2
192 (3 + n) (n + 2) (1 + n) (5012210197 n + 68668508136 n + 230397973787) g(n)
/ 2
/ ((n + 8) %1 (9 + n) ) + 64 (n + 2) (3 + n)
/
3 2
(12031015463 n + 209462653977 n + 1146827473951 n + 1955605395651)
/ 2 4
g(1 + n) / ((n + 8) %1 (9 + n) ) - 16 (3 + n) (14697920604 n
/
3 2
+ 226338254429 n + 977125198318 n + 242221348307 n - 3899034005754)
/ 2 2
g(n + 2) / ((n + 8) %1 (9 + n) ) - 16 (3900084475166 n + 2224613598953 n
/
3 4 5
+ 551265919667 n + 62767040545 n + 2675460092 n + 1908560904639)
/ 2 2
g(3 + n) / ((n + 8) %1 (9 + n) ) - (105752729453220 n + 37627970037136 n
/
3 4 5
+ 6344144026813 n + 505383296280 n + 15036630591 n + 112202053775136)
/ 2 4
g(4 + n) / ((n + 8) %1 (9 + n) ) - (n + 7) (12031015463 n
/
3 2
+ 316412618049 n + 3011375310906 n + 12300203797052 n + 18131468268624)
/ 2 4 3
g(n + 5) / ((n + 8) %1 (9 + n) ) + (3674480151 n + 78716122010 n
/
2 /
+ 579315351097 n + 1595303734430 n + 950207236512) g(n + 6) / (%1
/
2
(9 + n) ) + g(n + 7) = 0
2
%1 := 668865023 n + 7997673634 n + 24168042764
subject to the initial conditions
g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 8, g(5) = 15, g(6) = 39, g(7) = 77
the recurrence in Maple input notation is
192*(3+n)*(n+2)*(1+n)*(5012210197*n^2+68668508136*n+230397973787)/(n+8)/(
668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(n)+64*(n+2)*(3+n)*(
12031015463*n^3+209462653977*n^2+1146827473951*n+1955605395651)/(n+8)/(
668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(1+n)-16*(3+n)*(14697920604*n^
4+226338254429*n^3+977125198318*n^2+242221348307*n-3899034005754)/(n+8)/(
668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(n+2)-16*(3900084475166*n+
2224613598953*n^2+551265919667*n^3+62767040545*n^4+2675460092*n^5+1908560904639
)/(n+8)/(668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(3+n)-(
105752729453220*n+37627970037136*n^2+6344144026813*n^3+505383296280*n^4+
15036630591*n^5+112202053775136)/(n+8)/(668865023*n^2+7997673634*n+24168042764)
/(9+n)^2*g(4+n)-(n+7)*(12031015463*n^4+316412618049*n^3+3011375310906*n^2+
12300203797052*n+18131468268624)/(n+8)/(668865023*n^2+7997673634*n+24168042764)
/(9+n)^2*g(n+5)+(3674480151*n^4+78716122010*n^3+579315351097*n^2+1595303734430*
n+950207236512)/(668865023*n^2+7997673634*n+24168042764)/(9+n)^2*g(n+6)+g(n+7)
= 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 2, 3, 8, 15, 39, 77, 216, 459, 1265, 2739, 7842, 17641, 49854, 113175,
327604, 761787, 2182833, 5101595, 14868582, 35338401, 102146176, 243510453,
713019480, 1721265625, 5005198029, 12105626337, 35565979706, 86870058279,
253706973975]
Invesigating the set of steps, {[-1, -1], [0, 1], [1, 0]}
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], [0, 1], [1, 0]}
Then f(n) satisfies the following linear recurrence equation with polynomial\
coefficients
54 (n + 2) (1 + n) f(n)
- ----------------------- + f(3 + n) = 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)*(1+n)/(n+6)/(2*n+9)*f(n)+f(3+n) = 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 , 8A, : 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], [0, 1], [1, 0]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
486 (3 + n) (n + 2) (1 + n) g(n)
- --------------------------------
2
(2 n + 17) (n + 7)
2
162 (n + 2) (3 + n) (4 n + 47 n + 118) g(1 + n)
- ------------------------------------------------
2
(2 n + 17) (n + 8) (n + 7)
3 2
54 (3 + n) (2 n + 27 n + 112 n + 162) g(n + 2)
+ ------------------------------------------------
2
(2 n + 17) (n + 8) (n + 7)
3 4 2
9 (17772 + 553 n + 26 n + 14373 n + 4278 n ) g(3 + n)
+ -------------------------------------------------------
2
(2 n + 17) (n + 8) (n + 7)
3 2
(n + 6) (4 n + 64 n + 333 n + 569) g(4 + n)
- 15/2 ---------------------------------------------
2
(2 n + 17) (n + 8) (n + 7)
2 3 4
(6917 n + 1722 n + 192 n + 8 n + 10659) g(n + 5)
- 1/2 ---------------------------------------------------
2
(2 n + 17) (n + 8) (n + 7)
3 2
(16 n + 348 n + 2499 n + 5917) g(n + 6)
- 1/2 ----------------------------------------- + g(n + 7) = 0
(n + 8) (n + 7) (2 n + 17)
subject to the initial conditions
g(1) = 2, g(2) = 4, g(3) = 10, g(4) = 26, g(5) = 66, g(6) = 178, g(7) = 488
the recurrence in Maple input notation is
-486*(3+n)*(n+2)*(1+n)/(2*n+17)/(n+7)^2*g(n)-162*(n+2)*(3+n)*(4*n^2+47*n+118)/(
2*n+17)/(n+8)/(n+7)^2*g(1+n)+54*(3+n)*(2*n^3+27*n^2+112*n+162)/(2*n+17)/(n+8)/(
n+7)^2*g(n+2)+9*(17772+553*n^3+26*n^4+14373*n+4278*n^2)/(2*n+17)/(n+8)/(n+7)^2*
g(3+n)-15/2*(n+6)*(4*n^3+64*n^2+333*n+569)/(2*n+17)/(n+8)/(n+7)^2*g(4+n)-1/2*(
6917*n+1722*n^2+192*n^3+8*n^4+10659)/(2*n+17)/(n+8)/(n+7)^2*g(n+5)-1/2*(16*n^3+
348*n^2+2499*n+5917)/(n+8)/(n+7)/(2*n+17)*g(n+6)+g(n+7) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 2, 4, 10, 26, 66, 178, 488, 1320, 3674, 10318, 28728, 81344, 231634, 655614
, 1876510, 5391998, 15423550, 44473310, 128605264, 370583896, 1074340126,
3121406738, 9043275450, 26324579482, 76763009234, 223318464418, 652169185724,
1907256905140, 5566743069850, 16299205388766]
Invesigating the set of steps, {[-1, -1], [0, 1], [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], [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 , 9A, : 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], [0, 1], [1, 1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
3 (1 + n) g(n)
- -------------- - 2 g(1 + n) + g(n + 2) = 0
3 + n
subject to the initial conditions
g(1) = 2, g(2) = 5
the recurrence in Maple input notation is
-3*(1+n)/(3+n)*g(n)-2*g(1+n)+g(n+2) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721, 143365, 414584,
1201917, 3492117, 10165779, 29643870, 86574831, 253188111, 741365049,
2173243128, 6377181825, 18730782252, 55062586341, 161995031226, 476941691177,
1405155255055, 4142457992363, 12219350698880, 36064309311811]
Invesigating the set of steps, {[-1, -1], [1, -1], [1, 0]}
This case is trivial
Invesigating the set of steps, {[-1, -1], [1, -1], [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], [1, -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 , 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], [1, -1], [1, 1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 3, g(3) = 5
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 3, 5, 15, 29, 87, 181, 543, 1181, 3543, 7941, 23823, 54573, 163719,
381333, 1143999, 2699837, 8099511, 19319845, 57959535, 139480397, 418441191,
1014536117, 3043608351, 7426790749, 22280372247, 54669443141, 164008329423,
404388938349, 1213166815047]
Invesigating the set of steps, {[-1, -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, -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 , 11A, : 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], [1, 0], [1, 1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
3 (1 + n) g(n)
- -------------- - 2 g(1 + n) + g(n + 2) = 0
3 + n
subject to the initial conditions
g(1) = 2, g(2) = 5
the recurrence in Maple input notation is
-3*(1+n)/(3+n)*g(n)-2*g(1+n)+g(n+2) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721, 143365, 414584,
1201917, 3492117, 10165779, 29643870, 86574831, 253188111, 741365049,
2173243128, 6377181825, 18730782252, 55062586341, 161995031226, 476941691177,
1405155255055, 4142457992363, 12219350698880, 36064309311811]
Invesigating the set of steps, {[-1, 0], [-1, 1], [0, -1]}
This case is trivial
Invesigating the set of steps, {[-1, 0], [-1, 1], [0, 1]}
This case is trivial
Invesigating the set of steps, {[-1, 0], [-1, 1], [1, -1]}
This case is trivial
Invesigating the set of steps, {[-1, 0], [-1, 1], [1, 0]}
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], [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 , 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], [1, 0]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 3, g(3) = 5
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 3, 5, 15, 29, 87, 181, 543, 1181, 3543, 7941, 23823, 54573, 163719,
381333, 1143999, 2699837, 8099511, 19319845, 57959535, 139480397, 418441191,
1014536117, 3043608351, 7426790749, 22280372247, 54669443141, 164008329423,
404388938349, 1213166815047]
Invesigating the set of steps, {[-1, 0], [-1, 1], [1, 1]}
This case is trivial
Invesigating the set of steps, {[-1, 0], [0, -1], [0, 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]}
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 , 13A, : 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], [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, 0], [0, -1], [1, -1]}
This case is trivial
Invesigating the set of steps, {[-1, 0], [0, -1], [1, 0]}
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
{[-1, 0], [0, -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 , 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
{[-1, 0], [0, -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, 0], [0, -1], [1, 1]}
We have
Theorem , 15, :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) (1 + n) f(n)
- ----------------------- + f(3 + n) = 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)*(1+n)/(n+6)/(2*n+9)*f(n)+f(3+n) = 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 , 15A, : 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], [0, -1], [1, 1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
486 (4 + n) (7 n + 41) (n + 2) (1 + n) 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(1 + n)
- -------------------------------------------------
(7 n + 34) (n + 7) (n + 6) (2 n + 13)
3 2
54 (3 + n) (35 n + 443 n + 1787 n + 2309) g(n + 2)
+ ----------------------------------------------------
(7 n + 34) (n + 7) (n + 6) (2 n + 13)
3 2
9 (4 + n) (28 n + 311 n + 897 n + 304) g(3 + n)
- -------------------------------------------------
(7 n + 34) (n + 7) (n + 6) (2 n + 13)
2 3 4
(24070 + 18281 n + 5123 n + 626 n + 28 n ) g(4 + n)
+ 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*(4+n)*(7*n+41)*(n+2)*(1+n)/(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(1+n)+54*(3+n)*(35*n^3+
443*n^2+1787*n+2309)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(n+2)-9*(4+n)*(28*n^3+311*n
^2+897*n+304)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(3+n)+3/2*(24070+18281*n+5123*n^2+
626*n^3+28*n^4)/(7*n+34)/(n+7)/(n+6)/(2*n+13)*g(4+n)-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]
Invesigating the set of steps, {[-1, 0], [0, 1], [1, -1]}
We have
Theorem , 16, :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
27 (n + 2) (1 + n) f(n)
- ----------------------- + f(3 + n) = 0
(9 + n) (n + 6)
subject to the initial conditions
f(1) = 0, f(2) = 0, f(3) = 1
the recurrence in Maple input notation is
-27*(n+2)*(1+n)/(9+n)/(n+6)*f(n)+f(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 0, 0, 1, 0, 0, 5, 0, 0, 42, 0, 0, 462, 0, 0, 6006, 0, 0, 87516, 0, 0,
1385670, 0, 0, 23371634, 0, 0, 414315330, 0, 0, 7646001090]
We also have the following theorem.
Theorem , 16A, : 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], [0, 1], [1, -1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
3 (1 + n) g(n) (5 + 2 n) g(1 + n)
- -------------- - ------------------ + g(n + 2) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 2
the recurrence in Maple input notation is
-3*(1+n)/(4+n)*g(n)-(5+2*n)/(4+n)*g(1+n)+g(n+2) = 0
For the sake of the OEIS, here are the first 31 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]
Invesigating the set of steps, {[-1, 0], [0, 1], [1, 0]}
We have
Theorem , 17, :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, 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 , 17A, : 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], [0, 1], [1, 0]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
3 (1 + n) g(n)
- -------------- - 2 g(1 + n) + g(n + 2) = 0
3 + n
subject to the initial conditions
g(1) = 2, g(2) = 5
the recurrence in Maple input notation is
-3*(1+n)/(3+n)*g(n)-2*g(1+n)+g(n+2) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721, 143365, 414584,
1201917, 3492117, 10165779, 29643870, 86574831, 253188111, 741365049,
2173243128, 6377181825, 18730782252, 55062586341, 161995031226, 476941691177,
1405155255055, 4142457992363, 12219350698880, 36064309311811]
Invesigating the set of steps, {[-1, 0], [0, 1], [1, 1]}
This case is trivial
Invesigating the set of steps, {[-1, 0], [1, -1], [1, 0]}
We have
Theorem , 18, :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], [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 , 18A, : 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], [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, 0], [1, -1], [1, 1]}
We have
Theorem , 19, :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], [1, 1]}
Then f(n) satisfies the following linear recurrence equation with polynomial\
coefficients
64 (4 + n) (3 + n) (n + 2) f(1 + n)
- ----------------------------------- + f(n + 5) = 0
(n + 5) (9 + n) (n + 7)
subject to the initial conditions
f(1) = 0, f(2) = 0, f(3) = 0, f(4) = 2, f(5) = 0
the recurrence in Maple input notation is
-64*(4+n)*(3+n)*(n+2)/(n+5)/(9+n)/(n+7)*f(1+n)+f(n+5) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 0, 0, 0, 2, 0, 0, 0, 28, 0, 0, 0, 660, 0, 0, 0, 20020, 0, 0, 0, 705432, 0,
0, 0, 27457584, 0, 0, 0, 1147334760, 0, 0]
Invesigating the set of steps, {[-1, 0], [1, 0], [1, 1]}
We have
Theorem , 20, :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, 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 , 20A, : 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, 0], [1, 1]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 2, g(2) = 6, g(3) = 16
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 2, 6, 16, 48, 136, 408, 1184, 3552, 10432, 31296, 92544, 277632, 824448,
2473344, 7365120, 22095360, 65920000, 197760000, 590790656, 1772371968,
5299916800, 15899750400, 47578857472, 142736572416, 427357700096, 1282073100288
, 3840133464064, 11520400392192, 34517383151616, 103552149454848]
Invesigating the set of steps, {[-1, 1], [0, -1], [0, 1]}
We have
Theorem , 21, :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], [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 , 21A, : 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], [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], [0, -1], [1, -1]}
This case is trivial
Invesigating the set of steps, {[-1, 1], [0, -1], [1, 0]}
We have
Theorem , 22, :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, 0]}
Then f(n) satisfies the following linear recurrence equation with polynomial\
coefficients
27 (n + 2) (1 + n) f(n)
- ----------------------- + f(3 + n) = 0
(9 + n) (n + 6)
subject to the initial conditions
f(1) = 0, f(2) = 0, f(3) = 1
the recurrence in Maple input notation is
-27*(n+2)*(1+n)/(9+n)/(n+6)*f(n)+f(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 0, 0, 1, 0, 0, 5, 0, 0, 42, 0, 0, 462, 0, 0, 6006, 0, 0, 87516, 0, 0,
1385670, 0, 0, 23371634, 0, 0, 414315330, 0, 0, 7646001090]
We also have the following theorem.
Theorem , 22A, : 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, 0]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
3 (1 + n) g(n) (5 + 2 n) g(1 + n)
- -------------- - ------------------ + g(n + 2) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 2
the recurrence in Maple input notation is
-3*(1+n)/(4+n)*g(n)-(5+2*n)/(4+n)*g(1+n)+g(n+2) = 0
For the sake of the OEIS, here are the first 31 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]
Invesigating the set of steps, {[-1, 1], [0, -1], [1, 1]}
We have
Theorem , 23, :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]}
Then f(n) satisfies the following linear recurrence equation with polynomial\
coefficients
64 (3 + n) (n + 2) (1 + n) f(n)
- ------------------------------- + f(4 + n) = 0
(4 + n) (n + 8) (n + 6)
subject to the initial conditions
f(1) = 0, f(2) = 0, f(3) = 0, f(4) = 2
the recurrence in Maple input notation is
-64*(3+n)*(n+2)*(1+n)/(4+n)/(n+8)/(n+6)*f(n)+f(4+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 0, 0, 0, 2, 0, 0, 0, 28, 0, 0, 0, 660, 0, 0, 0, 20020, 0, 0, 0, 705432, 0,
0, 0, 27457584, 0, 0, 0, 1147334760, 0, 0]
Invesigating the set of steps, {[-1, 1], [0, 1], [1, -1]}
This case is trivial
Invesigating the set of steps, {[-1, 1], [0, 1], [1, 0]}
This case is trivial
Invesigating the set of steps, {[-1, 1], [0, 1], [1, 1]}
This case is trivial
Invesigating the set of steps, {[-1, 1], [1, -1], [1, 0]}
This case is trivial
Invesigating the set of steps, {[-1, 1], [1, -1], [1, 1]}
This case is trivial
Invesigating the set of steps, {[-1, 1], [1, 0], [1, 1]}
This case is trivial
Invesigating the set of steps, {[0, -1], [0, 1], [1, -1]}
We have
Theorem , 24, :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]}
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 , 24A, : 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]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 1, g(2) = 3, g(3) = 5
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 1, 3, 5, 15, 29, 87, 181, 543, 1181, 3543, 7941, 23823, 54573, 163719,
381333, 1143999, 2699837, 8099511, 19319845, 57959535, 139480397, 418441191,
1014536117, 3043608351, 7426790749, 22280372247, 54669443141, 164008329423,
404388938349, 1213166815047]
Invesigating the set of steps, {[0, -1], [0, 1], [1, 0]}
We have
Theorem , 25, :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, 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 , 25A, : 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, 0]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
3 (1 + n) g(n)
- -------------- - 2 g(1 + n) + g(n + 2) = 0
3 + n
subject to the initial conditions
g(1) = 2, g(2) = 5
the recurrence in Maple input notation is
-3*(1+n)/(3+n)*g(n)-2*g(1+n)+g(n+2) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721, 143365, 414584,
1201917, 3492117, 10165779, 29643870, 86574831, 253188111, 741365049,
2173243128, 6377181825, 18730782252, 55062586341, 161995031226, 476941691177,
1405155255055, 4142457992363, 12219350698880, 36064309311811]
Invesigating the set of steps, {[0, -1], [0, 1], [1, 1]}
We have
Theorem , 26, :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]}
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 , 26A, : 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]}
Then g(n) satisfies the following linear recurrence equation with polynomial\
coefficients
24 (1 + n) g(n) 8 (1 + n) g(1 + n)
--------------- - ------------------ - 3 g(n + 2) + g(3 + n) = 0
4 + n 4 + n
subject to the initial conditions
g(1) = 2, g(2) = 6, g(3) = 16
the recurrence in Maple input notation is
24*(1+n)/(4+n)*g(n)-8*(1+n)/(4+n)*g(1+n)-3*g(n+2)+g(3+n) = 0
For the sake of the OEIS, here are the first 31 terms
[1, 2, 6, 16, 48, 136, 408, 1184, 3552, 10432, 31296, 92544, 277632, 824448,
2473344, 7365120, 22095360, 65920000, 197760000, 590790656, 1772371968,
5299916800, 15899750400, 47578857472, 142736572416, 427357700096, 1282073100288
, 3840133464064, 11520400392192, 34517383151616, 103552149454848]
Invesigating the set of steps, {[0, -1], [1, -1], [1, 0]}
This case is trivial
Invesigating the set of steps, {[0, -1], [1, -1], [1, 1]}
This case is trivial
Invesigating the set of steps, {[0, -1], [1, 0], [1, 1]}
This case is trivial
Invesigating the set of steps, {[0, 1], [1, -1], [1, 0]}
This case is trivial
Invesigating the set of steps, {[0, 1], [1, -1], [1, 1]}
This case is trivial
Invesigating the set of steps, {[0, 1], [1, 0], [1, 1]}
This case is trivial
Invesigating the set of steps, {[1, -1], [1, 0], [1, 1]}
This case is trivial
----------------------------------------------
We have discovered, 50, 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, 30, cases were trivial, 0,
cases do not have a holonomic representation of complexity <=, 12,
for the enuemrating sequence
of walks that start and end at the origin, and, 2, cases do not have such rep\
resentations 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, 0], [1, -1], [1, 1]}, {[-1, 1], [0, -1], [1, 1]}}
do not have a holonomic representation of complexity <=, 12,
and are possibly non-holonomic.
----------------------------------------------
The whole thing took, 356.212, seconds.