Watermelon uniform random generation with applications

摘要

Watermelons are particular configurations of vicious walkers. In these configurations, each path starts and ends at the same ordinate. We present a simple uniform random generation algorithm of watermelons based on enumeration formulas of star configurations (with or without a wall). The performance of this algorithm is better than earlier ones in the case of watermelons with few walkers. Using appropriate bijections, these algorithms can also generate underdiagonal paths, realizers (or Schnyder Trees), twin parallelogram polyominoes according to their perimeter and width, Baxter permutations according to the number of rises, etc. Moreover, we present some experimental results on the height of watermelons and realizers. (C) 2003 Elsevier B.V. All rights reserved. [References: 37]