A014523 - OEIS

%I #38 Jul 18 2024 13:57:35

%S 1,4,20,111,624,3505,19676,110444,619935,3479776,19532449,109638260,

%T 615414276,3454402959,19390027600,108838828241,610926955724,

%U 3429215026140,19248644351551,108045225087424,606472354675265,3404210752374756,19108292005806324

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

%H Harvey P. Dale, <a href="/A014523/b014523.txt">Table of n, a(n) for n = 0..1000</a>

%H Belgacem Bouras, <a href="http://www.emis.de/journals/JIS/VOL16/Bouras/bouras4.html">A New Characterization of Catalan Numbers Related to Hankel Transforms and Fibonacci Numbers</a>, Journal of Integer Sequences, 16 (2013), #13.3.3.

%H Karen L. Collins, Lucia B. Krompart, <a href="http://dx.doi.org/10.1016/0012-365X(95)00330-Y">The number of Hamiltonian paths in a rectangular grid</a>, Discrete Mathematics, Volume 169, Issues 1-3, 15 May 1997, Pages 29-38.

%H Michael Dougherty, Christopher French, Benjamin Saderholm, and Wenyang Qian, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/French/french2.html">Hankel Transforms of Linear Combinations of Catalan Numbers</a>, Journal of Integer Sequences, Vol. 14 (2011), Article 11.5.1.

%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>

%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-9,7,-1).

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

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

%t 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 *)

%t LinearRecurrence[{7,-9,7,-1},{1,4,20,111},30] (* _Harvey P. Dale_, Jul 18 2024 *)

%o (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 */

%o (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

%Y Cf. A014584.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, Dec 11 1999

%E Sequence name clarified by _Andrew Howroyd_, Dec 20 2015

%E a(21)-a(22) from _Vincenzo Librandi_, Dec 21 2015