|
%I #10 Dec 08 2018 15:51:22
%S 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,
%T 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,
%U 51,120,9,21,0,8,5,35,0,180,0,1,70,9,14,28,0,120
%N Number of Lyndon permutations of a multiset whose multiplicities are the prime indices of n > 1.
%C 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}.
%C 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.
%C a(1) = 1 by convention.
%H Andrew Howroyd, <a href="/A318808/b318808.txt">Table of n, a(n) for n = 1..1000</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Lyndon_word">Lyndon word</a>
%F a(p) = 0 for prime p. - _Andrew Howroyd_, Dec 08 2018
%e The a(30) = 10 Lyndon permutations of {1,1,1,2,2,3}:
%e (111223)
%e (111232)
%e (111322)
%e (112123)
%e (112132)
%e (112213)
%e (112312)
%e (113122)
%e (113212)
%e (121213)
%t nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
%t LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
%t Table[Length[Select[Permutations[nrmptn[n]],LyndonQ]],{n,2,100}]
%o (PARI) sig(n)={my(f=factor(n)); concat(vector(#f~, i, vector(f[i,2], j, primepi(f[i,1]))))}
%o count(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
%o a(n)={if(n==1, 1, count(sig(n)))} \\ _Andrew Howroyd_, Dec 08 2018
%Y Cf. A000670, A005651, A008480, A019536, A056239, A060223, A112798, A296372, A298941, A305936, A318762, A318810.
%K nonn
%O 1,8
%A _Gus Wiseman_, Sep 04 2018
|
