This site is supported by donations to The OEIS Foundation.

Meanders

From OeisWiki
Jump to: navigation, search


This article is under construction.            

Please do not rely on any information it contains.            


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

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

Meander BR.png Meander LR.png Meander LB.png
Meander TR.png Meander LB.png Meander BT.png
Meander BR.png Meander LT & BR.png Meander LT.png
Meander BT.png Meander TR.png Meander LB.png
Meander TR.png Meander LR.png Meander LT.png

General definition: the natural framework seems to be that of a CW-complex. Given a CW-complex 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 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.
Meander LT.png
N
Meander LR.png
H
Meander TR.png
E
Meander BT.png
V
Meander BR.png
S
Meander LT & BR.png
A
Meander LB.png
W
Meander LB & TR.png
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.
Meander 1-by-1 (small).png
O

Equivalence of the two definitions

(...)

Relation with Hamiltonian cycles

We define the dual graph of a -dimensional CW-complex 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 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 -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 -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 -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.
Meander X.png
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.
Meander XH.png
C
Meander XV.png
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 -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 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 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...



Recurrence relations
relation tile relation tile
A(0i,0j) = 0 (empty) B(0i,0j) = B(i,j)
Meander BT.png
A(0i,1j) = B(i,j)
Meander BR.png
B(0i,1j) = A(i,j),
Meander TR.png
A(1i,0j) = B(i,j)
Meander LB.png
B(1i,0j) = A(i,j),
Meander LT.png
A(1i,1j) = A(i,j)
Meander LR.png
B(1i,1j) = 2 B(i,j)
Meander LT & BR.png
&
Meander LB & TR.png

[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 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)
Meander LT & BR.png
&
Meander LB & TR.png
&
Meander X.png

[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 one-to-one correspondence (90 o rotation) between each element of the two sets of meanders. The meanders for or for are trivial, where and

Number of meanders on an -grid
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 rectangular grids (up to symmetry)

(...)

Proof for S(n,3)

(...)

Meanders on rectangular grids (up to oriented symmetry)

(...)

Proof for T(n,3)

(...)

Self-crossing meanders on rectangular grids

(...)

Multimeanders on rectangular grids

(...)

Self-crossing 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...

Self-crossing meanders on square grids

(...)

Multimeanders on square grids

(...)

Self-crossing multimeanders on square grids

(...)

Rectangular grids with sides identified (quadriangulated)

Meanders on rectangular grids with sides identified

(...)

Self-crossing meanders on rectangular grids with sides identified

(...)

Multimeanders on rectangular grids with sides identified

(...)

Self-crossing multimeanders on rectangular grids with sides identified

(...)

Projective planes (triangulated)

Meanders on projective planes

(...)

Self-crossing meanders on projective planes

(...)

Multimeanders on projective planes

(...)

Self-crossing multimeanders on projective planes

(...)

Triangular grids (triangulated)

Meanders on triangular grids

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

(...)

Self-crossing meanders on triangular grids

(...)

Multimeanders on triangular grids

(...)

Self-crossing 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...)

(...)

Self-crossing meanders on hexagonal grids

(...)

Multimeanders on hexagonal grids

(...)

Self-crossing multimeanders on hexagonal grids

(...)

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

Self-crossing meanders on the surface of polyhedra

(...)

Multimeanders on the surface of polyhedra

(...)

Self-crossing multimeanders on the surface of polyhedra

(...)

Spheres (triangulated)

Meanders on spheres

(...)

Self-crossing meanders on spheres

(...)

Multimeanders on spheres

(...)

Self-crossing multimeanders on spheres

(...)

Cylinders (quadriangulated)

Meanders on cylinders

(...)

Self-crossing meanders on cylinders

(...)

Multimeanders on cylinders

(...)

Self-crossing multimeanders on cylinders

(...)

Möbius bands (quadriangulated)

Meanders on Möbius bands

(...)

Self-crossing meanders on Möbius bands

(...)

Multimeanders on Möbius bands

(...)

Self-crossing multimeanders on Möbius bands

(...)

Tori (quadriangulated)

Meanders on tori

(...)

Self-crossing meanders on tori

(...)

Multimeanders on tori

(...)

Self-crossing multimeanders on tori

(...)

Surfaces in 4-space

Klein bottles (quadriangulated)

Meanders on Klein bottles

(...)

Self-crossing meanders on Klein bottles

(...)

Multimeanders on Klein bottles

(...)

Self-crossing multimeanders on Klein bottles

(...)

...

(...)

Description of the algorithms used

(...)

...

(...)

See also