

A140878


Table, by rows, of universal sequences arising in the solution vectors of a conjecture of Ira Gessel.


0



1, 1, 1, 2, 3, 1, 1, 5, 11, 19, 10, 2, 1, 9, 37, 85, 158, 103, 35, 5, 1, 14, 87, 332, 782, 1521, 1126, 499, 126, 14, 1, 20, 172, 911, 3343, 8004, 16056, 12941, 6765, 2296, 462, 42, 1, 27, 305, 2096, 10147, 36350, 88044, 180621, 154750, 90781, 37178, 10254, 1716, 132
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Each of these rows (universal sequences) ends in a Catalan number A000108. Gessel's problem is equivalent to walks in the positive quarterplane. Abstract: Let F(m; n1, n2) denote the number of lattice walks from (0,0) to (n1,n2), always staying in the first quadrant {(n_1,n_2); n1 >= 0, n2 >= 0} and having exactly m steps, each of which belongs to the set {E=(1,0), W=(1,0), NE=(1,1), SW=(1,1)}. Ira Gessel conjectured that F(2n; 0, 0) = 16^n (1/2)_n (5/6)_n / ((2)_n (5/3)_n) where (a)_n is the Pochhammer symbol. We pose similar conjectures for some other values of (n1,n2) and give closedform formulas for F(n1; n1, n2) when n1 >= n2 as well as for F(2n2  n1; n1, n2) when n1 <= n2. In the main part of the paper, we derive a functional equation satisfied by the generating function of F(m; n1, n2), use the kernel method to turn it into an infinite lowertriangular system of linear equations satisfied by the values of F(m; n1, 0) and F(m; 0, n2) + F(m;
0, n2  1) and express these values explicitly as determinants of lowerHessenberg matrices with unit superdiagonals whose nonzero entries are products of two binomial coefficients.


LINKS

Table of n, a(n) for n=1..56.
Marko Petkovsek, Herbert S. Wilf, On a conjecture of Ira Gessel, arXiv:0807.3202.


EXAMPLE

Table begins with these 8 rows:
1, 1.
1, 2, 3, 1.
1, 5, 11, 19, 10, 2.
1, 9, 37, 85, 158, 103, 35, 5.
1, 14, 87, 332, 782, 1521, 1126, 499, 126, 14.
1, 20, 172, 911, 3343, 8004, 16056, 12941, 6765, 2296, 462, 42.
1, 27, 305, 2096, 10147, 36350, 88044, 180621, 154750, 90781, 37178, 10254, 1716, 132.
1, 35, 501, 4300, 25297, 118472, 417565, 1020162, 2128824, 1910006, 1217523, 570409, 193137, 44913, 6435, 429.


CROSSREFS

Cf. A000108, A060900, A135404.
Sequence in context: A194680 A131739 A011151 * A182933 A068348 A308290
Adjacent sequences: A140875 A140876 A140877 * A140879 A140880 A140881


KEYWORD

nonn,tabf,uned


AUTHOR

Jonathan Vos Post, Jul 22 2008


STATUS

approved



