A332871 Number of compositions of n whose run-lengths are not weakly increasing.

0, 0, 0, 0, 1, 4, 8, 24, 55, 128, 282, 625, 1336, 2855, 6000, 12551, 26022, 53744, 110361, 225914, 460756, 937413, 1902370, 3853445, 7791647, 15732468, 31725191, 63907437, 128613224, 258626480, 519700800, 1043690354, 2094882574, 4202903667, 8428794336, 16897836060

Offset: 0

Author

Gus Wiseman, Feb 29 2020

Keywords

• nonn

Comments

A composition of n is a finite sequence of positive integers summing to n.

Also compositions whose run-lengths are not weakly decreasing.

Examples

			The a(4) = 1 through a(6) = 8 compositions:
  (112)  (113)   (114)
         (221)   (1113)
         (1112)  (1131)
         (1121)  (1221)
                 (2112)
                 (11112)
                 (11121)
                 (11211)
For example, the composition (2,1,1,2) has run-lengths (1,2,1), which are not weakly increasing, so (2,1,1,2) is counted under a(6).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000

Crossrefs

The version for the compositions themselves (not run-lengths) is A056823.

The version for unsorted prime signature is A112769, with dual A071365.

The case without weakly decreasing run-lengths either is A332833.

The complement is counted by A332836.

Compositions that are not unimodal are A115981.

Compositions with equal run-lengths are A329738.

Compositions whose run-lengths are not unimodal are A332727.

Cf. A001523, A072704, A100883, A181819, A329744, A329766, A332641, A332669, A332726, A332745, A332746, A332834, A332835.

Programs

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!LessEqual@@Length/@Split[#]&]],{n,0,10}]

Formula

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

Extensions

Terms a(21) and beyond from Andrew Howroyd, Dec 30 2020