OFFSET
1,3
EXAMPLE
The a(6) = 7 partitions are (6), (51), (42), (411), (3111), (2211), (21111). This list does not include (321) because there are two possible permutations that are Lyndon words, namely (123) and (132). The list does not include (33), (222), or (111111) because no permutation of these is a Lyndon word.
MAPLE
with(combinat): with(numtheory):
g:= l-> (n-> `if`(n=0, 1, add(mobius(j)*multinomial(n/j,
(l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):
b:= (n, i, l)-> `if`(n=0 or i=1, `if`(g([l[], n])=1, 1, 0),
add(b(n-i*j, i-1, [l[], j]), j=0..n/i)):
a:= n-> b(n$2, []):
seq(a(n), n=1..30); # Alois P. Heinz, Feb 09 2018
MATHEMATICA
LyndonQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And]&&Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
Table[Length[Select[IntegerPartitions[n], Length[Select[Permutations[#], LyndonQ]]===1&]], {n, 20}]
(* Second program: *)
multinomial[n_, k_List] := n!/Times @@ (k!);
g[l_List] := With[{n = Total[l]}, If[n == 0, 1, Sum[MoebiusMu[j]*multinomial[n/j, l/j], {j, Divisors[GCD @@ l]}]/n]];
b[n_, i_, l_List] := If[n == 0 || i == 1, If[g[Append[l, n]] == 1, 1, 0], Sum[b[n - i*j, i - 1, Append[l, j]], {j, 0, n/i}]];
a[n_] := b[n, n, {}];
Array[a, 30] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 30 2018
EXTENSIONS
a(23)-a(62) from Alois P. Heinz, Feb 09 2018
STATUS
approved