login
A098691
Array T(q,n) by antidiagonals: number of self-reciprocal polynomials of degree 2*n over GF(q) (for q >= 2 and n >= 1).
3
1, 1, 1, 2, 2, 1, 2, 4, 4, 2, 3, 6, 10, 10, 3, 3, 9, 20, 32, 24, 5, 4, 12, 35, 78, 102, 60, 9, 4, 16, 56, 162, 312, 340, 156, 16, 5, 20, 84, 300, 777, 1300, 1170, 410, 28, 5, 25, 120, 512, 1680, 3885, 5580, 4096, 1092, 51, 6, 30, 165, 820, 3276, 9800, 19995, 24414
OFFSET
2,4
COMMENTS
Also, number of self-complementary primitive necklaces of length n in q colors.
LINKS
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
Rows are A000048 (q=2), A006575 (q=3).
Columns 1-4 are A004526, A002620, A000292, 2*A011863.
Main diagonal is in A098692.
Sequence in context: A261359 A217680 A144218 * A324251 A035364 A261734
KEYWORD
nonn,tabl
AUTHOR
Ralf Stephan, Sep 21 2004
STATUS
approved