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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A019536 a(n) = number of necklaces of n beads with up to n unlabeled colors. 12
1, 2, 5, 20, 109, 784, 6757, 68240, 787477, 10224812, 147512053, 2340964372, 40527565261, 760095929840, 15352212731933, 332228417657960, 7668868648772701, 188085259070219000, 4884294069438337429 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

The Moebius transform of this sequence is A060223.

LINKS

G. C. Greubel, Table of n, a(n) for n = 1..420

M. Goebel, On the number of special permutation-invariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505-509 (Lect. Notes Comp. Sci.)

F. Ruskey, Necklaces with Fixed Density

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]

Eric Weisstein's world of Mathematics, Necklaces

FORMULA

See Mathematica code

EXAMPLE

a(3)=5 since the partitions of the 3 (unlabeled) colors are {3}:RRR, {2,1}:RRG and {1,1,1}:RGB, with multiplicities resp. *1, *2, *1, ( *2 since partitioning 3 beads over a bin of 2 and a bin of 1), so the necklaces are {R,R,R},{R,R,G},{R,G,G},{R,G,B},{R,B,G}.

MATHEMATICA

Needs["DiscreteMath`Combinatorica`"]; mult[li:{__Integer}] := Multinomial @@ Length /@ Split[Sort[li]]; neck[li:{__Integer}] := Module[{n, d}, n=Plus @@ li; d=n-First[li]; Fold[ #1+(EulerPhi[ #2]*(n/#2)!)/Times @@ ((li/#2)!)&, 0, Divisors[GCD @@ li]]/n]; Table[(mult /@ Partitions[n]).(neck /@ Partitions[n]), {n, 24}]

(* second program: *)

a[n_] := Sum[DivisorSum[n, EulerPhi[#]*StirlingS2[n/#, k] k! &]/n, {k, 1, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Mar 31 2016, after Philippe Deléham *)

PROG

(PARI) a(n) = sum(k=1, n, sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2)*k!)/n); \\ Michel Marcus, Mar 31 2016

CROSSREFS

Cf. A000670, A019537.

Row sums of A087854. - Philippe Deléham

Sequence in context: A296727 A201224 A305922 * A129949 A127065 A168357

Adjacent sequences:  A019533 A019534 A019535 * A019537 A019538 A019539

KEYWORD

easy,nonn

AUTHOR

Manfred Goebel (goebel(AT)informatik.uni-tuebingen.de)

EXTENSIONS

Edited by Wouter Meeussen, Aug 06 2002

Corrected by T. D. Noe, Oct 31 2006

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 November 17 05:59 EST 2018. Contains 317275 sequences. (Running on oeis4.)