A200893 -id:A200893 - cp's OEIS frontend

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

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

Offset: 3

Thomas A. Gittings, Dec 11 2003

Arises from a conjecture about sequence of rational links with n crossings.
Conjecture derived from: s(n) = k(n) + l(n): definition of sum of rational knots (k) and links (l) s(n) = 6s(n-2) -8s(n-4): see A005418 (Jablan's observation) d(n) = d(n-2) + 2d(n-4): see A001045 (modified Jacobsthal sequence) l(n) = k(n-1) + d(n): conjecture.
a(n) is the number of rational (2-component) links. - Slavik Jablan, Dec 26 2003
Also yields the number of meanders, reduced by symmetry, on an n X 3 rectangle (see A200893). - Jon Wild, Nov 25 2011

Reinhard Zumkeller, Table of n, a(n) for n = 3..1000
C. Ernst and D. W. Sumners, The Growth of the Number of Prime Knots, Math. Proc. Cambridge Philos. Soc. 102, 303-315, 1987 (see Theorem 5, formulas for TL_n).
Index entries for linear recurrences with constant coefficients, signature (1,3,-1,0,-2,-4).

This is the difference between A005418 and A018240.
Cf. A018240 = sequence of rational knots, A005418 = number of rational knots and links, A001045 = Jacobsthal sequence, A329908, A336398.
Cf. A200893, and see the third column of the triangle read by rows there.

a090597 n = a090597_list !! (n-3)
a090597_list = [0,1,1,3,3,8,12] ++ zipWith (-)
   (drop 4 $ zipWith (-) (map (* 5) zs) (drop 2 a090597_list))
   (zipWith (+) (drop 2 $ map (* 2) zs) (map (* 8) zs))
   where zs = zipWith (+) a090597_list $ tail a090597_list
-- Reinhard Zumkeller, Nov 24 2011

f[x_] := (x-x^3-2x^4-3x^5) / (1-x-3x^2+x^3+2x^5+4x^6); CoefficientList[ Series[ f[x], {x, 0, 29}], x] (* Jean-François Alcover, Dec 06 2011 *)
J[n_] := (2^n - (-1)^n)/3; Table[(J[n - 3] + J[(n - If[OddQ[n], 3, 0])/2])/2 , {n, 3, 31}] (* David Scambler, Dec 13 2011 *)
LinearRecurrence[{1,3,-1,0,-2,-4},{0,1,1,3,3,8},30] (* Harvey P. Dale, Nov 12 2013 *)

a(n) = +a(n-1) +3*a(n-2) -a(n-3) -2*a(n-5) -4*a(n-6). - R. J. Mathar, Nov 23 2011
G.f.: -x^4*(-1+x^2+3*x^4+2*x^3) / ( (2*x-1)*(1+x)*(2*x^2-1)*(1+x^2) ). - R. J. Mathar, Nov 23 2011
a(n) = (J(n-3) + J((n-3)/2))/2 if n is odd; (J(n-3) + J(n/2))/2 if n is even, where J is the Jacobsthal number A001045. - David Scambler, Dec 12 2011

A200000 Number of meanders filling out an n X n grid, reduced for symmetry.

Original entry on oeis.org

1, 1, 0, 4, 42, 9050, 6965359, 26721852461, 429651752290375, 31194475941824888769, 9828395457980805457337560, 13684686862375136981850903785368, 83297108604256429529069019958551956425, 2226741508593975401942934273354241209226704830, 260577257822688861848154672171293101310412373160498171, 133631198381015786582155688877301469836628906260462969996612568, 299985729493560746632648983353916422875677601725131683097521792924081609

Offset: 1

Jon Wild, Nov 20 2011

The sequence counts the distinct closed paths that visit every cell of an n X 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.
Are a(1) and a(2) the only two terms equal to 1? And is a(3) the only term equal to 0? - Daniel Forgues, Nov 24 2011
The answer is yes: There are several patterns that can straightforwardly be generalized to any grid of any size n>3, e.g., #13 and #6347 of the graphics for a(6) (resp. #24 or #28 of a(5) for odd n). - M. F. Hasler, Nov 24 2011

			a(1) counts the paths that visit the single cell of the 1 X 1 lattice: there is one, the "fat dot".
The 4 solutions for n=4, 42 solutions for n=5 and 9050 solutions for n=6 are illustrated in the supporting .png files.

Dale Gerdemann, Video illustration for a(5) = 42
OEIS Wiki, Number of meanders filling out an n-by-n grid (reduced for symmetry)
Jon Wild, Illustration for a(4) = 4
Jon Wild, Illustration for a(5) = 42
Jon Wild, Illustration for a(6) = 9050 [Warning: this is a large file!]
Zhao Hui Du, C++ source code for A200000 and A200749

Cf. A200749 (version not reduced for symmetry).
Cf. A200893 (meanders on n X k rectangles instead of squares, reduced for symmetry).
Cf. A201145 (meanders on n X k rectangles, not reduced for symmetry).

a(8) and a(10) from Alex Chernov, May 28 2012
a(9) from Alex Chernov, added by Max Alekseyev, Jul 21 2013
a(11) to a(17) from Zhao Hui Du, Apr 03 2014

A201145 Triangle read by rows: number of meanders filling out an n X k grid, unreduced for symmetry.

Original entry on oeis.org

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

Jon Wild, Nov 27 2011

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

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

Alex Chernov, Rows 1..15 of triangle, flattened
Alex Chernov, Some terms for rows above 15
Jon Wild, Illustration for T(6,4) = 199

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.

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

More terms from Alex Chernov, Jan 01 2012

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A200000 Number of meanders filling out an n X n grid, reduced for symmetry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A201145 Triangle read by rows: number of meanders filling out an n X k grid, unreduced for symmetry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions