This site is supported by donations to The OEIS Foundation.

Meanders filling out an n-by-k grid (not reduced for symmetry)

From OeisWiki

Jump to: navigation, search

This article page is a stub, please help by expanding it.


Meanders filling out an \scriptstyle n \,-by-\scriptstyle k \, grid, not reduced for symmetry:

Closed paths that visit every cell of an \scriptstyle n \,-by-\scriptstyle k \, rectangular lattice at least once, that never cross any edge between adjacent squares more than once, and are self-avoiding. Paths related by rotation and/or reflection of the square lattice are considered distinct.

Contents

Meanders filling out an n-by-k grid, not reduced for symmetry

The 1-by-1 grid has the distinct and unique meander with zero ID.

Meander for 1-by-1 grid
ID Image
0 File:Meander_1-by-1 (small).png

The \scriptstyle n \,-by-\scriptstyle k \, grid, \scriptstyle n \,\ge\, 2,\, 2 \,\le\,\, k \,\le\, n, \, has meanders which are built from the meander sections with nonzero IDs.

Meander sections
Image Abbreviation Abbreviation

(Benoît Jubin)

ID Valid IDs (left)
Valid IDs (above)
Valid IDs (right)
Valid IDs (below)
File:Meander LT & BR.png UD A -4 -4, -2, -1, +2, +4 -4, -2, +1, +3, +4 -4, -3, -1, +3, +4 -4, -3, +1, +2, +4
File:Meander LT.png LT or TL N -3 -4, -2, -1, +2, +4 -4, -2, +1, +3, +4 -2, +1, +2 -2, -1, +3
File:Meander BR.png BR or RB S -2 -3, +1, +3 -3, -1, +2 -4, -3, -1, +3, +4 -4, -3, +1, +2, +4
File:Meander LR.png LR or RL H -1 -4, -2, -1, +2, +4 -3, -1, +2 -4, -3, -1, +3, +4 -2, -1, +3
File:Meander BT.png BT or TB V +1 -3, +1, +3 -4, -2, +1, +3, +4 -2, +1, +2 -4, -3, +1, +2, +4
File:Meander TR.png TR or RT E +2 -3, +1, +3 -4, -2, +1, +3, +4 -4, -3, -1, +3, +4 -2, -1, +3
File:Meander LB.png LB or BL W +3 -4, -2, -1, +2, +4 -3, -1, +2 -2, +1, +2 -4, -3, +1, +2, +4
File:Meander LB & TR.png DD B +4 -4, -2, -1, +2, +4 -4, -2, +1, +3, +4 -4, -3, -1, +3, +4 -4, -3, +1, +2, +4

The sum of meander section IDs is 0 for a meander with horizontal and vertical symmetry. The sum of meander section IDs is 0 for the four corners (-2, +3, +2, -3.)

For the \scriptstyle n \,-by-\scriptstyle k \, grid, we need to solve \scriptstyle nk - 4,\, n \,\ge\, 2,\,2 \,\le\, k \,\le\, n, \, cells. For each cell, there are up to 8 tiles to choose from, giving \scriptstyle 8^{nk - 4},\, n \,\ge\, 2,\,2 \,\le\, k \,\le\, n, \, possible (valid or invalid) configurations.

Number of meanders filling out an n-by-k grid, not reduced for symmetry

Number of meanders T(n, k) filling out an \scriptstyle n \,-by-\scriptstyle k \, grid, not reduced for symmetry
\scriptstyle n \, = 1 1
2 0 1
3 0 1 0
4 0 1 2 11
5 0 1 2 42 320
6 0 1 6 199 3278 71648
7 0 1 10 858 29904 1369736 55717584
8 0 1 22 3881 285124 ? ? ?
9 0 1 42 17156 2671052 ? ? ? ?
10 0 1 ? ? ? ? ? ? ? ?
11 0 1 ? ? ? ? ? ? ? ? ?
12 0 1 ? ? ? ? ? ? ? ? ? ?
13 0 1 ? ? ? ? ? ? ? ? ? ? ?
\scriptstyle k \, = 1 2 3 4 5 6 7 8 9 10 11 12 13

Number of meanders filling out an n-by-3 grid, not reduced for symmetry

Meanders for 4-by-3 grid
Code Image
{{Meander|4|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -3, +1,,
+2, -1, -3,,
}}

(2 orientations)

