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!)
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 quarter-plane. 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 closed-form 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 lower-triangular 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 lower-Hessenberg 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

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 February 22 14:33 EST 2020. Contains 332136 sequences. (Running on oeis4.)