OFFSET
0,4
COMMENTS
The first and the last terms in each row are Catalan numbers. The sum in each row gives the Gessel sequence.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..5049
Arvind Ayyer, Towards a human proof of Gessel's conjecture, arXiv:0902.2329 [math.CO], 2009.
Manuel Kauers, Christoph Koutschan and Doron Zeilberger, Proof of Ira Gessel's Lattice Path Conjecture
Marko Petkovsek and Herbert S. Wilf, On a conjecture of Ira Gessel, arXiv:0807.3202 [math.CO], 2008.
EXAMPLE
For n=2, there are 2 walks of length 4 where the diagonal steps (1,1) and (-1,-1) occur zero times [(1,0),(1,0),(-1,0),(-1,0)] and [(1,0),(-1,0),(1,0),(-1,0)];
7 walks where the diagonal steps occur once [(1,0),(-1,0),(1,1),(-1,-1)], [(1,1),(-1,-1),(1,0),(-1,0)], [(1,0),(1,1),(-1,0),(-1,-1)], [(1,0),(1,1),(-1,-1),(-1,0)], [(1,1),(1,0),(-1,0),(-1,-1)], [(1,1),(1,0),(-1,-1),(-1,0)], [(1,1),(-1,0),(1,0),(-1,-1)];
and finally 2 walks where the diagonal steps occur twice [(1,1),(1,1),(-1,-1),(-1,-1)] and [(1,1),(-1,-1),(1,1),(-1,-1)].
Triangle begins:
1;
1, 1;
2, 7, 2;
5, 37, 38, 5;
14, 177, 390, 187, 14;
42, 806, 3065, 3175, 874, 42;
MAPLE
b:= proc(n, k, t, x, y) option remember; `if` (min(n, x, y, k, t, n-x)<0, 0, `if` (n=0, `if` (max(n, k, t)=0, 1, 0), b(n-1, k-1, t, x+1, y+1) +b(n-1, k, t, x+1, y) +b(n-1, k, t, x-1, y) +b(n-1, k, t-1, x-1, y-1))) end: T:= (n, k)-> b(2*n, k, k, 0, 0):
seq (seq (T(n, k), k=0..n), n=0..8); # Alois P. Heinz, Jul 04 2011
MATHEMATICA
b[n_, k_, t_, x_, y_] := b[n, k, t, x, y] = If[Min[n, x, y, k, t, n-x] < 0, 0, If[n == 0, If[Max[n, k, t] == 0, 1, 0], b[n-1, k-1, t, x+1, y+1] + b[n - 1, k, t, x+1, y] + b[n-1, k, t, x-1, y] + b[n-1, k, t-1, x-1, y-1]]]; T[n_, k_] := b[2*n, k, k, 0, 0]; Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 27 2016, after Alois P. Heinz *)
CROSSREFS
KEYWORD
AUTHOR
Arvind Ayyer, Mar 02 2009
STATUS
approved