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

Author

Alois P. Heinz, Aug 27 2015

Keywords

• nonn

Examples

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

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

Crossrefs

Cf. A072605, A247551, A261531, A261599.

Programs

Maple

with(numtheory):
b:= proc(n, i, g, d, j) option remember; `if`(g>0 and gn, 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 && gn, 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 *)

Formula

a(n) ~ c * (n-1)!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264818011615... . - Vaclav Kotesovec, Aug 27 2015