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

Offset: 1

Author

Gus Wiseman, Aug 10 2024

Keywords

• nonn

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.

Examples

			The a(1) = 0 through a(6) = 10 compositions:
     .  .  .  (121)  (131)   (132)
                     (1121)  (141)
                     (1211)  (1131)
                             (1212)
                             (1221)
                             (1311)
                             (2121)
                             (11121)
                             (11211)
                             (12111)
		

Links

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

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.

Programs

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
				

Formula

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