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

%I #11 Sep 17 2020 20:32:27

%S 0,0,1,1,5,11,25,55,117,241,493,1001,2019,4061,8149,16331,32705,65461,

%T 130981,262037,524161,1048425,2096975,4194097,8388365,16776933,

%U 33554103,67108481,134217285,268434945,536870321,1073741145,2147482869,4294966401,8589933569

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

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

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

%e The a(2) = 1 through a(5) = 11 compositions:

%e (11) (111) (22) (113)

%e (112) (122)

%e (121) (131)

%e (211) (212)

%e (1111) (221)

%e (311)

%e (1112)

%e (1121)

%e (1211)

%e (2111)

%e (11111)

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

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

%Y A332834 is the weak version.

%Y A337482 is the semi-strict version.

%Y A337484 counts only compositions of length 3.

%Y A007318 and A097805 count compositions by length.

%Y A032020 counts strict compositions, ranked by A233564.

%Y A218004 counts strictly increasing or weakly decreasing compositions.

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

%K nonn

%O 0,5

%A _Gus Wiseman_, Sep 11 2020