A375140 - OEIS

A375140

Number of integer compositions of n whose leaders of weakly increasing runs are not strictly decreasing.

0, 0, 0, 1, 3, 10, 26, 65, 151, 343, 750, 1614, 3410, 7123, 14724, 30220, 61639, 125166, 253233, 510936, 1028659, 2067620, 4150699, 8324552, 16683501, 33417933, 66910805, 133931495, 268023257, 536279457, 1072895973, 2146277961, 4293254010, 8587507415

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

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

Also the number of integer compositions of n matching the dashed patterns 1-32 or 1-21.

LINKS

Table of n, a(n) for n=1..34.

Wikipedia, Permutation pattern.

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

FORMULA

a(n) = 2^(n-1) - A188920(n).

EXAMPLE

The a(1) = 0 through a(6) = 10 compositions:

. . . (121) (131) (132)

(1121) (141)

(1211) (1131)

(1212)

(1221)

(1311)

(2121)

(11121)

(11211)

(12111)

MATHEMATICA

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], !Greater@@First/@Split[#, LessEqual]&]], {n, 15}]

- or -

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], MatchQ[#, {___, x_, ___, z_, y_, ___}/; x<=y<z]&]], {n, 0, 15}]

CROSSREFS

For leaders of identical runs we have A056823.

The complement is counted by A188920.

Leaders of weakly increasing runs are rows of A374629, sum A374630.

For weakly decreasing leaders we have A374636, ranks A375137 or A375138.

For leaders of weakly decreasing runs we have the complement of A374746.

Compositions of this type are ranked by A375295, reverse A375296.

A003242 counts anti-runs, ranks A333489.

A106356 counts compositions by number of maximal anti-runs.

A238424 counts partitions whose first differences are an anti-run.

A274174 counts contiguous compositions, ranks A374249.

A011782 counts compositions.

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

A335456 counts patterns matched by compositions.

A335548 counts non-contiguous compositions, ranks A374253.

A374637 counts compositions by sum of leaders of weakly increasing runs.

Cf. A124766, A238343, A261982, A333213, A335514, A373949, A374635, A374678, A374687, A374761.

Sequence in context: A333897 A316937 A269965 * A110158 A301308 A196232

Adjacent sequences: A375137 A375138 A375139 * A375141 A375142 A375143

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 10 2024

STATUS

approved