A124353 Number of (directed) Hamiltonian circuits on the n-antiprism graph.

6, 18, 32, 58, 112, 220, 450, 938, 1982, 4220, 9022, 19332, 41472, 89022, 191150, 410506, 881656, 1893634, 4067256, 8735972, 18763898, 40302866, 86566390, 185935764, 399371142, 857808780, 1842486536, 3957474934, 8500256470, 18257692546, 39215680080, 84231321290, 180920373632, 388598695916

Offset: 1

Author

Eric W. Weisstein, Oct 27 2006

Keywords

• nonn

Comments

The antiprism graph is defined for n>=3; extended to n=1 using the closed form.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Max A. Alekseyev, Gérard P. Michon, Making Walks Count: From Silent Circles to Hamiltonian Cycles, arXiv:1602.01396 [math.CO], 2016-2017.
• Mordecai J. Golin and Yiu Cho Leung, Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees, Hamiltonian Cycles and other Parameters, Technical report HKUST-TCSC-2004-02. See also.
• Eric Weisstein's World of Mathematics, Antiprism Graph
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-2,0,1).

Crossrefs

Cf. A124352.

Programs

Magma

I:=[6,18,32,58,112]; [n le 5 select I[n] else 3*Self(n-1) - Self(n-2) - 2*Self(n-3) + Self(n-5): n in [1..35]]; // Vincenzo Librandi, Feb 04 2016

Mathematica

Table[2 (2 n + RootSum[-1 - 2 # - #^2 + #^3 &, #^n &]), {n, 20}]
LinearRecurrence[{3, -1, -2, 0, 1}, {6, 18, 32, 58, 112}, 50] (* Vincenzo Librandi, Feb 04 2016 *)
Join[{6, 18}, Rest[Rest[Rest[CoefficientList[Series[-18*x^2 - 6*x - 6 + (4*x^2 + 4*x - 6)/(x^3 + 2*x^2 + x - 1) + 4/(x - 1)^2 + 4/(x - 1), {x, 0, 50}], x]]]]] (* G. C. Greubel, Apr 27 2017 *)

PARI

x='x+O('x^50); concat([6,18], Vec(-18*x^2-6*x-6+(4*x^2+4*x-6)/(x^3+2*x^2+x-1)+4/(x-1)^2+4/(x-1))) \\ G. C. Greubel, Apr 27 2017

Formula

a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) + a(n-5).

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

O.g.f.: -18*x^2-6*x-6+(4*x^2+4*x-6)/(x^3+2*x^2+x-1)+4/(x-1)^2+4/(x-1) . - R. J. Mathar, Feb 10 2008

a(n) = 2*(n + 3*A000930(2*n) - 2*A000930(2*n-1)) = A137725(2*n) = 2*A137726(2*n).

Extensions

Formulas and further terms from Max Alekseyev, Feb 08 2008

Typo in formula corrected by Max Alekseyev, Nov 03 2010