%I #26 May 22 2024 02:13:20
%S 1,2,5,20,129,1316,16813,262284,4783029,100002024,2357947701,
%T 61917406672,1792160394049,56693913450992,1946195068379933,
%U 72057594071484456,2862423051509815809,121439531097819321972,5480386857784802185957,262144000000051200072048,13248496640331026150086281
%N Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.
%C From _Olivier GĂ©rard_, Aug 01 2016: (Start)
%C Equivalent to the definition: number of classes of endofunctions of [n] under rotation and translation mod n.
%C Classes can be of size between n and n^2 depending on divisibility properties of n.
%C n n 2n 3n ... n^2
%C --------------------------
%C 1 1
%C 2 2
%C 3 3 2
%C 4 4 2 14
%C 5 5 0 124
%C 6 6 6 22 1282
%C 7 7 0 16806
%C 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.
%C (End)
%H Stefano Spezia, <a href="/A130293/b130293.txt">Table of n, a(n) for n = 1..350</a>
%H Darij Grinberg and Peter Mao, <a href="https://arxiv.org/abs/2405.08937">Necklaces over a group with identity product</a>, arXiv:2405.08937 [math.CO], 2024. See p. 22.
%F a(n) = (1/n^2)*Sum_{d|n} d*phi(d)*n^(n/d). - _Vladeta Jovovic_, Aug 14 2007, Aug 24 2007
%e The 5 necklaces for n=3 are: 000, 001, 002, 012 and 021.
%t 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}];
%t a[n_]:=Sum[d EulerPhi[d]n^(n/d),{d,Divisors[n]}]/n^2; Array[a,21] (* _Stefano Spezia_, May 21 2024 *)
%o (PARI) a(n) = sumdiv(n, d, d*eulerphi(d)*n^(n/d))/n^2; \\ _Michel Marcus_, Aug 05 2016
%Y Cf. A002075-A002076.
%Y Cf. A081720.
%Y Cf. A000312: All endofunctions.
%Y Cf. A000169: Classes under translation mod n.
%Y Cf. A001700: Classes under sort.
%Y Cf. A056665: Classes under rotation.
%Y Cf. A168658: Classes under complement to n+1.
%Y Cf. A130293: Classes under translation and rotation.
%Y Cf. A081721: Classes under rotation and reversal.
%Y Cf. A275549: Classes under reversal.
%Y Cf. A275550: Classes under reversal and complement.
%Y Cf. A275551: Classes under translation and reversal.
%Y Cf. A275552: Classes under translation and complement.
%Y Cf. A275553: Classes under translation, complement and reversal.
%Y Cf. A275554: Classes under translation, rotation and complement.
%Y Cf. A275555: Classes under translation, rotation and reversal.
%Y Cf. A275556: Classes under translation, rotation, complement and reversal.
%Y Cf. A275557: Classes under rotation and complement.
%Y Cf. A275558: Classes under rotation, complement and reversal.
%K nonn
%O 1,2
%A _Wouter Meeussen_, Aug 06 2007, Aug 14 2007