A Constructive Enumeration of Meanders

Reinhard O.W. Franzand^{1} and Berton A. Earnshaw^{2}

franz@et.byu.edu

berton@et.byu.edu

Annals of Combinatorics 6 (1) p.7-18 March, 2002

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].

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.