login
A261531
Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.
4
1, 1, 1, 2, 2, 4, 15, 25, 69, 254, 1799, 4039, 16828, 61751, 349831, 3485031, 10391139, 49433136, 240065255, 1282012987, 9167583734, 131550812011, 459677216341, 2707382738559, 14318807603110, 94084166753927, 601900541251447, 5894253303715375
OFFSET
0,4
LINKS
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Eric Weisstein's World of Mathematics, Necklace
FORMULA
a(n) = (1/n) * Sum_{d | n} phi(n/d) * A007837(d) for n>0. - Andrew Howroyd, Apr 02 2017
EXAMPLE
a(4) = 2: 0000, 0001.
a(5) = 4: 00000, 00001, 00011, 00101.
a(6) = 15: 000000, 000001, 000011, 000101, 000112, 000121, 000122, 001001, 001012, 001021, 001022, 001102, 001201, 001202, 010102.
MAPLE
with(numtheory): with(combinat):
g:= l-> (n-> `if`(n=0, 1, add(phi(j)*multinomial(n/j,
(l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):
b:= proc(n, i, l) `if`(i*(i+1)/2<n, 0, `if`(n=0, g(l),
b(n, i-1, l)+`if`(i>n, 0, b(n-i, i-1, [l[], i]))))
end:
a:= n-> b(n$2, []):
seq(a(n), n=0..35);
MATHEMATICA
multinomial[n_, k_] := n!/Times @@ (k!);
g[l_] := Function[n, If[n==0, 1, Sum[EulerPhi[j]*multinomial[n/j, l/j], {j, Divisors[GCD @@ l]}]/n]][Total[l]];
b[n_, i_, l_] := If[i*(i+1)/2<n, 0, If[n==0, g[l], b[n, i-1, l] + If[i>n, 0, b[n-i, i-1, Append[l, i]]]]];
a[n_] := b[n, n, {}];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Mar 21 2017, translated from Maple *)
PROG
(PARI) a(n)={if(n==0, 1, my(p=prod(k=1, n, (1+x^k/k!) + O(x*x^n))); sumdiv(n, d, eulerphi(n/d)*d!*polcoeff(p, d))/n)} \\ Andrew Howroyd, Dec 21 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Aug 23 2015
STATUS
approved