This site is supported by donations to The OEIS Foundation.

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

(Redirected from Number of meanders filling out an n-by-n grid (reduced for symmetry))

Meanders filling out an ${\displaystyle \scriptstyle n\,}$-by-${\displaystyle \scriptstyle k\,}$ grid, reduced for symmetry:

Closed paths that visit every cell of an ${\displaystyle \scriptstyle n\,}$-by-${\displaystyle \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 not considered distinct.

## Meanders filling out an n-by-k grid, 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

The ${\displaystyle \scriptstyle n\,}$-by-${\displaystyle \scriptstyle k\,}$ grid, ${\displaystyle \scriptstyle n\,\geq \,2,\,2\,\leq \,\,k\,\leq \,n,\,}$ has meanders which are built from the meander sections with nonzero IDs.

Meander sections
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 ${\displaystyle \scriptstyle n\,}$-by-${\displaystyle \scriptstyle k\,}$ grid, we need to solve ${\displaystyle \scriptstyle nk-4,\,n\,\geq \,2,\,2\,\leq \,k\,\leq \,n,\,}$ cells. For each cell, there are up to 8 tiles to choose from, giving ${\displaystyle \scriptstyle 8^{nk-4},\,n\,\geq \,2,\,2\,\leq \,k\,\leq \,n,\,}$ possible (valid or invalid) configurations.

### Meanders filling out a 4-by-3 grid, reduced for symmetry

Meanders for 4-by-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-by-k grid, reduced for symmetry

 ${\displaystyle \scriptstyle 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 ? ? ? ? ? ? ? ? 11 0 1 ? ? ? ? ? ? ? ? ? 12 0 1 ? ? ? ? ? ? ? ? ? ? 13 0 1 ? ? ? ? ? ? ? ? ? ? ? ${\displaystyle \scriptstyle k\,}$ = 1 2 3 4 5 6 7 8 9 10 11 12 13

### Conjecture concerning S(n, 3)

${\displaystyle \scriptstyle S(n,\,3),\,n\,\geq \,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:

${\displaystyle \scriptstyle S(n,3)={\frac {J(n-3)+J({\frac {n-3}{2}})}{2}},\,n{\rm {~odd}};\ S(n,3)={\frac {J(n-3)+J({\frac {n}{2}})}{2}},\,n{\rm {~even}};\,n\,\geq \,3,\,}$

where ${\displaystyle \scriptstyle J(n)={\frac {2^{n}-(-1)^{n}}{3}}}$ is the Jacobsthal number A001045.

Proof. 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 ${\displaystyle \scriptstyle k}$ are counted by the Jacobsthal number ${\displaystyle \scriptstyle 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 2k+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 ${\displaystyle \scriptstyle 2^{k}}$ 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 ${\displaystyle \scriptstyle 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 2k+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 ${\displaystyle \scriptstyle 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 nx3 meander has n-1 borders of which 2 were ignored, such meanders with top-bottom symmetry removed are counted by ${\displaystyle \scriptstyle J(n-3)}$.

Applying these results we get:

n odd: ${\displaystyle \scriptstyle S(n,s)={\frac {1}{2}}*J(n-3)\,+\,{\frac {1}{2}}*J({\frac {n-3}{2}}),\,n>=3;}$
n even: ${\displaystyle \scriptstyle S(n,s)={\frac {1}{2}}*J(n-3)\,+\,{\frac {1}{2}}*J({\frac {n-4}{2}})\,+\,{\frac {1}{2}}*2^{\frac {n-4}{2}},\,n>=4;}$

Simplifying the latter yields ${\displaystyle \scriptstyle S(n,3)={\frac {J(n-3)+J({\frac {n-3}{2}})}{2}},\,n{\rm {~odd}};\ S(n,3)={\frac {J(n-3)+J({\frac {n}{2}})}{2}},\,n{\rm {~even}};\,n\,\geq \,3,}$ where ${\displaystyle \scriptstyle J(n)={\frac {2^{n}-(-1)^{n}}{3}}}$, completing the proof.

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

Meanders filling out an n-by-n grid, 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 not considered distinct.

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

### Meanders filling out a 1-by-1 grid (reduced for symmetry)

The 1-by-1 grid has the distinct and unique meander

Meander for 1-by-1 grid
Code Image
{{Meander|1|1|
0,,
}}


### Meanders filling out a 2-by-2 grid (reduced for symmetry)

Trivial case.

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


### Meanders filling out a 3-by-3 grid (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.

Invalid (not a single path) meanders for 3-by-3 grid
Code Image
{{Meander|3|3|
-2, -1, +3,,
+1,  0, +1,,
+2, -1, -3,,
}}


### Meanders filling out a 4-by-4 grid (reduced for symmetry)

There are 4 non-oriented meanders.

Meanders for 4-by-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-by-5 grid (reduced for symmetry)

There are 42 non-oriented meanders.

Meanders for 5-by-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-by-6 grid (reduced for symmetry)

There are 9050 non-oriented meanders.

Meanders for 6-by-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-by-k grid (reduced for symmetry)

(...)

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

(...)

#### Self-crossing meanders filling out a 4-by-4 grid (reduced for symmetry)

Example of a self-crossing meander filling out a 4-by-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 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, ...}