The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A019536 Number of length n necklaces with integer entries that cover an initial interval of positive integers. 28
 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 Original name: a(n) = number of necklaces of n beads with up to n unlabeled colors. 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.); see p. 509 (stated as an open problem). 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. a(n) ~ (n-1)! / (2 * log(2)^(n+1)). - Vaclav Kotesovec, Jul 21 2019 From Petros Hadjicostas, Aug 19 2019: (Start) The first formula is due to Philippe Deléham from the Crossrefs (see also the programs below). The second one follows easily from the first one. The third one follows from the second one using the associative property of Dirichlet convolutions. a(n) = Sum_{k = 1..n} (k!/n) * Sum_{d|n} phi(d) * S2(n/d, k), where S2(n, k) = Stirling numbers of 2nd kind (A008277). a(n) = (1/n) * Sum_{d|n} phi(d) * A000670(n/d). a(n) = Sum_{d|n} A060223(d). (End) EXAMPLE a(3) = 5 since there are the following length 3 words up to rotation:      111,  112, 122, 123, 132. a(4) = 20 since there are the following length 4 words up to rotation:      1111,      1112, 1122, 1212, 1222,      1123, 1132, 1213, 1223, 1232, 1233, 1322, 1323, 1332,      1234, 1243, 1324, 1342, 1423, 1432. 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, A008277, A019537, A060223. 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 Edited by Andrew Howroyd, Aug 19 2019 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 20 20:02 EDT 2020. Contains 337265 sequences. (Running on oeis4.)