A298941 Number of permutations of the multiset of prime factors of n > 1 that are Lyndon words.

1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 2, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 0, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 3, 1, 1, 1, 1, 1, 3

Offset: 2

Author

Gus Wiseman, Jan 29 2018

Keywords

• nonn

Examples

			The a(90) = 3 Lyndon permutations are {2,3,3,5}, {2,3,5,3}, {2,5,3,3}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..20000

Crossrefs

Cf. A000740, A001037, A001222, A008480, A008965, A059966, A060223, A096443, A112798, A215366, A275024, A294859, A298947.

Programs

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)):
a:= n-> g(map(i-> i[2], ifactors(n)[2])):
seq(a(n), n=2..150);  # Alois P. Heinz, Feb 09 2018

Mathematica

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Permutations[primeMS[n]],LyndonQ]],{n,2,60}]
(* Second program: *)
multinomial[n_, k_List] := n!/Times @@ (k!);
g[l_] := With[{n = Total[l]}, If[n == 0, 1, Sum[MoebiusMu[j] multinomial[ n/j, l/j], {j, Divisors[GCD @@ l]}]/n]];
a[n_] := g[FactorInteger[n][[All, 2]]];
a /@ Range[2, 150] (* Jean-François Alcover, Dec 15 2020, after Alois P. Heinz *)