login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A130293 Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent. 15
1, 2, 5, 20, 129, 1316, 16813, 262284, 4783029, 100002024, 2357947701, 61917406672, 1792160394049, 56693913450992, 1946195068379933, 72057594071484456, 2862423051509815809, 121439531097819321972 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..18.

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}];

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 04:04 EDT 2018. Contains 316431 sequences. (Running on oeis4.)