OFFSET
2,4
COMMENTS
Also, number of self-complementary primitive necklaces of length n in q colors.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 2..1276
H. Meyn and W. Götz, Self-reciprocal polynomials over finite fields, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
R. L. Miller, Necklaces, symmetries and self-reciprocal polynomials, Discr. Math. 22 (1978), 25-33.
FORMULA
T(q, n) = (q^n-1)/(2*n) for q odd and n=2^s; otherwise Sum_{d|n, d odd} mu(d)*q^(n/d) / (2*n).
T(q, n) = Sum_{d|n, d odd} mu(d) * (q^(n/d) - (q mod 2)) / (2*n). - Andrew Howroyd, Aug 21 2019
EXAMPLE
[q=2]: 1, 1, 1, 2, 3, 5, 9, 16, ...
[q=3]: 1, 2, 4, 10, 24, 60, 156, 410, ...
[q=4]: 2, 4, 10, 32, 102, 340, 1170, 4096, ...
[q=5]: 2, 6, 20, 78, 312, 1300, 5580, 24414, ...
[q=6]: 3, 9, 35, 162, 777, 3885, 19995, 104976, ...
[q=7]: 3, 12, 56, 300, 1680, 9800, 58824, 360300, ...
...
PROG
(PARI) T(q, n) = sumdiv(n, d, if(d%2, moebius(d) * (q^(n/d)-q%2), 0)) / (2*n); \\ Andrew Howroyd, Aug 21 2019
(PARI) T(q, n) = {if(q%2 && n == 2^logint(n, 2), q^n-1, sumdiv(n, d, if(d%2, moebius(d)*q^(n/d)))) / (2*n)} \\ Andrew Howroyd, Aug 22 2019
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Ralf Stephan, Sep 21 2004
STATUS
approved