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

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, 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, 323, 254, 136, 69, 30, 15, 6, 3, 1, 1, 335, 640, 510, 295, 142, 70, 30, 15, 6, 3, 1, 1

Offset

1,4

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Wikipedia, Lyndon word: Standard factorization

Formula

First column is A059966.

Example

Triangle begins:
    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,  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, 323, 254, 136,  69,  30,  15,   6,   3,   1,   1;
  335, 640, 510, 295, 142,  70,  30,  15,   6,   3,   1,   1;

Mathematica

neckQ[q_]:=Array[OrderedQ[{RotateRight[q, #], q}]&, Length[q]-1, 1, And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q, k], {k, Length[q]}];
qit[q_]:=If[#===Length[q], {q}, Prepend[qit[Drop[q, #]], Take[q, #]]]&[Max@@Select[Range[Length[q]], neckQ[Take[q, #]]&&aperQ[Take[q, #]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[qit[#]]===k&]], {n, 12}, {k, n}]

Prog

(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)}
A(n)=[Vecrev(p/y) | p<-EulerMT(y*vector(n, n, sumdiv(n, d, moebius(n/d) * (2^d-1))/n))]
{ my(T=A(12)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 01 2018

Crossrefs

Cf. A000740, A001045, A008965, A019536, A059966, A060223, A185700, A228369, A232472, A277427, A281013, A296302, A296372.

Sequence in context: A304942 A090011 A061554 * A345710 A088326 A216956

Adjacent sequences: A296370 A296371 A296372 * A296374 A296375 A296376

Keyword

nonn,tabl

Author

Gus Wiseman, Dec 11 2017

Status

approved