cp's OEIS Frontend

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

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