A333148 Number of compositions of n whose non-adjacent parts are weakly decreasing.

1, 1, 2, 4, 7, 12, 19, 30, 46, 69, 102, 149, 214, 304, 428, 596, 823, 1127, 1532, 2068, 2774, 3697, 4900, 6460, 8474, 11061, 14375, 18600, 23970, 30770, 39354, 50153, 63702, 80646, 101783, 128076, 160701, 201076, 250933, 312346, 387832, 480409, 593716, 732105, 900810, 1106063, 1355336, 1657517, 2023207, 2464987, 2997834, 3639464

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..700

Formula

See Sage code for the formula. - Max Alekseyev, Oct 31 2024

Example

The a(1) = 1 through a(6) = 19 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (13)    (14)     (15)
             (21)   (22)    (23)     (24)
             (111)  (31)    (32)     (33)
                    (121)   (41)     (42)
                    (211)   (131)    (51)
                    (1111)  (212)    (141)
                            (221)    (222)
                            (311)    (231)
                            (1211)   (312)
                            (2111)   (321)
                            (11111)  (411)
                                     (1311)
                                     (2121)
                                     (2211)
                                     (3111)
                                     (12111)
                                     (21111)
                                     (111111)
For example, (2,3,1,2) is such a composition, because the non-adjacent pairs of parts are (2,1), (2,2), (3,2), all of which are weakly decreasing.

Mathematica

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

Prog

(Sage) def a333148(n): return number_of_partitions(n) + sum( Partitions(m, max_part=l, length=k).cardinality() * Partitions(n-m-l^2, min_length=k+2*l).cardinality() for l in range(1, (n+1).isqrt()) for m in range((n-l^2-2*l)*l//(l+1)+1) for k in range(ceil(m/l), min(m, n-m-l^2-2*l)+1) ) # Max Alekseyev, Oct 31 2024

Crossrefs

Unimodal compositions are A001523.

The case of normal sequences appears to be A028859.

A version for ordered set partitions is A332872.

The case of strict compositions is A333150.

The version for strictly decreasing parts is A333193.

Standard composition numbers (A066099) of these compositions are A334966.

Cf. A056242, A059204, A072706, A107429, A115981, A329398, A332578, A332669, A332673, A332724, A332834.

Sequence in context: A264392 A100823 A102346 * A343661 A342229 A326080

Adjacent sequences: A333145 A333146 A333147 * A333149 A333150 A333151

Keyword

nonn

Author

Gus Wiseman, May 16 2020

Extensions

Edited and terms a(21)-a(51) added by Max Alekseyev, Oct 30 2024

Status

approved