cp's OEIS Frontend

A019536 Number of length n necklaces with integer entries that cover an initial interval of positive integers.

%I A019536 #97 Feb 16 2025 08:32:33
%S A019536 1,2,5,20,109,784,6757,68240,787477,10224812,147512053,2340964372,
%T A019536 40527565261,760095929840,15352212731933,332228417657960,
%U A019536 7668868648772701,188085259070219000,4884294069438337429
%N A019536 Number of length n necklaces with integer entries that cover an initial interval of positive integers.
%C A019536 Original name: a(n) = number of necklaces of n beads with up to n unlabeled colors.
%C A019536 The Moebius transform of this sequence is A060223.
%H A019536 G. C. Greubel, <a href="/A019536/b019536.txt">Table of n, a(n) for n = 1..420</a>
%H A019536 M. Goebel, <a href="https://doi.org/10.1007/s002000050088">On the number of special permutation-invariant orbits and terms</a>, 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).
%H A019536 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A019536 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A019536 Eric Weisstein's world of Mathematics, <a href="https://mathworld.wolfram.com/Necklace.html">Necklaces</a>.
%F A019536 See Mathematica code.
%F A019536 a(n) ~ (n-1)! / (2 * log(2)^(n+1)). - _Vaclav Kotesovec_, Jul 21 2019
%F A019536 From _Petros Hadjicostas_, Aug 19 2019: (Start)
%F A019536 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.
%F A019536 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).
%F A019536 a(n) = (1/n) * Sum_{d|n} phi(d) * A000670(n/d).
%F A019536 a(n) = Sum_{d|n} A060223(d).
%F A019536 (End)
%F A019536 From _Richard L. Ollerton_, May 07 2021: (Start)
%F A019536 a(n) = (1/n)*Sum_{k=1..n} A000670(gcd(n,k)).
%F A019536 a(n) = (1/n)*Sum_{k=1..n} A000670(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
%e A019536 a(3) = 5 since there are the following length 3 words up to rotation:
%e A019536      111,  112, 122, 123, 132.
%e A019536 a(4) = 20 since there are the following length 4 words up to rotation:
%e A019536      1111,
%e A019536      1112, 1122, 1212, 1222,
%e A019536      1123, 1132, 1213, 1223, 1232, 1233, 1322, 1323, 1332,
%e A019536      1234, 1243, 1324, 1342, 1423, 1432.
%t A019536 Needs["DiscreteMath`Combinatorica`"];
%t A019536 mult[li:{__Integer}] := Multinomial @@ Length /@ Split[Sort[li]];
%t A019536 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];
%t A019536 Table[(mult /@ Partitions[n]).(neck /@ Partitions[n]), {n, 24}]
%t A019536 (* second program: *)
%t A019536 a[n_] := Sum[DivisorSum[n, EulerPhi[#]*StirlingS2[n/#, k] k! &]/n, {k, 1, n}];
%t A019536 Table[a[n], {n, 1, 20}] (* _Jean-François Alcover_, Mar 31 2016, after _Philippe Deléham_ *)
%o A019536 (PARI) a(n) = sum(k=1, n, sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2)*k!)/n); \\ _Michel Marcus_, Mar 31 2016
%Y A019536 Cf. A000670, A008277, A019537, A060223.
%Y A019536 Row sums of A087854. - _Philippe Deléham_
%K A019536 easy,nonn
%O A019536 1,2
%A A019536 Manfred Goebel (goebel(AT)informatik.uni-tuebingen.de)
%E A019536 Edited by _Wouter Meeussen_, Aug 06 2002
%E A019536 Corrected by _T. D. Noe_, Oct 31 2006
%E A019536 Edited by _Andrew Howroyd_, Aug 19 2019