Image:Meander BR.png Image:Meander LR.png Image:Meander LB.png
Image:Meander TR.png Image:Meander LB.png Image:Meander BT.png
Image:Meander BR.png Image:Meander LT.png Image:Meander BT.png
Image:Meander TR.png Image:Meander LR.png Image:Meander LT.png

Meanders for 5-by-3 grid
Code Image
{{Meander|5|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -4, -3,,
+1, +2, +3,,
+2, -1, -3,,
}}

(2 orientations)

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

Meanders for 6-by-3 grid
Code Image Code Image Code Image
{{Meander|6|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -3, +1,,
+1, -2, -3,,
+1, +2, +3,,
+2, -1, -3,,
}}

(2 orientations)

Image:Meander BR.png Image:Meander LR.png Image:Meander LB.png
Image:Meander TR.png Image:Meander LB.png Image:Meander BT.png
Image:Meander BR.png Image:Meander LT.png Image:Meander BT.png
Image:Meander BT.png Image:Meander BR.png Image:Meander LT.png
Image:Meander BT.png Image:Meander TR.png Image:Meander LB.png
Image:Meander TR.png Image:Meander LR.png Image:Meander LT.png
{{Meander|6|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -3, +1,,
+2, +3, +1,,
-2, -3, +1,,
+2, -1, -3,,
}}

(2 orientations)

Image:Meander BR.png Image:Meander LR.png Image:Meander LB.png
Image:Meander TR.png Image:Meander LB.png Image:Meander BT.png
Image:Meander BR.png Image:Meander LT.png Image:Meander BT.png
Image:Meander TR.png Image:Meander LB.png Image:Meander BT.png
Image:Meander BR.png Image:Meander LT.png Image:Meander BT.png
Image:Meander TR.png Image:Meander LR.png Image:Meander LT.png
{{Meander|6|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -4, -3,,
+2, +4, +3,,
-2, -3, +1,,
+2, -1, -3,,
}}

(2 orientations)

Image:Meander BR.png Image:Meander LR.png Image:Meander LB.png
Image:Meander TR.png Image:Meander LB.png Image:Meander BT.png
Image:Meander BR.png Image:Meander LT & BR.png Image:Meander LT.png
Image:Meander TR.png Image:Meander LB & TR.png Image:Meander LB.png
Image:Meander BR.png Image:Meander LT.png Image:Meander BT.png
Image:Meander TR.png Image:Meander LR.png Image:Meander LT.png
Proof concerning T(n, 3)

\scriptstyle T(n, 3),\, n \,\ge\, 3, \, might match either of (if so, how could this be proved?):

A078008 Expansion of (1-x)/(1-x-2*x^2), n >= 0. (thus T(n, 3) = a(n-2), n >= 3)
{1, 0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, 1366, 2730, 5462, 10922, 21846, 43690, 87382, ...}
A014113 a(n) = 2^n - a(n-1), or a(n)=a(n-1)+2a(n-2), n >= 0. (thus T(n, 3) = a(n-3), n >= 3)
{0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, 1366, 2730, 5462, 10922, 21846, 43690, 87382, ...}
Comment from Jon Wild: further entries in the sequence indicate that it continues to match A078008. I do not know how to prove it, but Benoît Jubin, writing on the seqfan email list (Nov 22 2011), said it was not difficult to prove.
Would you please ask Benoît Jubin to add the proof to this wiki page. — Daniel Forgues 05:15, 28 November 2011 (UTC)

Proof from Benoît Jubin (in french) that T(n, 3) = A078008(n-2) , n ≥ 3:


(...)

Voici ma preuve pour a(n) = T(3,n) (sans symétries). Vous pourrez sûrement la rendre plus jolie en utilisant les images des méandres.

Pour les abréviations des pièces du puzzle, je préfère qu'elles soient toutes données pour une seule lettre majuscule: voici le dictionnaire entre vos et mes abréviations:
LR = H (pour Horizontal)
BT = V (pour Vertical)
LT = N (pour North)
BR = S (pour South)
TR = E (pour East)
LB = W (pour West)
LT&BR = A
LB&TR = B

Les méandres sur la grille (3,n) sont de la forme:
S.........W
V..(n-2)..V
E.........N
où le (n-2) signifie qu'il y a (n-2) colonnes. Maintenant, tous ces méandres sont dans exactement un des cas de figures suivants ou son symétrique haut-bas:
SHH..
VSW..(n-4)
ENE..
ou
SHWS
VSBN..(n-5)
ENEH..
ou
SHWSH..
VSBAW..(n-6)
ENENE..
ou
SHWSWS..
VSBABN..(n-7)
ENENEH..
ou
...etc jusqu'à (n-n).
En prenant en compte la symétrie haut-bas, ceci donne
a(n) = 2 * ( a(n-2) + a(n-3) + ... + a(2) )
avec bien entendu a(2) = 1.

