This site is supported by donations to The OEIS Foundation.

# Meanders

Please do not rely on any information it contains.

## 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 ${\displaystyle \scriptstyle n\,}$ (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 ${\displaystyle \scriptstyle n\times k\,}$ grid, ${\displaystyle \scriptstyle k\,\leq \,n\,}$, made of square tiles (chessboard). DESCRIBE the loops

Here is an example of a meander on a 5-by-3 grid:

A meander on a (5,3)-grid
IDs Image

S, H, W,
E, W, V,
S, A, N,
V, E, W,
E, H, N,

(2 orientations)

General definition: the natural framework seems to be that of a CW-complex. Given a CW-complex of dimension ${\displaystyle \scriptstyle d\,}$, we consider the closed simple loops intersecting at least once every open ${\displaystyle \scriptstyle d\,}$-cell, intersecting at most once every open ${\displaystyle \scriptstyle (d-1)\,}$-cell, and intersecting no closed ${\displaystyle \scriptstyle (d-2)\,}$-cell. In the two-dimensional 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 CW-complex:

PICTURE [preferably, with irregular triangular, quadrilateral and pentagonal tiles]
A meander on a 2-dimensional CW-complex

### As tilings

describe the possible tiles

Square 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 one-by-one grid.

Square tiles (continued)
tile abbrev.
O

(...)

### Relation with Hamiltonian cycles

We define the dual graph of a ${\displaystyle \scriptstyle d\,}$-dimensional CW-complex as the graph with vertices corresponding to the ${\displaystyle \scriptstyle d\,}$-cells and with an edge between two vertices if the corresponding ${\displaystyle \scriptstyle d\,}$-cells meet in a ${\displaystyle \scriptstyle (d-1)\,}$-cell. Then a Hamiltonian cycle of that graph gives a meander of the original CW-complex 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 ${\displaystyle d}$-cell on a connected set. For instance, for tilings by squares, this amounts to forbidding tiles of type A or B.

### Is there a one-by-one meander?

Is there a meander on a single tile, or in terms of a CW-complex, a meander on a single ${\displaystyle \scriptstyle d\,}$-cell? This question becomes more important in the case of multimeanders.

In the CW-complex definition, there is no obstruction to a meander on a single ${\displaystyle \scriptstyle d\,}$-cell.

Not yet settled.

### Meanders up to symmetry

When the grid or CW-complex 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 D4 with 8 elements, and the symmetries that preserve orientation form the cyclic group C4 of order 4, which sits as a subgroup of index 2 of D4. 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

#### Self-crossing meanders

The other generalization is to allow self-crossings. 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,

Additional square tile for self-crossing meanders
tile abbrev.
X

We can also distinguish between over- and under-crossing, adding the two tiles

Additional square tiles for self-crossing meanders with over/under-crossing distinction
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 CW-complex definition, one has to impose that if a given closed ${\displaystyle \scriptstyle d\,}$-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 ${\displaystyle \scriptstyle d\,}$-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 self-crossing meanders, mutually-crossing multimeanders or mutually-crossing self-crossing multimeanders.

##### Multi self-crossing meanders

This is the case where disconnected meanders are not allowed to cross each other, but each meander is allowed to be self-crossing.

##### Mutually-crossing multimeanders

This is the case where disconnected meanders are allowed to cross each other, but each meander is not allowed to be self-crossing.

##### Mutually-crossing self-crossing multimeanders

This is the case where both disconnected meanders are allowed to cross each other and each meander is allowed to be self-crossing.

## Multimeanders on rectangular grids

Although meanders are the main objects of interest, we begin with multimeanders, which are easier to count. We denote by ${\displaystyle TT(n,k)}$ the number of multimeanders on an ${\displaystyle (n,k)}$-grid.

We give a construction to find ${\displaystyle TT(n,k)}$ using a double induction (corresponding to the two dimensions of the grid). The idea is to first find a linear recurrence relation on ${\displaystyle n}$ given by a matrix ${\displaystyle A_{k}}$, and then to construct the matrices ${\displaystyle A_{k}}$ using another induction.

The first step is as follows....

For the second step...

Recurrence relations
relation tile relation tile
A(0i,0j) = 0 (empty) B(0i,0j) = B(i,j)
A(0i,1j) = B(i,j) B(0i,1j) = A(i,j),
A(1i,0j) = B(i,j) B(1i,0j) = A(i,j),
A(1i,1j) = A(i,j) B(1i,1j) = 2 B(i,j) &

[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:

${\displaystyle A(\varnothing ,\varnothing )=1,B(\varnothing ,\varnothing )=0}$

${\displaystyle A(0i,0j)=0,A(0i,1j)=B(i,j),A(1i,1j)=A(i,j)}$

${\displaystyle B(0i,0j)=B(i,j),B(0i,1j)=A(i,j),B(1i,1j)=2B(i,j)}$

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 n-th power of A_k.

Remark: the matrix A has size 2^(k-1) 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.

Recurrence relations
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 ${\displaystyle \scriptstyle (n,k)\,}$-grid, ${\displaystyle \scriptstyle k\,\leq \,n\,}$, is given by A201145. We denote it by ${\displaystyle \scriptstyle T(n,k)\,}$. Obviously, ${\displaystyle \scriptstyle T(n,k)\,=\,T(k,n)\,}$ since there is a one-to-one correspondence (90 o rotation) between each element of the two sets of meanders. The meanders for ${\displaystyle \scriptstyle T(n,k)\,}$ or ${\displaystyle \scriptstyle T(k,n)\,}$ for ${\displaystyle \scriptstyle k\,\leq \,2\,}$ are trivial, where ${\displaystyle \scriptstyle T(1,k)\,=\,T(n,1)\,=\,0^{\{(n-1)+(k-1)\}}\,}$ and ${\displaystyle \scriptstyle T(2,k)\,=\,T(n,2)\,=\,1.\,}$

 ${\displaystyle \scriptstyle n\backslash k\,}$ 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/b-file 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 square grids

The main diagonal (highlighted) of meanders on rectangular grids (shown above).

It would be nice to know the asymptotic behavior...

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

### Triangular grids (triangulated)

#### Meanders on triangular grids

DESCRIBE: triangular tiles (six kinds, two kinds up to rotation) (pictures...)

(...)

(...)

(...)

(...)

### 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...)

(...)

(...)

(...)

(...)

## Surfaces in 3-space

### 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. (...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)