A014523 Number of Hamiltonian paths in a 4 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

1, 4, 20, 111, 624, 3505, 19676, 110444, 619935, 3479776, 19532449, 109638260, 615414276, 3454402959, 19390027600, 108838828241, 610926955724, 3429215026140, 19248644351551, 108045225087424, 606472354675265, 3404210752374756, 19108292005806324

Offset

0,2

Links

Table of n, a(n) for n=0..22.

Belgacem Bouras, A New Characterization of Catalan Numbers Related to Hankel Transforms and Fibonacci Numbers, Journal of Integer Sequences, 16 (2013), #13.3.3.

Karen L. Collins, Lucia B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Mathematics, Volume 169, Issues 1-3, 15 May 1997, Pages 29-38.

Michael Dougherty, Christopher French, Benjamin Saderholm, and Wenyang Qian, Hankel Transforms of Linear Combinations of Catalan Numbers, Journal of Integer Sequences, Vol. 14 (2011), Article 11.5.1.

Index entries for two-way infinite sequences

Index entries for sequences related to graphs, Hamiltonian

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

Formula

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

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

Mathematica

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

Prog

(PARI) {a(n)= if(n<-1, -a(-2-n), polcoeff( (1-3*x+x^2)/ (1-7*x+9*x^2-7*x^3+x^4) +x*O(x^n), n))} /* Michael Somos, Jun 14 2003 */
(Magma) I:=[1, 4, 20, 111]; [n le 4 select I[n] else 7*Self(n-1)- 9*Self(n-2)+7*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Dec 21 2015

Crossrefs

Cf. A014584.

Sequence in context: A263854 A026156 A025183 * A153299 A239643 A081335

Adjacent sequences: A014520 A014521 A014522 * A014524 A014525 A014526

Keyword

nonn,easy

Author

N. J. A. Sloane, Dec 11 1999

Extensions

Sequence name clarified by Andrew Howroyd, Dec 20 2015

a(21)-a(22) from Vincenzo Librandi, Dec 21 2015

Status

approved