Le fait que ces cas de figures conduisent à des méandres différents est évident, puisque les débuts de méandres sont différents. Le fait qu'ils représentent tous les cas de figures repose sur deux raisons:
* les cases de la rangée du milieu doivent être visitées, ce qui entraîne qu'aucune colonne ne peut être de la forme (ligne horizontale; quelque chose; ligne horizontale).
* si une ligne verticale (de séparation entre cases) est traversée aux niveaux haut et bas (et pas milieu), alors on peut couper le méandre en deux sous-méandres: c'est pourquoi dans les débuts de méandres ci-dessus, aucune ligne verticale n'est traversée ainsi, mais au contraire est traversée (haut,milieu) ou (bas,milieu).

C'est beaucoup plus simple à expliquer de vive voix devant un tableau, mais je pense que c'est compréhensible comme ça.

(...)

Benoît

Meanders filling out an n-by-n grid (not reduced for symmetry)

Meanders filling out an n-by-n grid, not reduced for symmetry:

Closed paths that visit every cell of an n-by-n square lattice at least once, that never cross any edge between adjacent squares more than once, and that do not self-intersect. Paths related by rotation and/or reflection of the square lattice are considered distinct.

For the n-by-n grid, we need to solve \scriptstyle n^2 - 4 \,=\, (n-2) (n+2),\, n \,\ge\, 2, \, cells. For each cell, there are up to 8 tiles to choose from, giving \scriptstyle 8^{n^2 - 4},\, n \,\ge\, 2, \, possible (valid or invalid) configurations.

Meanders filling out an 1-by-1 grid (not reduced for symmetry)

Cf. Meanders filling out an 1-by-1 grid (reduced for symmetry).

Meanders filling out an 2-by-2 grid (not reduced for symmetry)

Cf. Meanders filling out an 2-by-2 grid (reduced for symmetry).

Meanders filling out an 3-by-3 grid (not reduced for symmetry)

There are no single closed path meanders for the 3-by-3 grid, since the edges must join the corners, leaving the center unvisited.

Cf. Meanders filling out an 3-by-3 grid (reduced for symmetry).

Meanders filling out an 4-by-4 grid (not reduced for symmetry)

There are 11 oriented meanders.

Cf. Meanders filling out an 4-by-4 grid (reduced for symmetry).

Meanders filling out an 5-by-5 grid (not reduced for symmetry)

There are 320 oriented meanders.

Cf. Meanders filling out an 5-by-5 grid (reduced for symmetry).

Meanders filling out an 6-by-6 grid (not reduced for symmetry)

There are 71648 oriented meanders.

Cf. Meanders filling out an 6-by-6 grid (reduced for symmetry).

Self-crossing meanders filling out an n-by-k grid (not reduced for symmetry)

(...)

Self-crossing meanders filling out an n-by-n grid (not reduced for symmetry)

(...)

Sequences

A200000 Number of meanders filling out an n-by-n, grid, reduced for symmetry, n ≥ 1.

{1, 1, 0, 4, 42, 9050, 6965359, ...}

A200749 Number of meanders filling out an n-by-n grid, not reduced for symmetry, n ≥ 1.

{1, 1, 0, 11, 320, 71648, 55717584, ...}

A200893 Triangle read by rows: number of meanders filling out an n by k grid, reduced for symmetry, n ≥ 1, 1 ≤ k ≤ n.

{1, 0, 1, 0, 1, 0, 0, 1, 1, 4, 0, 1, 1, 14, 42, 0, 1, 3, 63, 843, 9050, 0, 1, 3, 224, 7506, 342743, 6965359, 0, 1, 8, 1022, 71542, 6971973, ...}

A201145 Triangle read by rows: number of meanders filling out an n by k grid, not reduced for symmetry, n ≥ 1, 1 ≤ k ≤ n.

{1, 0, 1, 0, 1, 0, 0, 1, 2, 11, 0, 1, 2, 42, 320, 0, 1, 6, 199, 3278, 71648, 0, 1, 10, 858, 29904, 1369736, 55717584, 0, 1, 22, 3881, 285124, ...}

See also






Personal tools