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

Author

Gus Wiseman, May 16 2020

Keywords

• nonn

Examples

			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.
		

Links

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

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.

Programs

Mathematica

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

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

Formula

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

Extensions

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