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 (L1, L2, L3) such that L2 intersects both L1 and L3 and three walks (L1, L2, L3) such that L1 intersects L3. 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