A376263 Number of strict integer compositions of n whose leaders of increasing runs are increasing.

1, 1, 1, 2, 2, 3, 5, 6, 8, 11, 18, 21, 30, 38, 52, 77, 96, 126, 167, 217, 278, 402, 488, 647, 822, 1073, 1340, 1747, 2324, 2890, 3695, 4690, 5924, 7469, 9407, 11718, 15405, 18794, 23777, 29507, 37188, 45720, 57404, 70358, 87596, 110672, 135329, 167018, 206761, 254200, 311920

Offset: 0

Author

Gus Wiseman, Sep 18 2024

Keywords

• nonn

Comments

The leaders of increasing runs of a sequence are obtained by splitting it into maximal increasing subsequences and taking the first term of each.

Examples

			The a(1) = 1 through a(9) = 11 compositions:
 (1) (2) (3)   (4)   (5)   (6)     (7)     (8)     (9)
         (1,2) (1,3) (1,4) (1,5)   (1,6)   (1,7)   (1,8)
                     (2,3) (2,4)   (2,5)   (2,6)   (2,7)
                           (1,2,3) (3,4)   (3,5)   (3,6)
                           (1,3,2) (1,2,4) (1,2,5) (4,5)
                                   (1,4,2) (1,3,4) (1,2,6)
                                           (1,4,3) (1,3,5)
                                           (1,5,2) (1,5,3)
                                                   (1,6,2)
                                                   (2,3,4)
                                                   (2,4,3)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Crossrefs

For less-greater or greater-less we have A294617.

This is a strict case of A374688, weak version A374635.

The strict less-greater version is A374689, weak version A189076.

A003242 counts anti-run compositions, ranks A333489.

A011782 counts compositions, strict A032020.

A238130, A238279, A333755 count compositions by number of runs.

A373949 counts compositions by run-compressed sum, opposite A373951.

A374700 counts compositions by sum of leaders of strictly increasing runs.

Cf. A000110, A008289, A056823, A106356, A188920, A238343, A261982, A274174, A333213, A374634, A374683, A374698, A374763.

Programs

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@#&&Less@@First/@Split[#,Less]&]],{n,0,15}]

PARI

\\ here Q(n) gives n-th row of A008289.
Q(n)={Vecrev(polcoef(prod(k=1, n, 1 + y*x^k, 1 + O(x*x^n)), n)/y)}
a(n)={if(n==0, 1, my(r=Q(n), s=Vec(serlaplace(exp(exp(x+O(x^#r))- 1)))); sum(k=1, #r, r[k]*s[k]))} \\ Andrew Howroyd, Sep 18 2024

Formula

a(n) = Sum_{k>=1} A008289(n,k)*A000110(k-1) for n > 0. - Andrew Howroyd, Sep 18 2024

Extensions

a(26) onwards from Andrew Howroyd, Sep 18 2024