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)
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = (1/n)*Sum_{k=1..n} A000670(gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} A000670(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (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
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