The Number of Ways of Walking in x1 ≥ ... ≥ xk ≥ 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.

By Doron Zeilberger

.pdf   .ps   .tex  

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger)

Written: Dec. 6, 2007.

I recently came back from an exciting visit to Bill Chen's exciting Chinese Combinatorics Empire at Nankai Univ., where I had lots of stimulating conversations, especially with Bill Chen, Christian Reidys, and the young combinatorics "whiz kid" Guoce Xin. Motivated by the recent work on the combinatorics of RNA Seconary structures of Chen and Reidys, I came up with the conjecture of the title, and was rather excited by it. Alas, as was pointed out by Guoce Xin, it follows immediately from known results.

Nevertheless, I have never seen this result stated in this form, and call it trivial if you will (of course, modulo Gessel and Grabiner-Magyar), I think that it is neat.

It would be interesting to find a nice bijective proof.

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page