|
|
A298941
|
|
Number of permutations of the multiset of prime factors of n > 1 that are Lyndon words.
|
|
7
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,29
|
|
LINKS
|
|
|
EXAMPLE
|
The a(90) = 3 Lyndon permutations are {2,3,3,5}, {2,3,5,3}, {2,5,3,3}.
|
|
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])):
|
|
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]]];
|
|
CROSSREFS
|
Cf. A000740, A001037, A001222, A008480, A008965, A059966, A060223, A096443, A112798, A215366, A275024, A294859, A298947.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|