Towards a Human Proof of Gessel's Conjecture
Arvind Ayyer
Institut de Physique Théorique
IPhT, CEA Saclay, and URA 2306, CNRS
91191 Gif-sur-Yvette Cedex
France
Abstract:
We interpret walks in the first quadrant with steps
{ (1,1), (1,0), (-1,0), (-1,-1) } as a generalization
of Dyck words with two sets of letters. Using this language, we give a formal
expression for the number of walks using the steps above, beginning and
ending at the origin. We give an explicit formula
for a restricted class of such words using a correspondence between
such words and Dyck paths.
This explicit formula is exactly the same
as that for the
degree of the polynomial satisfied by the square of the area of cyclic
n-gons conjectured by Robbins, although the connection is a mystery.
Finally we remark on another combinatorial problem in which the same
formula appears and argue for the existence of a bijection.
Full version: pdf,
dvi,
ps,
latex
(Concerned with sequences
A000531
A045720 and
A135404.)
Received March 2 2009;
revised version received April 30 2009.
Published in Journal of Integer Sequences, May 12 2009.
Return to
Journal of Integer Sequences home page