Annals of Combinatorics 6 (2002) 7-17A Constructive Enumeration of Meanders Reinhard O.W. Franzand and Berton A. Earnshaw College of Engineering and Technology,
Brigham Young University, Provo, UT 84602, USA Received October 2, 2001 AMS Subject Classification: 05A15, 05A18, 06A07, 06A08 Abstract. We present an efficient algorithm for the construction of plane meanders. All known construction algorithms seem to be of exponential complexity. We use the description of meanders in terms of pairs of noncrossing partitions as introduced in [4]. Keywords: meanders, noncrossing partitions, partitions References 1. M. Aigner, Combinatorial Theory, Springer, Berlin, 1979. 2.. A. Björner, Shellable, and Cohen-Macauly, Partially ordered sets, Trans. Amer. Math. Soc. 260 (1980) 159–183. 3. N. Dershowitz, Ordered trees and non-crossing partitions, Discrete Math. 62 (1986) 215– 218. 4. R. Franz, A Partial order for the set of meanders, Ann. Combin. 2 (1998) 7–18. 5. R. Franz, On the representation of meanders, preprint. 6. R. Franz, Meanders on surfaces, preprint. 7. R. Franz, B. Earnshaw, and J. Grout, Counting meanders I, preprint. 8. G. Kreweras, Sur les partitions noncroisées d’un cycle, Discrete Math. 1 (1972) 333–350. 9. S.K. Lando and A.K. Zvonkin, Meanders, selected translations, Selecta Math. Soviet. 11 (1992) 117–144. 10. S.K. Lando and A.K. Zvonkin, Plane and projective meanders, Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991), Theoret. Comput. Sci. 117 (1/2) (1992) 227–241. 11. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth, Belmont, CA, 1986. 12. R.P. Stanley, Parking functions and noncrossing partitions, The Wilf Festschrift, Elect. J. Combin. 4 (2) (1997). 13. R. Simion and D. Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991) 193–206. |