|
|
A019536
|
|
Number of length n necklaces with integer entries that cover an initial interval of positive integers.
|
|
45
|
|
|
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
|
Eric Weisstein's world of Mathematics, Necklaces.
|
|
FORMULA
|
See Mathematica code.
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).
(End)
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}];
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|