cp's OEIS Frontend

A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.

%I A296372 #27 Dec 16 2018 17:42:10
%S A296372 1,1,2,4,5,4,18,31,18,8,108,208,153,56,16,778,1700,1397,616,160,32,
%T A296372 6756,15980,14668,7197,2196,432,64,68220,172326,171976,93293,31564,
%U A296372 7208,1120,128
%N A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.
%C A296372 A finite sequence is normal if its union is an initial interval of positive integers.
%H A296372 Andrew Howroyd, <a href="/A296372/b296372.txt">Rows n = 1..50 of triangle, flattened</a>
%H A296372 Wikipedia, <a href="http://en.wikipedia.org/wiki/Lyndon_word#Standard_factorization">Lyndon word: Standard factorization</a>
%e A296372 The T(3,2) = 5 normal sequences are {2,1,2}, {1,2,1}, {2,1,3}, {2,3,1}, {3,1,2}.
%e A296372 Triangle begins:
%e A296372      1;
%e A296372      1,     2;
%e A296372      4,     5,     4;
%e A296372     18,    31,    18,     8;
%e A296372    108,   208,   153,    56,    16;
%e A296372    778,  1700,  1397,   616,   160,    32;
%e A296372   6756, 15980, 14668,  7197,  2196,   432,    64;
%t A296372 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A296372 aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
%t A296372 qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
%t A296372 allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
%t A296372 Table[Length[Select[Join@@Permutations/@allnorm[n],Length[qit[#]]===k&]],{n,5},{k,n}]
%o A296372 (PARI) \\ here U(n,k) is A074650(n,k).
%o A296372 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 A296372 U(n,k)={sumdiv(n, d, moebius(n/d) * k^d)/n}
%o A296372 A(n)={[Vecrev(p/y) | p<-sum(k=1, n, EulerMT(vector(n, n, y*U(n,k)))*sum(j=k, n, (-1)^(k-j)*binomial(j,k)))]}
%o A296372 { my(T=A(10)); for(n=1, #T, print(T[n])) } \\ _Andrew Howroyd_, Dec 08 2018
%Y A296372 Row sums are A000670.
%Y A296372 First column is A060223.
%Y A296372 Cf. A000740, A001045, A008965, A019536, A059966, A074650, A185700, A228369, A232472, A277427, A281013, A296373.
%K A296372 nonn,tabl
%O A296372 1,3
%A A296372 _Gus Wiseman_, Dec 11 2017
%E A296372 Example and program corrected by _Gus Wiseman_, Dec 08 2018