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
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).
Programs
-
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 *) -
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
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
Extensions
Formulae corrected by Max Alekseyev, Nov 03 2010
Comments