On Three and Four Vicious Walkers
William Y. C. Chen, Donna Q. J. Dou, and Terence Y. J. Zhang
Abstract: We establish a reflection principle for three lattice walkers and use this principle to reduce the enumeration of configurations of three vicious walkers to that of configurations of two vicious walkers. Precisely, the reflection principle leads to a bijection between three walks (L_{1}, L_{2}, L_{3}) such that L_{2} intersects both L_{1} and L_{3} and three walks (L_{1}, L_{2}, L_{3}) such that L_{1} intersects L_{3}. Hence we find a combinatorial interpretation of the formula for the generating function for the number of configurations of three vicious walkers, originally derived by Bousquet-Mélou by using the kernel method, and independently by Gessel by using tableaux and symmetric functions. This answers a question posed by Gessel and Bousquet-Mélou. We also find a reflection principle for four vicious walks that leads to a combinatorial interpretation of a formula derived from Gessel's theorem. AMS Classification: 05A15; 82B23 Keywords: vicious walkers, watermelon, Catalan numbers, Ballot numbers, reflection principle Download: PDF |