The Number of Ways of Walking in x_{1} ≥ … ≥ x_{k} ≥ 0 for n Days, Starting and Ending at the Origin,

Where at each Day you may either Stay in Place or Move One Unit in any Direction, Equals the Number of n-Cell Standard Young Tableaux with ≤ 2k + 1 Rows.

Doron ZEILBERGER^{1}

Theorem: See title .

Proof: Consider the number of ways of walking in x_{1} ≥ … ≥ x_{k} ≥ 0, from the origin back to the origin, in n days, without the lazy option, i.e. where at each day one is obliged to move one unit in any (legal) direction. The exponential generating function for this sequence is given by a certain determinant due, in more general form, to D. Grabiner and P. Magyar, and spelled-out, for our case, in Eq. (9) of http://arxiv.org/pdf/math/05012230 (by Chen et. al). Obviously, the exponential generating function for the same quantity for lazy walkers, who sometimes rest, is e^{t} times that, since the latter is the binomial transform of the former.

Surprise! This is exactly Gessel’s formula for the exponential generating function for the number of Standard Young Tableaux with n cells and ≤ 2k + 1 rows, spelled out in Eq. (24) of R. Stanley’s

paper http://arxiv.org/pdf/math/050125035 .

It would be interesting to find a nice bijective proof.

Acknowledgement: I wish to thank Guoce Xin for pointing out the (a posteriori) trivial proof (modulo Gessel and Grabiner-Magyar).

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg . Dec. 6, 2007. Exclusively published in the Personal Journal of Ekhad and Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html . Supported in part by the NSF.