A005389 Number of Hamiltonian circuits on 2n times 4 rectangle.

1, 6, 37, 236, 1517, 9770, 62953, 405688, 2614457, 16849006, 108584525, 699780452, 4509783909, 29063617746, 187302518353, 1207084188912, 7779138543857, 50133202843990, 323086934794997, 2082156365731164, 13418602439355485, 86477122654688250, 557307869909156153

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• easy

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..200
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• T. G. Schmalz, G. E. Hite and D. J. Klein, Compact self-avoiding circuits on two-dimensional lattices, J. Phys. A 17 (1984), 445-453.
• Index entries for linear recurrences with constant coefficients, signature (8,-10,0,-1).

Crossrefs

Bisection of A006864.

Programs

Magma

I:=[1,6,37,236]; [n le 4 select I[n] else 8*Self(n-1) -10*Self(n-2) -Self(n-4): n in [1..41]]; // G. C. Greubel, Nov 17 2022

Maple

A005389:=-(-1+2*z+z**2)/(1-8*z+10*z**2+z**4); [Conjectured by Simon Plouffe in his 1992 dissertation.]
a:= n -> (Matrix([[0,1,2,-11]]). Matrix(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [8,-10,0,-1][i] else 0 fi)^(n))[1,1]: seq (a(n), n=1..25); # Alois P. Heinz, Aug 05 2008

Mathematica

a[1]=1; a[2]=6; a[3]=37; a[4]=236; a[n_] := a[n] = 8*a[n-1]-10*a[n-2]-a[n-4]; Array[a, 23] (* Jean-François Alcover, Mar 13 2014 *)
CoefficientList[Series[(1 - 2 x - x^2)/(1 - 8 x + 10 x^2 + x^4), {x, 0, 30}], x] (* Vincenzo Librandi, Mar 15 2014 *)

SageMath

def A005389_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-2*x-x^2)/(1-8*x+10*x^2+x^4) ).list()
A005389_list(40) # G. C. Greubel, Nov 17 2022

Formula

G.f.: x*(1-2*x-x^2)/(1-8*x+10*x^2+x^4). - Ralf Stephan, Apr 23 2004