A130293 Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.

1, 2, 5, 20, 129, 1316, 16813, 262284, 4783029, 100002024, 2357947701, 61917406672, 1792160394049, 56693913450992, 1946195068379933, 72057594071484456, 2862423051509815809, 121439531097819321972, 5480386857784802185957, 262144000000051200072048, 13248496640331026150086281

Offset: 1

Author

Wouter Meeussen, Aug 06 2007, Aug 14 2007

Keywords

• nonn

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)

Examples

			The 5 necklaces for n=3 are: 000, 001, 002, 012 and 021.
		

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.

Crossrefs

Cf. A002075-A002076.

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.

Programs

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

PARI

a(n) = sumdiv(n, d, d*eulerphi(d)*n^(n/d))/n^2; \\ Michel Marcus, Aug 05 2016

Formula

a(n) = (1/n^2)*Sum_{d|n} d*phi(d)*n^(n/d). - Vladeta Jovovic, Aug 14 2007, Aug 24 2007