(Redirected from Number of meanders filling out an n-by-n grid (reduced for symmetry))
There are no approved revisions of this page, so it may
not have been
reviewed.
This article page is a stub, please help by expanding it.
Meanders filling out an
grid, reduced for symmetry:
- Closed paths that visit every cell of an 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 not considered distinct.
Meanders filling out an n × k grid, reduced for symmetry
The 1 × 1 grid has the distinct and unique meander with zero ID.
Meander for 1 × 1 grid
| ID
|
Image
|
| 0
|
|
The
grid,
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)
|
 |
UD |
A |
−4 |
−4, −2, −1, +2, +4 |
−4, −2, +1, +3, +4 |
−4, −3, −1, +3, +4 |
−4, −3, +1, +2, +4
|
 |
LT (WN) or TL (NW) |
N |
−3 |
−4, −2, −1, +2, +4 |
−4, −2, +1, +3, +4 |
−2, +1, +2 |
−2, −1, +3
|
 |
BR (SE) or RB (ES) |
S |
−2 |
−3, +1, +3 |
−3, −1, +2 |
−4, −3, −1, +3, +4 |
−4, −3, +1, +2, +4
|
 |
LR (WE) or RL (EW) |
H |
−1 |
−4, −2, −1, +2, +4 |
−3, −1, +2 |
−4, −3, −1, +3, +4 |
−2, −1, +3
|
 |
BT (SN) or TB (NS) |
V |
+1 |
−3, +1, +3 |
−4, −2, +1, +3, +4 |
−2, +1, +2 |
−4, −3, +1, +2, +4
|
 |
TR (NE) or RT (EN) |
E |
+2 |
−3, +1, +3 |
−4, −2, +1, +3, +4 |
−4, −3, −1, +3, +4 |
−2, −1, +3
|
 |
