A137725 -id:A137725 - cp's OEIS frontend

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

Eric W. Weisstein, Oct 27 2006

nonn

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

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).

Cf. A124352.

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

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

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

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).

Formulas and further terms from Max Alekseyev, Feb 08 2008

Typo in formula corrected by Max Alekseyev, Nov 03 2010

A137726 Number of sequences of length n with elements {-2,-1,+1,+2}, counted up to simultaneous reversal and negation, such that the sum of elements of the whole sequence but of no proper subsequence equals 0 modulo n. For n>=4, the number of Hamiltonian (undirected) cycles on the circulant graph C_n(1,2).

Original entry on oeis.org

2, 2, 8, 9, 12, 16, 23, 29, 41, 56, 79, 110, 158, 225, 325, 469, 682, 991, 1446, 2110, 3085, 4511, 6603, 9666, 14157, 20736, 30380, 44511, 65223, 95575, 140060, 205253, 300800, 440828, 646051, 946817, 1387613, 2033628, 2980411, 4367986, 6401578, 9381949, 13749897, 20151433, 29533342

Offset: 1

Max Alekseyev, Feb 08 2008

For n>1, the number of circular permutations (counted up to rotations and reversals) of {0, 1,...,n-1} such that the distance between every two adjacent elements is -2,-1,1,or 2 modulo n.

G. C. Greubel, Table of n, a(n) for n = 1..1000
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.
Spoj, Problem 7709: Jumping Zippy
Eric Weisstein's World of Mathematics, Circulant Graph
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,0,-1,1).

Cf. A069241, A124353, A137725.

Rest[CoefficientList[Series[-x*(x^7 + 2*x^5 - 4*x^4 - 5*x^3 + 4*x^2 - 2*x + 2)/((x - 1)^2*(x + 1)*(x^3 + x - 1)), {x, 0, 50}], x]] (* G. C. Greubel, Apr 27 2017 *)

x='x+O('x^50); Vec(-x*(x^7 + 2*x^5 - 4*x^4 - 5*x^3 + 4*x^2 - 2*x + 2)/((x - 1)^2*(x + 1)*(x^3 + x - 1))) \\ G. C. Greubel, Apr 27 2017

For even n>=4, a(n) = n + 3*A000930(n) - 2*A000930(n-1); for odd n>=3, a(n) = n + 1 + 3*A000930(n) - 2*A000930(n-1).
For n>8, a(n) = 2*a(n-1) - a(n-3) - a(n-5) + a(n-6) or a(n) = a(n-1) + a(n-2) - a(n-5) - 2.
a(n) = A137725(n) / 2.
G.f.: -x*(x^7+2*x^5-4*x^4-5*x^3+4*x^2-2*x+2)/((x-1)^2*(x+1)*(x^3+x-1)). - Colin Barker, Aug 22 2012

Formulae corrected by Max Alekseyev, Nov 03 2010

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions