This site is supported by donations to The OEIS Foundation.

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

From OeisWiki
(Redirected from Meanders filling out an n-by-n grid (reduced for symmetry))
Jump to: navigation, search


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


Meanders filling out an
n  × k
grid, reduced for symmetry:
Closed paths that visit every cell of an
n  × 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 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 Meander 1-by-1 (small).png

The
n  × k
grid,
n   ≥   2, 2   ≤   k   ≤   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)
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
Meander LT.png LT (WN) or TL (NW) N −3 −4, −2, −1, +2, +4 −4, −2, +1, +3, +4 −2, +1, +2 −2, −1, +3
Meander BR.png BR (SE) or RB (ES) S −2 −3, +1, +3 −3, −1, +2 −4, −3, −1, +3, +4 −4, −3, +1, +2, +4
Meander LR.png LR (WE) or RL (EW) H −1 −4, −2, −1, +2, +4 −3, −1, +2 −4, −3, −1, +3, +4 −2, −1, +3
Meander BT.png BT (SN) or TB (NS) V +1 −3, +1, +3 −4, −2, +1, +3, +4 −2, +1, +2 −4, −3, +1, +2, +4
Meander TR.png TR (NE) or RT (EN) E +2 −3, +1, +3 −4, −2, +1, +3, +4 −4, −3, −1, +3, +4 −2, −1, +3
Meander LB.png LB (WS) or BL (SW) W +3 −4, −2, −1, +2, +4 −3, −1, +2 −2, +1, +2 −4, −3, +1, +2, +4
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
n  × k
grid, we need to solve
nk  −  4, n   ≥   2, 2   ≤   k   ≤   n,
cells. For each cell, there are up to 8 tiles to choose from, giving
8nk  − 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)

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

Number of meanders filling out an n  × k grid, reduced for symmetry

Number of meanders filling out an
n  × k
grid, reduced for symmetry

n

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

k = 1

2
3
4
5
6
7
8
9
10  

Conjecture concerning S (n, 3)

S (n, 3), 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
S (n, 3) = a (n), n   ≥   3.
)
{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))

S (n, 3) = a (n), n ≥ 3.


Closed form solution:

S (n, 3)  = 
J  (n − 3) + J  (
n − 3
2
)
2
, n odd; S (n, 3)  = 
J  (n − 3) + J  (
n
2
)
2
, n even; n ≥ 3,
where
J  (n) =
2n  −  ( − 1)n
3
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
n
-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
n  −  3
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
k
are counted by the Jacobsthal number
J  (k )
.

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
2 k + 3
(e.g. 1231321,
k = 2
) is left-right symmetrical when the left half matches the reversed right half, e.g. 1[23]1[32]1. There are
2k
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
k
as before but must end in 1 or 3. These words are counted by
J  (k )
. An odd-length word may have left-right symmetry or rotational symmetry but not both.

Even length words:

A word of even length
2 k + 2
(e.g. 123123,
k = 2
)) cannot be left-right symmetrical because the middle two letters would need to be identical. For rotational symmetry the left side is of length
k
as above and must end in 1 or 3, e.g. 1[23][12]3. These words are also counted by
J (k ).
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
n  × 3
meander has
n  −  1
borders of which 2 were ignored, such meanders with top-bottom symmetry removed are counted by
J  (n  −  3)
.

Applying these results we get:

n odd: S (n, s)  = 
1
2
J  (n − 3) +
1
2
J  (
n − 3
2
), n ≥ 3,
n even: S (n, s)  = 
1
2
J  (n − 3) +
1
2
J  (
n − 4
2
) +
1
2
2
n − 4
2
, n ≥ 4.
Simplifying the latter yields
S (n, 3)  = 
J  (n  −  3) + J  (
n  −  3
2
)
2
, n odd; S (n, 3)  = 
J  (n  −  3) + J  (
n
2
)
2
, n even; n   ≥   3,
where
J  (n) =
2n  −  ( − 1)n
3
, completing the proof. 

Meanders filling out an n  × n grid (reduced for symmetry)

