login
Number of compositions of n that are not strictly increasing.
1

%I #7 Oct 13 2020 14:34:35

%S 0,0,1,2,6,13,28,59,122,248,502,1012,2033,4078,8170,16357,32736,65498,

%T 131026,262090,524224,1048500,2097063,4194200,8388486,16777074,

%U 33554267,67108672,134217506,268435200,536870616,1073741484,2147483258,4294966848,8589934080

%N Number of compositions of n that are not strictly increasing.

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

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

%e (11) (21) (22) (32)

%e (111) (31) (41)

%e (112) (113)

%e (121) (122)

%e (211) (131)

%e (1111) (212)

%e (221)

%e (311)

%e (1112)

%e (1121)

%e (1211)

%e (2111)

%e (11111)

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

%Y A000009 counts the complement.

%Y A047967 is the unordered version.

%Y A056823 is the weak version.

%Y A140106 counts the unordered case of length 3.

%Y A242771 counts the case of length 3.

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

%Y A337481 counts these compositions that are not strictly decreasing.

%Y A337482 counts these compositions that are not weakly decreasing.

%Y A001523 counts unimodal compositions, with complement A115981.

%Y A007318 and A097805 count compositions by length.

%Y A218004 counts strictly increasing or weakly decreasing compositions.

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

%K nonn

%O 0,4

%A _Gus Wiseman_, Oct 06 2020