|
%I #21 Apr 30 2019 09:55:33
%S 1,1,1,3,11,49,265,1640,11932,96780,887931,8939050,99298073,
%T 1195617442,15619180497,219049941148,3293800823995,52746930894773,
%U 897802366153076,16167544246362566,307372573010691195,6148811682561388635,129164845357775064609
%N 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.
%H Alois P. Heinz, <a href="/A261600/b261600.txt">Table of n, a(n) for n = 0..300</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="http://mathworld.wolfram.com/Necklace.html">Necklace</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lyndon_word">Lyndon word</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) ~ c * (n-1)!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264818011615... . - _Vaclav Kotesovec_, Aug 27 2015
%e a(3) = 3: 001, 012, 021.
%e a(4) = 11: 0001, 0011, 0012, 0021, 0102, 0123, 0132, 0213, 0231, 0312, 0321.
%p with(numtheory):
%p b:= proc(n, i, g, d, j) option remember; `if`(g>0 and g<d, 0,
%p `if`(n=0, `if`(d=g, 1, 0), `if`(i<1, 0, b(n, i-1, g, d, j)+
%p `if`(i>n, 0, binomial(n/j, i/j)*b(n-i, i, igcd(i, g), d, j)))))
%p end:
%p a:= n-> `if`(n=0, 1, add(add((f-> `if`(f=0, 0, f*b(n$2, 0, d, j)))(
%p mobius(j)), j=divisors(d)), d=divisors(n))/n):
%p seq(a(n), n=0..25);
%t 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 *)
%Y Cf. A072605, A247551, A261531, A261599.
%K nonn
%O 0,4
%A _Alois P. Heinz_, Aug 27 2015
|