LB (WS) or BL (SW) |
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
grid, we need to solve
| n k − 4, n ≥ 2, 2 ≤ k ≤ n, |
cells. For each cell, there are up to 8 tiles to choose from, giving
| 8 n k − 4, n ≥ 2, 2 ≤ k ≤ n, |
possible (valid or invalid) configurations.
Meanders filling out a 4 × 3 grid, reduced for symmetry
Meanders for 4 × 3 grid
| Code
|
Image
|
{{Meander|4|3|
-2, -1, +3,,
+1, -2, -3,,
+1, +2, +3,,
+2, -1, -3,,
}}
(2 orientations)
|
|
Number of meanders filling out an n × k grid, reduced for symmetry
Number of meanders filling out an grid, reduced for symmetry
|
|
|
| 1
|
|
1
|
|
| 2
|
|
0
|
1
|
|
| 3
|
|
0
|
1
|
0
|
|
| 4
|
|
0
|
1
|
1
|
4
|
|
| 5
|
|
0
|
1
|
1
|
14
|
42
|
|
| 6
|
|
0
|
1
|
3
|
63
|
843
|
9050
|
|
| 7
|
|
0
|
1
|
3
|
224
|
7506
|
342743
|
6965359
|
|
| 8
|
|
0
|
1
|
8
|
1022
|
71542
|
6971973
|
?
|
?
|
|
| 9
|
|
0
|
1
|
12
|
4314
|
668042
|
?
|
?
|
?
|
?
|
|
| 10
|
|
0
|
1
|
?
|
?
|
?
|
?
|
?
|
?
|
?
|
?
|
|
|
|
|
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
|
Conjecture concerning S (n, 3)
might match
A090597 (if so, how could this be proved?).
- Comment from Jon Wild: I have extended the sequence for S(n,3) beyond the entries currently appearing here, and it continues to match A090597 as far as I can test it. I do not know how to prove it.
- This is thus a conjecture. — Daniel Forgues 05:32, 28 November 2011 (UTC)
A090597 | a (n) = − a (n − 1) + 5 [a (n − 2) + a (n − 3)] − 2 [a (n − 4) + a (n − 5)] − 8 [a (n − 6) + a (n − 7)], n ≥ 3. |
(Thus
)
-
{0, 1, 1, 3, 3, 8, 12, 27, 45, 96, 176, 363, 693, 1408, 2752, 5547, 10965, 22016, 43776, 87723, 174933, 350208, 699392, 1399467, 2796885, 5595136, 11186176, 22375083, 44741973, 89489408, ...}
Proposition concerning S (n, 3)
Proposition. (David Scambler 03:45, 19 December 2011 (UTC))
-
Closed form solution:
-
| S (n, 3) = , n odd; S (n, 3) = , n even; n ≥ 3, |
where is a Jacobsthal number (see A001045).
Proof. (Verify: proposition concerning S (n, 3).) [1]
First, by algebraic manipulation it can be shown that the closed form satisfies the given recurrence.
The geometry of -long, 3-high meanders is such that the lower track (1) and the upper track (3) take turns moving in and out of the middle (2) row. Considering the middle row only at the borders joining adjacent cells it must be the case that track (1), track (3) or neither (2) crosses the border. At the extremes the first and last middle-row borders are crossed by neither track and may be ignored for the time being. There are therefore borders to consider. A meander can be fully specified by a list of letters from the alphabet {1, 2, 3}, one for each border crossing. To eliminate top-bottom symmetry assume that it is track 1 that first enters the middle row starting from the left. It is clear that there can be no repeated identical letters since that would cause a cell to be skipped. We therefore arrive at words that start with 1, end with 1 or 3 and have no repeats. Such words of length are counted by the Jacobsthal number .
It remains to evaluate left-right and rotational symmetries. Left-right words are symmetrical if they are the same read backwards. They are rotationally symmetrical if they are the same read backwards while exchanging 1s and 3s. It is necessary to consider even and odd length words separately.
Odd length words:
- A word of odd length (e.g. 1231321, ) is left-right symmetrical when the left half matches the reversed right half, e.g. 1[23]1[32]1. There are such half-words. For rotational symmetry the middle letter must be 2 to remain fixed under the transformation, e.g. 1[23]2[12]3. The left side cannot end with 2 otherwise a duplicate letter results. The left side is now of length as before but must end in 1 or 3. These words are counted by . An odd-length word may have left-right symmetry or rotational symmetry but not both.
Even length words:
- A word of even length (e.g. 123123, )) cannot be left-right symmetrical because the middle two letters would need to be identical. For rotational symmetry the left side is of length as above and must end in 1 or 3, e.g. 1[23][12]3. These words are also counted by
- To obtain the results we first assume that the rotation or flipping of each meander maps to a redundant partner. We then adjust for the symmetrical meanders, which map to themselves. So we halve the number of meanders and add back half of the symmetrical meanders. Recalling that an meander has borders of which 2 were ignored, such meanders with top-bottom symmetry removed are counted by .
Applying these results we get:
-
| n odd: S (n, s) = J (n − 3) + J ( ), n ≥ 3, |
-
| n even: S (n, s) = J (n − 3) + J ( ) + 2 , n ≥ 4. |
Simplifying the latter yields | S (n, 3) = , n odd; S (n, 3) = , n even; n ≥ 3, |
where , completing the proof. □
Meanders filling out an n × n grid (reduced for symmetry)
Meanders filling out an
grid, reduced for symmetry:
- Closed paths that visit every cell of an 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 not considered distinct.
For the
grid, we need to solve
| n 2 − 4 = (n − 2) (n + 2), n ≥ 2, |
cells. For each cell, there are up to 8 tiles to choose from, giving
possible (valid or invalid) configurations.
Meanders filling out a 1 × 1 grid (reduced for symmetry)
The 1 × 1 grid has the distinct and unique meander
Meander for 1 × 1 grid
| Code
|
Image
|
{{Meander|1|1|
0,,
}}
|
|
Meanders filling out a 2 × 2 grid (reduced for symmetry)
Trivial case.
Meander for 2 × 2 grid
| Code
|
Image
|
{{Meander|2|2|
-2, +3,,
+2, -3,,
}}
|
|
Meanders filling out a 3 × 3 grid (reduced for symmetry)
There are no single closed path meanders for the 3 × 3 grid, since the edges must join the corners, leaving the center unvisited.
Invalid (not a single path) meanders for 3 × 3 grid
| Code
|
Image
|
{{Meander|3|3|
-2, -1, +3,,
+1, 0, +1,,
+2, -1, -3,,
}}
|
|
Meanders filling out a 4 × 4 grid (reduced for symmetry)
There are 4 non-oriented meanders.
Meanders for 4 × 4 grid
| Code
|
Image
|
Code
|
Image
|
{{Meander|4|4|
-2, +3, -2, +3,,
+2, +4, -3, +1,,
-2, -4, +3, +1,,
+2, -3, +2, -3,,
}}
(4 orientations)
|
|
{{Meander|4|4|
-2, +3, -2, +3,,
+2, +4, -4, -3,,
-2, -4, +4, +3,,
+2, -3, +2, -3,,
}}
(1 orientation)
|
|
{{Meander|4|4|
-2, +3, -2, +3,,
+1, +2, -3, +1,,
+1, -2, +3, +1,,
+2, -3, +2, -3,,
}}
(2 orientations)
|
|
{{Meander|4|4|
-2, +3, -2, +3,,
+1, +1, +1, +1,,
+1, +2, -3, +1,,
+2, -1, -1, -3,,
}}
(4 orientations)
|
|
Meanders filling out a 5 × 5 grid (reduced for symmetry)
There are 42 non-oriented meanders.
Meanders for 5 × 5 grid
| Code
|
Image
|
{{Meander|5|5|
-2, +3, -2, -1, +3,,
+2, +4, -3, -2, -3,,
-2, -3, -2, -4, +3,,
+1, -2, +4, -3, +1,,
+2, -3, +2, -1, -3,,
}}
|
...
|
Meanders filling out a 6 × 6 grid (reduced for symmetry)
There are 9050 non-oriented meanders.
Meanders for 6 × 6 grid
| Code
|
Image
|
{{Meander|6|6|
-2, +3, -2, +3, -2, +3,,
+2, +4, -3, +2, -3, +1,,
-2, -3, -2, +3, -2, -3,,
+2, +3, +2, +4, -4, +3,,
-2, -3, -2, +4, -3, +1,,
+2, -1, -3, +2, -1, -3,,
}}
|
...
|
Self-crossing meanders filling out an n × k grid (reduced for symmetry)
(...)
Self-crossing meanders filling out an n × n grid (reduced for symmetry)
(...)
Self-crossing meanders filling out a 4 × 4 grid (reduced for symmetry)
Example of a self-crossing meander filling out a 4 × 4 grid (reduced for symmetry)
| Code
|
Result
|
{{Meander|4|4|
-2, +3, -2, +3,,
+2, -4, +4, -3,,
-2, -5, +5, +3,,
+2, -3, +2, -3,,
}}
|
|
|
| Code
|
Result
|
{{Meander|4|4|
BR, LB, BR, LB,,
TR, UD, DD, LT,,
BR, XH, XV, LB,,
TR, LT, TR, LT,,
}}
|
|
|
| Code
|
Result
|
{{Meander|4|4|
S, W, S, W,,
E, A, B, N,,
S, C, D, W,,
E, N, E, N,,
}}
|
|
|
Sequences
A200000 Number of meanders filling out an
, grid, reduced for symmetry,
.
-
{1, 1, 0, 4, 42, 9050, 6965359, ...}
A200749 Number of meanders filling out an
grid, not reduced for symmetry,
.
-
{1, 1, 0, 11, 320, 71648, 55717584, ...}
A200893 Triangle read by rows: number of meanders filling out an
grid, reduced for symmetry,
.
-
{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
grid, not reduced for symmetry,
.
-
{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
Notes
- ↑ Needs verification (proposition concerning S (n, 3)).
.png){kind=small}
