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

Sequence in context: A012321 A012519 A076795 * A156073 A006366 A012317

Adjacent sequences: A130290 A130291 A130292 * A130294 A130295 A130296

Keyword

nonn

Author

Wouter Meeussen, Aug 06 2007, Aug 14 2007

Status

approved