A299070 Regular triangle T(n,k) is the number of compositions of n whose standard factorization into Lyndon words has k distinct factors.

1, 2, 0, 3, 1, 0, 5, 3, 0, 0, 7, 9, 0, 0, 0, 13, 17, 2, 0, 0, 0, 19, 39, 6, 0, 0, 0, 0, 35, 72, 21, 0, 0, 0, 0, 0, 59, 141, 55, 1, 0, 0, 0, 0, 0, 107, 266, 132, 7, 0, 0, 0, 0, 0, 0, 187, 511, 300, 26, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Author

Gus Wiseman, Feb 01 2018

Keywords

• nonn
• tabl

Comments

Row sums are 2^(n-1). First column is A008965. A version without the zeros is A299072.

Examples

			Triangle begins:
    1
    2    0
    3    1    0
    5    3    0    0
    7    9    0    0    0
   13   17    2    0    0    0
   19   39    6    0    0    0    0
   35   72   21    0    0    0    0    0
   59  141   55    1    0    0    0    0    0
  107  266  132    7    0    0    0    0    0    0
  187  511  300   26    0    0    0    0    0    0    0.
The a(5,2) = 9 compositions are (41), (32), (311), (131), (221), (212), (2111), (1211), (1121) with factorizations
    (41) = (4) * (1)
    (32) = (3) * (2)
   (311) = (3) * (1)^2
   (131) = (13) * (1)
   (221) = (2)^2 * (1)
   (212) = (2) * (12)
  (2111) = (2) * (1)^3
  (1211) = (12) * (1)^2
  (1121) = (112) * (1).
		

Crossrefs

Cf. A001045, A001221, A008965, A059966, A116608, A146289, A185700, A296373, A299072.

Programs

Mathematica

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