A261600 Number of primitive (aperiodic, or Lyndon) necklaces with n beads such that beads of a largest subset have label 0, beads of a largest remaining subset have label 1, and so on.

1, 1, 1, 3, 11, 49, 265, 1640, 11932, 96780, 887931, 8939050, 99298073, 1195617442, 15619180497, 219049941148, 3293800823995, 52746930894773, 897802366153076, 16167544246362566, 307372573010691195, 6148811682561388635, 129164845357775064609

Offset

0,4

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) ~ c * (n-1)!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264818011615... . - Vaclav Kotesovec, Aug 27 2015

Example

a(3) = 3: 001, 012, 021.
a(4) = 11: 0001, 0011, 0012, 0021, 0102, 0123, 0132, 0213, 0231, 0312, 0321.

Maple

with(numtheory):
b:= proc(n, i, g, d, j) option remember; `if`(g>0 and g<d, 0,
      `if`(n=0, `if`(d=g, 1, 0), `if`(i<1, 0, b(n, i-1, g, d, j)+
      `if`(i>n, 0, binomial(n/j, i/j)*b(n-i, i, 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..25);

Mathematica

b[n_, i_, g_, d_, j_] := b[n, i, g, d, j] = If[g>0 && g<d, 0, If[n==0, If[d == g, 1, 0], If[i<1, 0, b[n, i-1, g, d, j] + If[i>n, 0, Binomial[n/j, i/j]*b[n-i, i, GCD[i, g], d, j]]]]]; a[n_] := If[n==0, 1, Sum[Sum[ Function[f, If[f==0, 0, f*b[n, n, 0, d, j]]][MoebiusMu[j]], {j, Divisors[ d]}], {d, Divisors[n]}]/n]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

Crossrefs

Cf. A072605, A247551, A261531, A261599.

Sequence in context: A307030 A335788 A012316 * A331617 A193319 A265905

Adjacent sequences: A261597 A261598 A261599 * A261601 A261602 A261603

Keyword

nonn

Author

Alois P. Heinz, Aug 27 2015

Status

approved