<%@ 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
franz@et.byu.edu
2College of Engineering and Technology, Brigham Young University, Provo, UT 84602, USA
berton@et.byu.edu
Annals of Combinatorics 6 (1) p.7-18 March, 2002
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.