A306447 Number of (undirected) Hamiltonian cycles in the n-antiprism graph.

3, 9, 16, 29, 56, 110, 225, 469, 991, 2110, 4511, 9666, 20736, 44511, 95575, 205253, 440828, 946817, 2033628, 4367986, 9381949, 20151433, 43283195, 92967882, 199685571, 428904390, 921243268, 1978737467, 4250128235, 9128846273, 19607840040, 42115660645

Offset: 1

Author

Eric W. Weisstein, May 04 2019

Keywords

• nonn
• easy

Comments

Extended to a(1)-a(2) using the formula/recurrence.

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• 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).

Programs

Mathematica

LinearRecurrence[{3,-1,-2,0,1},{3,9,16,29,56},40] (* Harvey P. Dale, Aug 06 2020 *)

PARI

Vec(x*(3 - 8*x^2 - 4*x^3 + 3*x^4) / ((1 - x)^2*(1 - x - 2*x^2 - x^3)) + O(x^35)) \\ Colin Barker, Jul 12 2020

Formula

a(n) = A124353(n)/2.

From Colin Barker, Jul 12 2020: (Start)

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

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

(End)