A261599 Number of primitive (aperiodic, or Lyndon) necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.

1, 1, 0, 1, 1, 3, 13, 24, 67, 252, 1795, 4038, 16812, 61750, 349806, 3485026, 10391070, 49433135, 240064988, 1282012986, 9167581934, 131550811985, 459677212302, 2707382738558, 14318807586215, 94084166753923, 601900541189696, 5894253303715121

Offset

0,6

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

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, Lyndon word

Wikipedia, Necklace (combinatorics)

Index entries for sequences related to necklaces

Formula

a(n) = (1/n) * Sum_{d | n} moebius(n/d) * A007837(d) for n>0. - Andrew Howroyd, Dec 21 2017

Example

a(4) = 1: 0001.
a(5) = 3: 00001, 00011, 00101.
a(6) = 13: 000001, 000011, 000101, 000112, 000121, 000122, 001012, 001021, 001022, 001102, 001201, 001202, 010102.
a(7) = 24: 0000001, 0000011, 0000101, 0000111, 0000112, 0000121, 0000122, 0001001, 0001011, 0001012, 0001021, 0001022, 0001101, 0001102, 0001201, 0001202, 0010011, 0010012, 0010021, 0010022, 0010101, 0010102, 0010201, 0010202.

Maple

with(numtheory):
b:= proc(n, i, g, d, j) option remember; `if`(i*(i+1)/2<n or g>0
       and g<d, 0, `if`(n=0, `if`(d=g, 1, 0), b(n, i-1, g, d, j)+
      `if`(i>n, 0, binomial(n/j, i/j)*b(n-i, i-1, igcd(i, g), d, j))))
    end:
a:= n-> `if`(n=0, 1, add(add((f-> `if`(f=0, 0, f*b(n$2, 0, d, j)))(
                     mobius(j)), j=divisors(d)), d=divisors(n))/n):
seq(a(n), n=0..30);

Mathematica

a[0] = 1; a[n_] := With[{P = Product[1 + x^k/k!, {k, 1, n}] + O[x]^(n+1) // Normal}, DivisorSum[n, MoebiusMu[n/#]*#!*Coefficient[P, x, #]&]/n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 28 2018, after Andrew Howroyd *)

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, moebius(n/d)*d!*polcoeff(p, d))/n)} \\ Andrew Howroyd, Dec 21 2017

Crossrefs

Cf. A007837, A261531, A261600.

Sequence in context: A260798 A102010 A121718 * A144826 A030552 A146371

Adjacent sequences: A261596 A261597 A261598 * A261600 A261601 A261602

Keyword

nonn

Author

Alois P. Heinz, Aug 25 2015

Status

approved