A261531 Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.

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

Author

Alois P. Heinz, Aug 23 2015

Keywords

• nonn

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..260
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Eric Weisstein's World of Mathematics, Necklace
• Wikipedia, Necklace (combinatorics)
• Index entries for sequences related to necklaces

Crossrefs

Cf. A072605, A261599, A261600.

Programs

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)/2n, 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)/2n, 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 *)

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

Formula

a(n) = (1/n) * Sum_{d | n} phi(n/d) * A007837(d) for n>0. - Andrew Howroyd, Apr 02 2017