A318808 Number of Lyndon permutations of a multiset whose multiplicities are the prime indices of n > 1.

1, 1, 0, 1, 0, 1, 0, 2, 1, 1, 0, 3, 0, 1, 2, 6, 0, 6, 0, 4, 2, 1, 0, 12, 3, 1, 14, 5, 0, 10, 0, 24, 3, 1, 5, 30, 0, 1, 3, 20, 0, 15, 0, 6, 30, 1, 0, 60, 8, 20, 4, 7, 0, 90, 7, 30, 4, 1, 0, 60, 0, 1, 51, 120, 9, 21, 0, 8, 5, 35, 0, 180, 0, 1, 70, 9, 14, 28, 0, 120

Offset: 1

Author

Gus Wiseman, Sep 04 2018

Keywords

• nonn

Comments

This multiset is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

The Lyndon product of two or more finite sequences is defined to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product.

a(1) = 1 by convention.

Examples

			The a(30) = 10 Lyndon permutations of {1,1,1,2,2,3}:
  (111223)
  (111232)
  (111322)
  (112123)
  (112132)
  (112213)
  (112312)
  (113122)
  (113212)
  (121213)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Wikipedia, Lyndon word

Crossrefs

Cf. A000670, A005651, A008480, A019536, A056239, A060223, A112798, A296372, A298941, A305936, A318762, A318810.

Programs

Mathematica

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{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[nrmptn[n]],LyndonQ]],{n,2,100}]

PARI

sig(n)={my(f=factor(n)); concat(vector(#f~, i, vector(f[i,2], j, primepi(f[i,1]))))}
count(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
a(n)={if(n==1, 1, count(sig(n)))} \\ Andrew Howroyd, Dec 08 2018

Formula

a(p) = 0 for prime p. - Andrew Howroyd, Dec 08 2018