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).

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

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

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

Adjacent sequences: A098688 A098689 A098690 * A098692 A098693 A098694

Keyword

nonn,tabl

Author

Ralf Stephan, Sep 21 2004

Status

approved