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

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,1

Comments

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.

Links

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

Formula

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

Mathematica

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

Prog

(PARI) 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

Crossrefs

Cf. A069241, A124353, A137725.

Sequence in context: A010584 A131659 A380145 * A121098 A121094 A029595

Adjacent sequences: A137723 A137724 A137725 * A137727 A137728 A137729

Keyword

nonn,easy

Author

Max Alekseyev, Feb 08 2008

Extensions

Formulae corrected by Max Alekseyev, Nov 03 2010

Status

approved