login
Number of compositions of n whose non-adjacent parts are strictly decreasing.
5

%I #12 Apr 17 2021 14:10:48

%S 1,1,2,3,5,7,11,15,21,29,40,53,71,93,122,158,204,260,332,419,528,661,

%T 825,1023,1267,1560,1916,2344,2860,3476,4217,5097,6147,7393,8872,

%U 10618,12685,15115,17977,21336,25276,29882,35271,41551,48872,57385,67277,78745,92040

%N Number of compositions of n whose non-adjacent parts are strictly decreasing.

%H Andrew Howroyd, <a href="/A333193/b333193.txt">Table of n, a(n) for n = 0..1000</a>

%e The a(1) = 1 through a(7) = 15 compositions:

%e (1) (2) (3) (4) (5) (6) (7)

%e (11) (12) (13) (14) (15) (16)

%e (21) (22) (23) (24) (25)

%e (31) (32) (33) (34)

%e (211) (41) (42) (43)

%e (221) (51) (52)

%e (311) (231) (61)

%e (312) (241)

%e (321) (322)

%e (411) (331)

%e (2211) (412)

%e (421)

%e (511)

%e (2311)

%e (3211)

%e For example, (2,3,1,2) is not such a composition, because the non-adjacent pairs of parts are (2,1), (2,2), (3,2), not all of which are strictly decreasing, while (2,4,1,1) is such a composition, because the non-adjacent pairs of parts are (2,1), (2,1), (4,1), all of which are strictly decreasing.

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{___,x_,__,y_,___}/;y>=x]&]],{n,0,15}]

%o (PARI) \\ p is all, q is those ending in an unreversed singleton.

%o seq(n)={my(q=O(x*x^n), p=1+q); for(k=1, n, [p,q] = [p*(1 + x^k + x^(2*k)) + q*x^k, q + p*x^k] ); Vec(p)} \\ _Andrew Howroyd_, Apr 17 2021

%Y A version for ordered set partitions is A332872.

%Y The case of strict compositions is A333150.

%Y The case of normal sequences appears to be A001045.

%Y Unimodal compositions are A001523, with strict case A072706.

%Y Strict compositions are A032020.

%Y Partitions with strictly increasing run-lengths are A100471.

%Y Partitions with strictly decreasing run-lengths are A100881.

%Y Compositions with weakly decreasing non-adjacent parts are A333148.

%Y Compositions with strictly increasing run-lengths are A333192.

%Y Cf. A059204, A072707, A115981, A227038, A332834, A332836, A333191, A334966.

%K nonn

%O 0,3

%A _Gus Wiseman_, May 18 2020

%E Terms a(21) and beyond from _Andrew Howroyd_, Apr 17 2021