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

1, 1, 2, 3, 5, 7, 11, 15, 21, 29, 40, 53, 71, 93, 122, 158, 204, 260, 332, 419, 528, 661, 825, 1023, 1267, 1560, 1916, 2344, 2860, 3476, 4217, 5097, 6147, 7393, 8872, 10618, 12685, 15115, 17977, 21336, 25276, 29882, 35271, 41551, 48872, 57385, 67277, 78745, 92040

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Example

The a(1) = 1 through a(7) = 15 compositions:
  (1)  (2)   (3)   (4)    (5)    (6)     (7)
       (11)  (12)  (13)   (14)   (15)    (16)
             (21)  (22)   (23)   (24)    (25)
                   (31)   (32)   (33)    (34)
                   (211)  (41)   (42)    (43)
                          (221)  (51)    (52)
                          (311)  (231)   (61)
                                 (312)   (241)
                                 (321)   (322)
                                 (411)   (331)
                                 (2211)  (412)
                                         (421)
                                         (511)
                                         (2311)
                                         (3211)
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.

Mathematica

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

Prog

(PARI) \\ p is all, q is those ending in an unreversed singleton.
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

Crossrefs

A version for ordered set partitions is A332872.

The case of strict compositions is A333150.

The case of normal sequences appears to be A001045.

Unimodal compositions are A001523, with strict case A072706.

Strict compositions are A032020.

Partitions with strictly increasing run-lengths are A100471.

Partitions with strictly decreasing run-lengths are A100881.

Compositions with weakly decreasing non-adjacent parts are A333148.

Compositions with strictly increasing run-lengths are A333192.

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

Sequence in context: A035977 A288256 A101049 * A035986 A035996 A261775

Adjacent sequences: A333190 A333191 A333192 * A333194 A333195 A333196

Keyword

nonn

Author

Gus Wiseman, May 18 2020

Extensions

Terms a(21) and beyond from Andrew Howroyd, Apr 17 2021

Status

approved