By Doron Zeilberger
(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.
Doron Zeilberger's Home Page