<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 1" %>
A Constructive Enumeration of Meanders
Reinhard O.W. Franzand1 and Berton A. Earnshaw2
1College of Engineering and Technology, Brigham Young University, Provo, UT 84602, USA
2College of Engineering and Technology, Brigham Young University, Provo, UT 84602, USA
Annals of Combinatorics 6 (1) p.7-18 March, 2002
AMS Subject Classification: 05A15, 05A18, 06A07, 06A08
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


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.