%I #37 Feb 16 2025 08:33:26
%S 1,1,1,2,2,4,15,25,69,254,1799,4039,16828,61751,349831,3485031,
%T 10391139,49433136,240065255,1282012987,9167583734,131550812011,
%U 459677216341,2707382738559,14318807603110,94084166753927,601900541251447,5894253303715375
%N Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.
%H Alois P. Heinz, <a href="/A261531/b261531.txt">Table of n, a(n) for n = 0..260</a>
%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Necklace.html">Necklace</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Necklace_(combinatorics)">Necklace (combinatorics)</a>
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F a(n) = (1/n) * Sum_{d | n} phi(n/d) * A007837(d) for n>0. - _Andrew Howroyd_, Apr 02 2017
%e a(4) = 2: 0000, 0001.
%e a(5) = 4: 00000, 00001, 00011, 00101.
%e a(6) = 15: 000000, 000001, 000011, 000101, 000112, 000121, 000122, 001001, 001012, 001021, 001022, 001102, 001201, 001202, 010102.
%p with(numtheory): with(combinat):
%p g:= l-> (n-> `if`(n=0, 1, add(phi(j)*multinomial(n/j,
%p (l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):
%p b:= proc(n, i, l) `if`(i*(i+1)/2<n, 0,`if`(n=0, g(l),
%p b(n, i-1, l)+`if`(i>n, 0, b(n-i, i-1, [l[], i]))))
%p end:
%p a:= n-> b(n$2, []):
%p seq(a(n), n=0..35);
%t multinomial[n_, k_] := n!/Times @@ (k!);
%t g[l_] := Function[n, If[n==0, 1, Sum[EulerPhi[j]*multinomial[n/j, l/j], {j, Divisors[GCD @@ l]}]/n]][Total[l]];
%t 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]]]]];
%t a[n_] := b[n, n, {}];
%t Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Mar 21 2017, translated from Maple *)
%o (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
%Y Cf. A072605, A261599, A261600.
%K nonn,changed
%O 0,4
%A _Alois P. Heinz_, Aug 23 2015