|
Search: id:A137725
|
|
|
| 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). |
|
+0
3
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
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
|
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.
Eric Weisstein's World of Mathematics, Circulant Graph
Eric Weisstein's World of Mathematics, Hamiltonian Circuit.
|
|
FORMULA
|
For even n>=4, a(n) = 2*(n + 3*A000930(n) - 2*A000930(n)); for odd n>=3, a(n) = 2*(n + 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 (mathar(AT)strw.leidenuniv.nl), Feb 10 2008
|
|
CROSSREFS
|
Cf. A124353, A137726
Sequence in context: A056450 A141125 A129884 this_sequence A082649 A053441 A065732
Adjacent sequences: A137722 A137723 A137724 this_sequence A137726 A137727 A137728
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Max Alekseyev (maxal(AT)cs.ucsd.edu), Feb 8, 2008
|
|
|
Search completed in 0.002 seconds
|
