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
Links
- Harvey P. Dale, Table of n, a(n) for n = 0..1000
- 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).
Crossrefs
Cf. A014584.
Programs
-
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
-
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 *) LinearRecurrence[{7,-9,7,-1},{1,4,20,111},30] (* Harvey P. Dale, Jul 18 2024 *) -
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 */
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).
Extensions
Sequence name clarified by Andrew Howroyd, Dec 20 2015
a(21)-a(22) from Vincenzo Librandi, Dec 21 2015