|
|
A326932
|
|
The number of permutations of GF(2^n) that are of the form x -> g(x), where g is a polynomial with coefficients in GF(2).
|
|
1
|
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Let q be a prime power. Each function from GF(q) to itself can be uniquely represented by a polynomial in GF(q)[X] of degree at most q-1. A polynomial g in GF(q)[X] is said to be a permutation polynomial, if the function x -> g(x) is a permutation of GF(q). a(n) gives the number of permutation polynomials in GF(2^n)[X] of degree at most 2^n-1 whose coefficients are all in the prime field GF(2).
Let GF(p) be a subfield of GF(q). The permutations of GF(q) of the form x -> g(x), where g is a polynomial with coefficients in GF(p), form a subgroup of the permutations of GF(q) (see Carlitz and Hayes, 1972).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Product_{d|n} p(d)!*d^p(d), where p(d) is the number of irreducible polynomials over GF(2) of degree d (i.e., sequence A001037). Proven more generally in Carlitz and Hayes, 1972.
|
|
MATHEMATICA
|
Block[{p}, p[n_] := p[n] = DivisorSum[n, (MoebiusMu[n/#]*2^#/n) &]; Array[Times @@ Map[p[#]!*#^p[#] &, Divisors@ #] &, 11]] (* Michael De Vlieger, Jul 08 2020 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|