Counting meanders

We have, with Moto Fukuda, a new paper on the arXiv, Enumerating meandric systems with large number of components, which deals with the enumeration of meandric systems.

In combinatorics, a meander on points is a closed, self-avoiding plane curve, which intersects a given line times. Below, the meanders of a river (Rio Cauto, in Cuba) and a mathematical meander are represented.

rio-cauto m1

The following more general objects are considered in the literature.

Definition 1 A meandric system on points with connected components is a collection of non-intersecting closed curves, which cross a given line times. A meander is a meandric system with component.

Below are represented two meandric systems on points, with , respectively connected components.

m2 m3

One easily recognizes the diagrams above and below the horizontal line: these are non-crossing pairings, a subclass of non-crossing partitions. Non-crossing pairings on points are known to be in bijection with (general) non-crossing partitions on points, through an operation called fattening; in the picture below, the same meanders as above are depicted, together with the corresponding non-crossing partitions on points; see how the meander (red) is a ``fattening'' of the pair of non-crossing partitions (black).

mm2 mm3

In our paper, we study meandric systems on points with connected components, for some fixed parameter . We obtain the general form of the generating function for the number of such meanders, with exact expressions for . Some trivial observations can be made right from the start. First, we have seen that meandric systems are in bijection with pairs of non-crossing partitions. Since non-crossing partitions are counted by Catalan numbers, we have

Note also that meandric systems with a maximal number of connected components (see the example on the right in the previous two pictures) correspond to the case where the two non-crossing partitions defining the meander are equal , and thus

To compute the numbers , it is not hard to see that the two non-crossing partitions and must be somehow ``close''. To make this precise, we consider another key bijection, the one between non-crossing partitions and the so-called geodesic permutations. In his seminal work Some properties of crossings and partitions, Biane realized that non-crossing partitions are in bijection with the following set of permutations

where is the full-cycle permutation and is the length function of permutations: is the minimal number of transpositions which multiply to . All these ideas are discussed in Lecture 23 of the excellent monograph of Nica and Speicher. In this framework, it has been known for some time that meanders on points with connected components are in bijection with the set

In particular, for , only pairs of geodesic permutations which differ by only one transposition contribute; one can easily show then

In our paper, we use the moment-cumulant formula from Free Probability Theory to show that, for fixed , the generating function for the number of meanders on points with connected components

after the change of variables , reads

where are polynomials of degree at most . With the help of a computer, we find these polynomials up to . We show that such meandric systems are made of simple building blocks, called irreducible meanders. Irreducible meanders were introduced by Lando and Zvonkin here, and they were recently featured in Andu Nica's recent paper.

Let me close this post by mentioning what is probably the most important problem related to the enumeration of meanders (on which we do not touch upon): the asymptotic growth of meanders. This problem and the one we discuss in our paper sit at opposite ends of the spectrum with respect to the number of components.

The sequence of meandric numbers is conjectured to grow like

for some constants . The exponential rate has been shown to satisfy . The polynomial speed is conjectured to be exactly .

The meandric numbers have a very simple geometric interpretation: they count diameters in the metric space :

The asymptotic behavior of the sequence is largely open. Old and recent results suggest that solving this many-faceted problem might require some new insight or techniques.