cp's OEIS Frontend

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

%I A296373 #15 Dec 02 2018 18:40:48
%S A296373 1,1,1,2,1,1,3,3,1,1,6,5,3,1,1,9,12,6,3,1,1,18,21,14,6,3,1,1,30,45,27,
%T A296373 15,6,3,1,1,56,84,61,29,15,6,3,1,1,99,170,120,67,30,15,6,3,1,1,186,
%U A296373 323,254,136,69,30,15,6,3,1,1,335,640,510,295,142,70,30,15,6,3,1,1
%N A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.
%H A296373 Andrew Howroyd, <a href="/A296373/b296373.txt">Table of n, a(n) for n = 1..1275</a>
%H A296373 Wikipedia, <a href="http://en.wikipedia.org/wiki/Lyndon_word#Standard_factorization">Lyndon word: Standard factorization</a>
%F A296373 First column is A059966.
%e A296373 Triangle begins:
%e A296373     1;
%e A296373     1,   1;
%e A296373     2,   1,   1;
%e A296373     3,   3,   1,   1;
%e A296373     6,   5,   3,   1,   1;
%e A296373     9,  12,   6,   3,   1,   1;
%e A296373    18,  21,  14,   6,   3,   1,   1;
%e A296373    30,  45,  27,  15,   6,   3,   1,   1;
%e A296373    56,  84,  61,  29,  15,   6,   3,   1,   1;
%e A296373    99, 170, 120,  67,  30,  15,   6,   3,   1,   1;
%e A296373   186, 323, 254, 136,  69,  30,  15,   6,   3,   1,   1;
%e A296373   335, 640, 510, 295, 142,  70,  30,  15,   6,   3,   1,   1;
%t A296373 neckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
%t A296373 aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
%t A296373 qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
%t A296373 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[qit[#]]===k&]],{n,12},{k,n}]
%o A296373 (PARI) EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
%o A296373 A(n)=[Vecrev(p/y) | p<-EulerMT(y*vector(n, n, sumdiv(n, d, moebius(n/d) * (2^d-1))/n))]
%o A296373 { my(T=A(12)); for(n=1, #T, print(T[n])) } \\ _Andrew Howroyd_, Dec 01 2018
%Y A296373 Cf. A000740, A001045, A008965, A019536, A059966, A060223, A185700, A228369, A232472, A277427, A281013, A296302, A296372.
%K A296373 nonn,tabl
%O A296373 1,4
%A A296373 _Gus Wiseman_, Dec 11 2017