This site is supported by donations to The OEIS Foundation.
Meanders filling out an n-by-k grid (not reduced for symmetry)
There are no approved revisions of this page, so it may not have been
Meanders filling out an -by- grid, not reduced for symmetry:
- Closed paths that visit every cell of an -by- 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
- 1 Meanders filling out an n-by-k grid, not reduced for symmetry
- 2 Number of meanders filling out an n-by-k grid, not reduced for symmetry
- 3 Meanders filling out an n-by-n grid (not reduced for symmetry)
- 3.1 Meanders filling out an 1-by-1 grid (not reduced for symmetry)
- 3.2 Meanders filling out an 2-by-2 grid (not reduced for symmetry)
- 3.3 Meanders filling out an 3-by-3 grid (not reduced for symmetry)
- 3.4 Meanders filling out an 4-by-4 grid (not reduced for symmetry)
- 3.5 Meanders filling out an 5-by-5 grid (not reduced for symmetry)
- 3.6 Meanders filling out an 6-by-6 grid (not reduced for symmetry)
- 4 Self-crossing meanders filling out an n-by-k grid (not reduced for symmetry)
- 5 Sequences
- 6 See also
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.
| ID | Image |
|---|---|
| 0 | .png){kind=small}
|
The -by- grid, has meanders which are built from the meander sections with nonzero IDs.
| Image | Abbreviation | Abbreviation | ID | Valid IDs (left) |
Valid IDs (above) |
Valid IDs (right) |
Valid IDs (below) |
|---|---|---|---|---|---|---|---|
 |
UD | A | -4 | -4, -2, -1, +2, +4 | -4, -2, +1, +3, +4 | -4, -3, -1, +3, +4 | -4, -3, +1, +2, +4 |
 |
LT or TL | N | -3 | -4, -2, -1, +2, +4 | -4, -2, +1, +3, +4 | -2, +1, +2 | -2, -1, +3 |
 |
BR or RB | S | -2 | -3, +1, +3 | -3, -1, +2 | -4, -3, -1, +3, +4 | -4, -3, +1, +2, +4 |
 |
LR or RL | H | -1 | -4, -2, -1, +2, +4 | -3, -1, +2 | -4, -3, -1, +3, +4 | -2, -1, +3 |
 |
BT or TB | V | +1 | -3, +1, +3 | -4, -2, +1, +3, +4 | -2, +1, +2 | -4, -3, +1, +2, +4 |
 |
TR or RT | E | +2 | -3, +1, +3 | -4, -2, +1, +3, +4 | -4, -3, -1, +3, +4 | -2, -1, +3 |
 |
LB or BL | W | +3 | -4, -2, -1, +2, +4 | -3, -1, +2 | -2, +1, +2 | -4, -3, +1, +2, +4 |
 |
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 -by- grid, we need to solve cells. For each cell, there are up to 8 tiles to choose from, giving 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 -by- grid, not reduced for symmetry = 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 ? ? ? ? ? ? ? ? ? ? ? = 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
| Code | Image | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
{{Meander|4|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -3, +1,,
+2, -1, -3,,
}}
(2 orientations) |
|
| Code | Image | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
{{Meander|5|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -4, -3,,
+1, +2, +3,,
+2, -1, -3,,
}}
(2 orientations) |
|
| 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) |
|
{{Meander|6|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -3, +1,,
+2, +3, +1,,
-2, -3, +1,,
+2, -1, -3,,
}}
(2 orientations) |
|
{{Meander|6|3|
-2, -1, +3,,
+2, +3, +1,,
-2, -4, -3,,
+2, +4, +3,,
-2, -3, +1,,
+2, -1, -3,,
}}
(2 orientations) |
|
Proof concerning T(n, 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 cells. For each cell, there are up to 8 tiles to choose from, giving 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
- Meanders filling out an n-by-k grid (reduced for symmetry)
- Meanders filling out an n-by-n grid (reduced for symmetry)
- Meanders filling out an n-by-k grid (not reduced for symmetry)
- Meanders filling out an n-by-n grid (not reduced for symmetry)
- Self-crossing meanders filling out an n-by-k grid (reduced for symmetry)
- Self-crossing meanders filling out an n-by-n 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)
- {{Meander}} graphic template
