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

%I #10 Sep 17 2020 20:32:38

%S 0,0,0,0,2,7,18,45,101,219,461,957,1957,3978,8036,16182,32506,65202,

%T 130642,261601,523598,1047709,2096062,4192946,8386912,16775117,

%U 33551832,67105663,134213789,268430636,536865013,1073734643,2147474910,4294956706,8589921771

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

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

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

%e The a(4) = 2 through a(4) = 18 compositions:

%e (112) (113) (114)

%e (121) (122) (132)

%e (131) (141)

%e (212) (213)

%e (1112) (231)

%e (1121) (312)

%e (1211) (1113)

%e (1122)

%e (1131)

%e (1212)

%e (1221)

%e (1311)

%e (2112)

%e (2121)

%e (11112)

%e (11121)

%e (11211)

%e (12111)

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

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

%Y A128422 counts only the case of length 3.

%Y A218004 counts the complement.

%Y A332834 is the weak version.

%Y A337481 is the strict version.

%Y A001523 counts unimodal compositions, with complement counted by A115981.

%Y A007318 and A097805 count compositions by length.

%Y A032020 counts strict compositions, ranked by A233564.

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

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

%K nonn

%O 0,5

%A _Gus Wiseman_, Sep 11 2020