A201145 Triangle read by rows: number of meanders filling out an n X k grid, unreduced 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, 27876028, 2372510658, 213773992667, 0, 1, 42, 17156, 2671052, 549405072, 98927211122, 18677872557034, 3437213982024260

Offset

1,9

Comments

This sequence counts the closed paths that visit every cell of an n X k rectangular lattice at least once, never cross any edge between adjacent squares more than once, and do not self-intersect. Paths related by rotation and/or reflection of the square lattice are counted as separate and equally valid; in other words, these are oriented meanders.

From Jon Wild, Nov 29 2011: (Start)

The values of T(n,4), n >= 4, form a series that increases by a multiplicative factor that gets closer and closer (alternating approaches from above and below) to a value of 4.4547 +/- 0.0007: 11, 42, 199, 858, 3881, 17156, 76707, 341060, 1520623, 6770556, 30165937, 134358958.

The values of T(n,5), n >= 5, form a series that increases by a multiplicative factor that gets closer and closer (alternating approaches from above and below) to a value of 9.421 +/- 0.014: 320, 3278, 29904, 285124, 2671052, 25200508, 237074534. (End)

It appears that T(n>=4,4) satisfies a recurrence with minimal polynomial x^6 - 7*x^5 + 7*x^4 + 10*x^3 - 9*x^2 - 3*x + 1; if so, then the ratio that T(n+1,4)/T(n,4) approaches as n goes to infinity is (1/12)*sqrt(24*sqrt(115)*cos(-(1/3)*Pi + (1/3)*arctan((3/1016)*sqrt(3)*sqrt(18097))) + 273) + (1/2)*sqrt(-(2/3)*sqrt(115)*cos(-(1/3)*Pi + (1/3)*arctan((3/1016)*sqrt(3)*sqrt(18097))) + (201/2)/sqrt(24*sqrt(115)*cos(-(1/3)*Pi + (1/3)*arctan((3/1016)*sqrt(3)*sqrt(18097))) + 273) + 91/6) + 3/4. - D. S. McNeil, Nov 30 2011

Links

Alex Chernov, Rows 1..15 of triangle, flattened

Alex Chernov, Some terms for rows above 15

Jon Wild, Illustration for T(6,4) = 199

Formula

T(n,3) is given by A078008, the expansion of (1-x)/(1-x-2*x^2). Benoit Jubin noticed (Nov 22 2011) that T(n,3) is also given by 2*(b(n-2) + b(n-3) + b(n-4) + ... +b(2)).

Example

The 199 meanders on a 6 X 4 rectangle are shown in the supporting png image.

Crossrefs

Cf. A200893, where the meanders on an n X k rectangle are unoriented, i.e., the sequence is reduced for symmetry.

Cf. A200749, which counts oriented meanders on an n X n square grid.

Cf. A200000, which counts unoriented meanders on an n X n square grid.

Sequence in context: A288848 A374945 A202952 * A053994 A348942 A057213

Adjacent sequences: A201142 A201143 A201144 * A201146 A201147 A201148

Keyword

nonn,tabl

Author

Jon Wild, Nov 27 2011

Extensions

More terms from Alex Chernov, Jan 01 2012

Status

approved