0,4

The first and the last terms in each row are Catalan numbers. The sum in each row gives the Gessel sequence.

Manuel Kauers, Christoph Koutschan and Doron Zeilberger, Proof of Ira Gessel's Lattice Path Conjecture.

Arvind Ayyer, Towards a human proof of Gessel's conjecture.

Marko Petkovsek and Herbert S. Wilf, On a conjecture of Ira Gessel.

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)].

Cf. A135404, A000531, A000108

Sequence in context: A078202 A074473 A021371 this_sequence A087706 A102447 A151869

Adjacent sequences: A157510 A157511 A157512 this_sequence A157514 A157515 A157516

nonn

Arvind Ayyer (arvind.ayyer(AT)cea.fr), Mar 02 2009