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

0, 0, 1, 1, 5, 11, 25, 55, 117, 241, 493, 1001, 2019, 4061, 8149, 16331, 32705, 65461, 130981, 262037, 524161, 1048425, 2096975, 4194097, 8388365, 16776933, 33554103, 67108481, 134217285, 268434945, 536870321, 1073741145, 2147482869, 4294966401, 8589933569

Offset

0,5

Comments

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

Links

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

Formula

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

Example

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

Mathematica

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

Crossrefs

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

A332834 is the weak version.

A337482 is the semi-strict version.

A337484 counts only compositions of length 3.

A007318 and A097805 count compositions by length.

A032020 counts strict compositions, ranked by A233564.

A218004 counts strictly increasing or weakly decreasing compositions.

Cf. A216652, A329398, A337462, A337483, A337605.

Sequence in context: A167238 A376763 A084640 * A056739 A003598 A014858

Adjacent sequences: A337478 A337479 A337480 * A337482 A337483 A337484

Keyword

nonn

Author

Gus Wiseman, Sep 11 2020

Status

approved