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

Author

Jon Wild, Nov 27 2011

Keywords

• nonn
• tabl

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

Examples

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

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

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.

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)).

Extensions

More terms from Alex Chernov, Jan 01 2012