OFFSET
1,2
COMMENTS
From Olivier Gérard, Aug 01 2016: (Start)
Equivalent to the definition: number of classes of endofunctions of [n] under rotation and translation mod n.
Classes can be of size between n and n^2 depending on divisibility properties of n.
n n 2n 3n ... n^2
--------------------------
1 1
2 2
3 3 2
4 4 2 14
5 5 0 124
6 6 6 22 1282
7 7 0 16806
For prime n, the only possible class sizes are n and n^2, the classes of size n are the n arithmetical progression modulo n so #(c-n)=n, #(c-n^2)=(n^n - n*n)/n^2 = n^(n-2)-1 and a(n) = n^(n-2)+n-1.
(End)
LINKS
Stefano Spezia, Table of n, a(n) for n = 1..350
Darij Grinberg and Peter Mao, Necklaces over a group with identity product, arXiv:2405.08937 [math.CO], 2024. See p. 22.
FORMULA
a(n) = (1/n^2)*Sum_{d|n} d*phi(d)*n^(n/d). - Vladeta Jovovic, Aug 14 2007, Aug 24 2007
EXAMPLE
The 5 necklaces for n=3 are: 000, 001, 002, 012 and 021.
MATHEMATICA
tor8={}; ru8=Thread[ i_ ->Table[ Mod[i+k, 8], {k, 8}]]; Do[idi=IntegerDigits[k, 8, 8]; try= Function[w, First[temp=Union[Join @@(Table[RotateRight[w, k], {k, 8}]/.#&)/@ ru8]]][idi]; If[idi===try, tor8=Flatten[ {tor8, {{Length[temp], idi}}}, 1] ], {k, 0, 8^8-1}];
a[n_]:=Sum[d EulerPhi[d]n^(n/d), {d, Divisors[n]}]/n^2; Array[a, 21] (* Stefano Spezia, May 21 2024 *)
PROG
(PARI) a(n) = sumdiv(n, d, d*eulerphi(d)*n^(n/d))/n^2; \\ Michel Marcus, Aug 05 2016
CROSSREFS
Cf. A081720.
Cf. A000312: All endofunctions.
Cf. A000169: Classes under translation mod n.
Cf. A001700: Classes under sort.
Cf. A056665: Classes under rotation.
Cf. A168658: Classes under complement to n+1.
Cf. A130293: Classes under translation and rotation.
Cf. A081721: Classes under rotation and reversal.
Cf. A275549: Classes under reversal.
Cf. A275550: Classes under reversal and complement.
Cf. A275551: Classes under translation and reversal.
Cf. A275552: Classes under translation and complement.
Cf. A275553: Classes under translation, complement and reversal.
Cf. A275554: Classes under translation, rotation and complement.
Cf. A275555: Classes under translation, rotation and reversal.
Cf. A275556: Classes under translation, rotation, complement and reversal.
Cf. A275557: Classes under rotation and complement.
Cf. A275558: Classes under rotation, complement and reversal.
KEYWORD
nonn
AUTHOR
Wouter Meeussen, Aug 06 2007, Aug 14 2007
STATUS
approved