A337482 Number of compositions of n that are neither strictly increasing nor weakly decreasing.

0, 0, 0, 0, 2, 7, 18, 45, 101, 219, 461, 957, 1957, 3978, 8036, 16182, 32506, 65202, 130642, 261601, 523598, 1047709, 2096062, 4192946, 8386912, 16775117, 33551832, 67105663, 134213789, 268430636, 536865013, 1073734643, 2147474910, 4294956706, 8589921771

Offset: 0

Author

Gus Wiseman, Sep 11 2020

Keywords

• nonn

Comments

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

Examples

			The a(4) = 2 through a(4) = 18 compositions:
  (112)  (113)   (114)
  (121)  (122)   (132)
         (131)   (141)
         (212)   (213)
         (1112)  (231)
         (1121)  (312)
         (1211)  (1113)
                 (1122)
                 (1131)
                 (1212)
                 (1221)
                 (1311)
                 (2112)
                 (2121)
                 (11112)
                 (11121)
                 (11211)
                 (12111)
		

Crossrefs

Ranked by the complement of the intersection of A114994 and A333255.

A128422 counts only the case of length 3.

A218004 counts the complement.

A332834 is the weak version.

A337481 is the strict version.

A001523 counts unimodal compositions, with complement counted by A115981.

A007318 and A097805 count compositions by length.

A032020 counts strict compositions, ranked by A233564.

A332745/A332835 count partitions/compositions with weakly increasing or weakly decreasing run-lengths.

Cf. A216652, A329398, A332831, A332833, A337462, A337483, A337484, A337605.

Programs

Mathematica

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

Formula

a(n) = 2^(n-1) - A000009(n) - A000041(n) + 1, n > 0.