login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A157513 Triangle of numbers of walks in the quarter-plane, of length 2n beginning and ending at the origin using steps {(1,1), (1,0), (-1,0), (-1,-1)} (Gessel steps) arranged according to the number of times the steps (1,1) and (-1,-1) occur. 1
1, 1, 1, 2, 7, 2, 5, 37, 38, 5, 14, 177, 390, 187, 14, 42, 806, 3065, 3175, 874, 42, 132, 3566, 20742, 37260, 22254, 3958, 132, 429, 15485, 127575, 351821, 365433, 141442, 17548, 429, 1430, 66373, 734332, 2876886, 4597444, 3100670, 839068, 76627, 1430 (list; table; graph; refs; listen; history; text; internal format)
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

Cf. A135404, A000531, A000108.

Sequence in context: A074473 A021371 A332501 * A087706 A102447 A151869

Adjacent sequences:  A157510 A157511 A157512 * A157514 A157515 A157516

KEYWORD

nonn,tabl,walk

AUTHOR

Arvind Ayyer, Mar 02 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 10 02:28 EDT 2020. Contains 336367 sequences. (Running on oeis4.)