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,6

Comments

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

Also compositions whose run-lengths are not weakly decreasing.

Links

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

Formula

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

Example

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).

Mathematica

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

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.

Sequence in context: A319721 A115641 A153334 * A116719 A159612 A099176

Adjacent sequences: A332868 A332869 A332870 * A332872 A332873 A332874

Keyword

nonn

Author

Gus Wiseman, Feb 29 2020

Extensions

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

Status

approved