A014524 Number of Hamiltonian paths from NW to SW corners in a grid with 2n rows and 4 columns.

0, 1, 8, 47, 264, 1480, 8305, 46616, 261663, 1468752, 8244304, 46276385, 259755560, 1458042831, 8184190168, 45938958232, 257861540369, 1447411446840, 8124514782015, 45603992276896, 255981331487648

Offset

0,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

K. L. Collins and L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29-38.

Index entries for sequences related to graphs, Hamiltonian

Index entries for linear recurrences with constant coefficients, signature (7,-9,7,-1).

Formula

From Colin Barker, May 20 2013: (Start)

a(n) = 7*a(n-1)-9*a(n-2)+7*a(n-3)-a(n-4).

G.f.: x*(x+1)/(x^4-7*x^3+9*x^2-7*x+1). (End)

Example

Illustration of a(1)=1:
   .__.__.__.
   .__.__.__|
Illustration of a few of the 8 solutions to a(2):
   .__.__.__.    .  .__.__.    .  .__.__.    .__.__.__.
   .__.__.  |    |  |  .__|    |__|  .__|    .__.__.__|
   |__   |  |    |__|  |__.    .__.  |__.    |__.__.__.
   .__|  |__|    .__.__.__|    |  |__.__|    .__.__.__|

Mathematica

CoefficientList[Series[x (x + 1)/(x^4 - 7 x^3 + 9 x^2 - 7 x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Oct 15 2013 *)

Crossrefs

Even bisection of column 4 of A271592.

Cf. A000532, A181688, A014523, A014585, A003695, A006864.

Sequence in context: A051140 A296631 A255720 * A098891 A054488 A034349

Adjacent sequences: A014521 A014522 A014523 * A014525 A014526 A014527

Keyword

nonn,easy

Author

N. J. A. Sloane.

Extensions

Name clarified by Andrew Howroyd, Apr 10 2016

Status

approved