This site is supported by donations to The OEIS Foundation.
Meanders
This is a draft of an article about meanders written by DF, BJ, DM, DS and JW. If you are not on this list, please contact us before editing this page.
Contents
 1 Introduction
 2 Definitions of meanders
 3 Multimeanders on rectangular grids
 4 Meanders on rectangular grids
 4.1 Meanders on rectangular grids
 4.2 Selfcrossing meanders on rectangular grids
 4.3 Multimeanders on rectangular grids
 4.4 Selfcrossing multimeanders on rectangular grids
 4.5 Square grids (quadriangulated)
 4.6 Rectangular grids with sides identified (quadriangulated)
 4.7 Projective planes (triangulated)
 4.8 Triangular grids (triangulated)
 4.9 Hexagonal grids (triangulated)
 5 Surfaces in 3space
 5.1 Surface of polyhedra
 5.2 Spheres (triangulated)
 5.3 Cylinders (quadriangulated)
 5.4 Möbius bands (quadriangulated)
 5.5 Tori (quadriangulated)
 6 Surfaces in 4space
 7 ...
 8 Description of the algorithms used
 9 ...
 10 See also
Introduction
This article is about meanders in the sense of Jon Wild (defined below) and some of its generalizations. The number of meanders on a square grid of side (up to symmetry) was seen to be important enough that it was chosen to be A200000, the 200000^{ th} sequence of the OEIS.
Brief summary
Article abstract.
Brief history
Brief history of (this kind of) meanders.
Other definitions for meanders
Arnold meanders
(TODO: briefly describe)
Arnold meanders: A005315, A005316 and links therein.
Wienand meanders
(TODO: briefly describe)
Wienand meanders: A199932 and links therein, as described by Peter Luschny. (http://oeis.org/wiki/User:Peter_Luschny/Meander)
Acknowledgements
Several persons will go here!
Definitions of meanders
(...)
As equivalence classes of closed loops
Elementary level: consider a rectangular grid, , made of square tiles (chessboard). DESCRIBE the loops
Here is an example of a meander on a 5by3 grid:
IDs  Image  

S, H, W, 

General definition: the natural framework seems to be that of a CWcomplex. Given a CWcomplex of dimension , we consider the closed simple loops intersecting at least once every open cell, intersecting at most once every open cell, and intersecting no closed cell. In the twodimensional case, these cells are respectively the faces, edges and vertices. Homotopy through loops of this type is an equivalence relation. A meander is an equivalence class for this relation, but by abuse of language, we will also call meander a representant of such a class.
Here is an example of a meander on an irregular CWcomplex:
PICTURE [preferably, with irregular triangular, quadrilateral and pentagonal tiles]
A meander on a 2dimensional CWcomplex
As tilings
describe the possible tiles
tile  abbrev.  tile  abbrev.  

N 

H  

E 

V  

S 

A  

W 

B 
As a mnemonic, N, E, S, W stand for North, East, South, West (slightly tilt your head to the left) and H and V stand for horizontal and vertical.
Besides these eight square tiles, there is one additional tile, which, since meanders are closed loops (that is, are connected), can appear only on a onebyone grid.
tile  abbrev.  

O 
Equivalence of the two definitions
(...)
Relation with Hamiltonian cycles
We define the dual graph of a dimensional CWcomplex as the graph with vertices corresponding to the cells and with an edge between two vertices if the corresponding cells meet in a cell. Then a Hamiltonian cycle of that graph gives a meander of the original CWcomplex in an obvious way. Similarly, Hamiltonian paths give open meanders. The converse is in general wrong, as the above example of a meander on a (5,3)grid shows. We will see below that meanders have much more "flexibility".
Actually, Hamiltonian cycles correspond to the meanders that intersect each cell on a connected set. For instance, for tilings by squares, this amounts to forbidding tiles of type A or B.
Is there a onebyone meander?
Is there a meander on a single tile, or in terms of a CWcomplex, a meander on a single cell? This question becomes more important in the case of multimeanders.
In the CWcomplex definition, there is no obstruction to a meander on a single cell.
Not yet settled.
Meanders up to symmetry
When the grid or CWcomplex has certain symmetries, we will also study the set of "meanders up to symmetry". For instance, the symmetries of a square grid form the dihedral group D_{4} with 8 elements, and the symmetries that preserve orientation form the cyclic group C_{4} of order 4, which sits as a subgroup of index 2 of D_{4}. For rectangular grids, and other grids, we will consider the relevant symmetry groups and the corresponding "meanders up to symmetry", that is, the equivalence classes (or orbits) of meanders under the action of the given symmetry group.
Generalizations
Selfcrossing meanders
The other generalization is to allow selfcrossings. In terms of loops: we consider all closed loops, and not only the simple ones. Equivalently, we consider immersions of the circle, and not only embeddings. In terms of tilings this amounts to allowing one new tile,
tile  abbrev.  

X 
We can also distinguish between over and undercrossing, adding the two tiles
tile  abbrev.  

C  

D 
Multimeanders
There are two natural generalizations of meanders. The first is to drop the connectedness requirement. We call "not necessarily connected meanders" multimeanders.
In the CWcomplex definition, one has to impose that if a given closed cell contains a connected component of a multimeander, then it does not intersect any other connected component of that multimeander. Or we can more drastically forbid that any closed cell contain a connected component of a multimeander.
We will see below that multimeanders are much simpler to compute. This is because, using the tiling definition, there are only local conditions to check (that adjacent tiles match), whereas connectedness is a global condition (except on some small grids), and is therefore much harder to check.
Both generalizations at once
Finally, we can obviously consider these two generalizations at once, leading to either multi selfcrossing meanders, mutuallycrossing multimeanders or mutuallycrossing selfcrossing multimeanders.
Multi selfcrossing meanders
This is the case where disconnected meanders are not allowed to cross each other, but each meander is allowed to be selfcrossing.
Mutuallycrossing multimeanders
This is the case where disconnected meanders are allowed to cross each other, but each meander is not allowed to be selfcrossing.
Mutuallycrossing selfcrossing multimeanders
This is the case where both disconnected meanders are allowed to cross each other and each meander is allowed to be selfcrossing.
Multimeanders on rectangular grids
Although meanders are the main objects of interest, we begin with multimeanders, which are easier to count. We denote by the number of multimeanders on an grid.
We give a construction to find using a double induction (corresponding to the two dimensions of the grid). The idea is to first find a linear recurrence relation on given by a matrix , and then to construct the matrices using another induction.
The first step is as follows....
For the second step...
[HOW to have both tiles on the same row in the last cell?]
So, in summary:
Define two symmetric functions A and B on couples of words on {0,1} of same length by induction on that length, as follows:
Let A_k be the matrix whose rows and columns are labelled by the words of size k with an even number of 1's (in any order, say lexicographic order). Then the number of multimeanders on an (n,k)grid is given by TT(n,k) = [(A_k)^n]_{0,0} the (0,0)entry of the nth power of A_k.
Remark: the matrix A has size 2^(k1) if k>0 and 1 if k=0.
Examples:
For A and B, the first step gives A(0,0) = A(0,1) = 0 ; A(1,1) = 1 ; B(0,0) = B(1,1) = 0 ; B(0,1) = 1.
The first few matrices A_k are
A_0 = (1) gives the empty multimeander on the empty grid
A_1 = (0) proves that TT(1,k)=0 (including on the (1,1)grid, which is normal since I used the definition without the special tile)
A_2 = (0,1;1,1) so the TT(2,k) are the Fibonacci numbers (shifted by one)
A_3 = (0,0,1,0;0,0,1,2;1,1,0,1;0,2,1,0)
Explanation:
A(i,j) is the number of open multimeanders on an (n,1)grid (where n is the common length of i and j), with "ends" on the left/right edge given by the words i/j; and similarly for B with in addition one end on the "top" edge.
A(empty,empty) = 1: the empty tiling
B(empty,empty) = 0: one cannot have one end and be empty
Multimeanders with crossings
When crossings are allowed, then the above is still valid with the only modification of B(1i,1j) = 2 B(i,j) into B(1i,1j) = 3 B(i,j). Indeed, as seen in the above table, the coefficient 2 accounts for the tiles A and B when no crossing is allowed, and the coefficient 3 accounts for the tiles A, B and X when crossings are allowed.
relation  tile  
B(1i,1j) = 3 B(i,j) 

[HOW to have both tiles on the same row in the last cell?]
Meanders on rectangular grids
Meanders on rectangular grids
The number of meanders on an grid, , is given by A201145. We denote it by . Obviously, since there is a onetoone correspondence (90 o rotation) between each element of the two sets of meanders. The meanders for or for are trivial, where and
1  2  3  4  5  6  7  8  9  
1  1  0  0  0  0  0  0  0  0 
2  0  1  1  1  1  1  1  1  1 
3  0  1  0  2  2  6  10  22  42 
4  0  1  2  11  42  199  858  3881  17156 
5  0  1  2  42  320  3278  29904  285124  2671052 
6  0  1  6  199  3278  71648  1369736  ?  ? 
7  0  1  10  858  29904  1369736  55717584  ?  ? 
8  0  1  22  3881  285124  ?  ?  ?  ? 
9  0  1  42  17156  2671052  ?  ?  ?  ? 
(for further values, see ... [the page/bfile dedicated to that sequence, or an appendix; but no need to put too many terms here, IMHO, we might even stop at 7] )
Meanders on rectangular grids (up to symmetry)
(...)
Proof for S(n,3)
(...)
Meanders on rectangular grids (up to oriented symmetry)
(...)
Proof for T(n,3)
(...)
Selfcrossing meanders on rectangular grids
(...)
Multimeanders on rectangular grids
(...)
Selfcrossing multimeanders on rectangular grids
(...)
Square grids (quadriangulated)
Meanders on square grids
The main diagonal (highlighted) of meanders on rectangular grids (shown above).
It would be nice to know the asymptotic behavior...
Selfcrossing meanders on square grids
(...)
Multimeanders on square grids
(...)
Selfcrossing multimeanders on square grids
(...)
Rectangular grids with sides identified (quadriangulated)
Meanders on rectangular grids with sides identified
(...)
Selfcrossing meanders on rectangular grids with sides identified
(...)
Multimeanders on rectangular grids with sides identified
(...)
Selfcrossing multimeanders on rectangular grids with sides identified
(...)
Projective planes (triangulated)
Meanders on projective planes
(...)
Selfcrossing meanders on projective planes
(...)
Multimeanders on projective planes
(...)
Selfcrossing multimeanders on projective planes
(...)
Triangular grids (triangulated)
Meanders on triangular grids
DESCRIBE: triangular tiles (six kinds, two kinds up to rotation) (pictures...)
(...)
Selfcrossing meanders on triangular grids
(...)
Multimeanders on triangular grids
(...)
Selfcrossing multimeanders on triangular grids
(...)
Hexagonal grids (triangulated)
Meanders on hexagonal grids
DESCRIBE: hexagonal tiles (1 (x 3) + 1 (x 3) + 1 (x 6) + 1 (x 6) + 1 (x 2), 5 kinds up to rotation) (is that right?...) (pictures...)
(...)
Selfcrossing meanders on hexagonal grids
(...)
Multimeanders on hexagonal grids
(...)
Selfcrossing multimeanders on hexagonal grids
(...)
Surfaces in 3space
Surface of polyhedra
Meanders on the surface of polyhedra
We begin with/restrict to the simpler case: the surfaces of the five Platonic solids (i.e. convex regular polyhedra), with one tile per face.
DESCRIBE: triangular tiles (one kind up to rotation: picture) and pentagonal tiles (four kinds up to symmetry: pictures)
VISUALIZATION: show the nets.
Meanders on the surface of tetrahedrons
Triangular tiles. One meander up to symmetry, and three total. Actually, there are no other multimeanders.
Meanders on the surface of hexahedrons (cubes)
Square tiles. (...)
Meanders on the surface of octahedrons
Triangular tiles. (...)
Meanders on the surface of dodecaedrons
Pentagonal tiles. (...)
Meanders on the surface of icosahedrons
Triangular tiles. (...)
Selfcrossing meanders on the surface of polyhedra
(...)
Multimeanders on the surface of polyhedra
(...)
Selfcrossing multimeanders on the surface of polyhedra
(...)
Spheres (triangulated)
Meanders on spheres
(...)
Selfcrossing meanders on spheres
(...)
Multimeanders on spheres
(...)
Selfcrossing multimeanders on spheres
(...)
Cylinders (quadriangulated)
Meanders on cylinders
(...)
Selfcrossing meanders on cylinders
(...)
Multimeanders on cylinders
(...)
Selfcrossing multimeanders on cylinders
(...)
Möbius bands (quadriangulated)
Meanders on Möbius bands
(...)
Selfcrossing meanders on Möbius bands
(...)
Multimeanders on Möbius bands
(...)
Selfcrossing multimeanders on Möbius bands
(...)
Tori (quadriangulated)
Meanders on tori
(...)
Selfcrossing meanders on tori
(...)
Multimeanders on tori
(...)
Selfcrossing multimeanders on tori
(...)
Surfaces in 4space
Klein bottles (quadriangulated)
Meanders on Klein bottles
(...)
Selfcrossing meanders on Klein bottles
(...)
Multimeanders on Klein bottles
(...)
Selfcrossing multimeanders on Klein bottles
(...)
...
(...)
Description of the algorithms used
(...)
...
(...)
See also
 Meanders filling out an nbyk grid (reduced for symmetry)
 Meanders filling out an nbyn grid (reduced for symmetry)
 Meanders filling out an nbyk grid (not reduced for symmetry)
 Meanders filling out an nbyn grid (not reduced for symmetry)
 Selfcrossing meanders filling out an nbyk grid (reduced for symmetry)
 Selfcrossing meanders filling out an nbyn grid (reduced for symmetry)
 Selfcrossing meanders filling out an nbyk grid (not reduced for symmetry)
 Selfcrossing meanders filling out an nbyn grid (not reduced for symmetry)
 {{Meander}} graphic template
 Selfavoiding walks#Hamiltonian lattice walks (especially Hamiltonian lattice cycles)