A137725 Number of sequences of length n with elements {-2,-1,+1,+2}, 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 (directed) circuits on the circulant graph C_n(1,2).

4, 4, 16, 18, 24, 32, 46, 58, 82, 112, 158, 220, 316, 450, 650, 938, 1364, 1982, 2892, 4220, 6170, 9022, 13206, 19332, 28314, 41472, 60760, 89022, 130446, 191150, 280120, 410506, 601600, 881656, 1292102, 1893634, 2775226, 4067256, 5960822, 8735972, 12803156, 18763898, 27499794, 40302866, 59066684

Offset: 1

Author

Max Alekseyev, Feb 08 2008

Keywords

• nonn

Comments

Number of 1-D walks with jumps to next-nearest neighbors with n steps, starting at 0 and ending at -2n, -n, 0, n, or 2n, such that every point is visited at most once and every pair of points at the distance n contains at least one unvisited point (not counting the ending visit). Cf. A092765.

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

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. See also
• Eric Weisstein's World of Mathematics, Circulant Graph
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1,0,-1,1).

Crossrefs

Cf. A124353, A137726.

Programs

Mathematica

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

PARI

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

Formula

For even n>=4, a(n) = 2*(n + 3*A000930(n) - 2*A000930(n-1)); for odd n>=3, a(n) = 2*(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) - 4.

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

Extensions

Typo in formulas corrected by Max Alekseyev, Nov 03 2010