Meanders filling out an
n  × n
grid, reduced for symmetry:
Closed paths that visit every cell of an
n  × 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 not considered distinct.
For the
n  × n
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
8n 2 − 4, n   ≥   2,
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,,
}}
Meander 1-by-1 (small).png

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,,
}}
Meander BR.png Meander LB.png
Meander TR.png Meander LT.png

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,,
}}
Meander BR.png Meander LR.png Meander LB.png
Meander BT.png Meander 1-by-1 (small).png Meander BT.png
Meander TR.png Meander LR.png Meander LT.png

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 BR.png Meander LB.png Meander BR.png Meander LB.png
Meander TR.png Meander LB & TR.png Meander LT.png Meander BT.png
Meander BR.png Meander LT & BR.png Meander LB.png Meander BT.png
Meander TR.png Meander LT.png Meander TR.png Meander LT.png
{{Meander|4|4|
-2, +3, -2, +3,,
+2, +4, -4, -3,,
-2, -4, +4, +3,,
+2, -3, +2, -3,, 
}}

(1 orientation)

Meander BR.png Meander LB.png Meander BR.png Meander LB.png
Meander TR.png Meander LB & TR.png Meander LT & BR.png Meander LT.png
Meander BR.png Meander LT & BR.png Meander LB & TR.png Meander LB.png
Meander TR.png Meander LT.png Meander TR.png Meander LT.png
{{Meander|4|4|
-2, +3, -2, +3,,
+1, +2, -3, +1,,
+1, -2, +3, +1,,
+2, -3, +2, -3,,
}}

(2 orientations)

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

(4 orientations)

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

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,,
}}
Meander BR.png Meander LB.png Meander BR.png Meander LR.png Meander LB.png
Meander TR.png Meander LB & TR.png Meander LT.png Meander BR.png Meander LT.png
Meander BR.png Meander LT.png Meander BR.png Meander LT & BR.png Meander LB.png
Meander BT.png Meander BR.png Meander LB & TR.png Meander LT.png Meander BT.png
Meander TR.png Meander LT.png Meander TR.png Meander LR.png Meander LT.png

...

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,,
}}
Meander BR.png Meander LB.png Meander BR.png Meander LB.png Meander BR.png Meander LB.png
Meander TR.png Meander LB & TR.png Meander LT.png Meander TR.png Meander LT.png Meander BT.png
Meander BR.png Meander LT.png Meander BR.png Meander LB.png Meander BR.png Meander LT.png
Meander TR.png Meander LB.png Meander TR.png Meander LB & TR.png Meander LT & BR.png Meander LB.png
Meander BR.png Meander LT.png Meander BR.png Meander LB & TR.png Meander LT.png Meander BT.png
Meander TR.png Meander LR.png Meander LT.png Meander TR.png Meander LR.png Meander LT.png

...

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,,
}}
Meander BR.png Meander LB.png Meander BR.png Meander LB.png
Meander TR.png Meander LT & BR.png Meander LB & TR.png Meander LT.png
Meander BR.png Meander XH.png Meander XV.png Meander LB.png
Meander TR.png Meander LT.png Meander TR.png Meander LT.png
Code Result
  
{{Meander|4|4|
BR, LB, BR, LB,,
TR, UD, DD, LT,,
BR, XH, XV, LB,,
TR, LT, TR, LT,,
}}
Meander BR.png Meander LB.png Meander BR.png Meander LB.png
Meander TR.png Meander LT & BR.png Meander LB & TR.png Meander LT.png
Meander BR.png Meander XH.png Meander XV.png Meander LB.png
Meander TR.png Meander LT.png Meander TR.png Meander LT.png
Code Result
 
{{Meander|4|4|
S, W, S, W,,
E, A, B, N,,
S, C, D, W,,
E, N, E, N,,
}}
Meander BR.png Meander LB.png Meander BR.png Meander LB.png
Meander TR.png Meander LT & BR.png Meander LB & TR.png Meander LT.png
Meander BR.png Meander XH.png Meander XV.png Meander LB.png
Meander TR.png Meander LT.png Meander TR.png Meander LT.png

Sequences

A200000 Number of meanders filling out an
n  × n
, grid, reduced for symmetry,
n   ≥   1
.
{1, 1, 0, 4, 42, 9050, 6965359, ...}
A200749 Number of meanders filling out an
n  × 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  × 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  × 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





Notes

  1. Needs verification (proposition concerning S (n, 3)).