A337698 Number of compositions of n that are not strictly increasing.

0, 0, 1, 2, 6, 13, 28, 59, 122, 248, 502, 1012, 2033, 4078, 8170, 16357, 32736, 65498, 131026, 262090, 524224, 1048500, 2097063, 4194200, 8388486, 16777074, 33554267, 67108672, 134217506, 268435200, 536870616, 1073741484, 2147483258, 4294966848, 8589934080

Offset

0,4

Links

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

Formula

a(n) = 2^(n-1) - A000009(n) for n > 0.

Example

The a(2) = 1 through a(5) = 13 compositions:
  (11)  (21)   (22)    (32)
        (111)  (31)    (41)
               (112)   (113)
               (121)   (122)
               (211)   (131)
               (1111)  (212)
                       (221)
                       (311)
                       (1112)
                       (1121)
                       (1211)
                       (2111)
                       (11111)

Mathematica

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

Crossrefs

A000009 counts the complement.

A047967 is the unordered version.

A056823 is the weak version.

A140106 counts the unordered case of length 3.

A242771 counts the case of length 3.

A333255 is the complement of a ranking sequence (using standard compositions A066099) for these compositions.

A337481 counts these compositions that are not strictly decreasing.

A337482 counts these compositions that are not weakly decreasing.

A001523 counts unimodal compositions, with complement A115981.

A007318 and A097805 count compositions by length.

A218004 counts strictly increasing or weakly decreasing compositions.

Cf. A000212, A128422, A332745, A332834, A332835, A337484.

Sequence in context: A182614 A288901 A288831 * A289574 A289525 A289764

Adjacent sequences: A337695 A337696 A337697 * A337699 A337700 A337701

Keyword

nonn

Author

Gus Wiseman, Oct 06 2020

Status

approved