A342528 Number of compositions with alternating parts weakly decreasing (or weakly increasing).

1, 1, 2, 4, 7, 12, 20, 32, 51, 79, 121, 182, 272, 399, 582, 839, 1200, 1700, 2394, 3342, 4640, 6397, 8771, 11955, 16217, 21878, 29386, 39285, 52301, 69334, 91570, 120465, 157929, 206313, 268644, 348674, 451185, 582074, 748830, 960676, 1229208, 1568716, 1997064

Offset: 0

Author

Gus Wiseman, Mar 24 2021

Keywords

• nonn

Comments

These are finite sequences q of positive integers summing to n such that q(i) >= q(i+2) for all possible i.

The strict case (alternating parts are strictly decreasing) is A000041. Is there a bijective proof?

Yes. Construct a Ferrers diagram by placing odd parts horizontally and even parts vertically in a fishbone pattern. The resulting Ferrers diagram will be for an ordinary partition and the process is reversible. It does not appear that this method can be applied to give a formula for this sequence. - Andrew Howroyd, Mar 25 2021

Examples

			The a(1) = 1 through a(6) = 20 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)
                                     (1212)
                                     (1311)
                                     (2121)
                                     (2211)
                                     (3111)
                                     (12111)
                                     (21111)
                                     (111111)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 501 terms from Andrew Howroyd)
• Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

Crossrefs

The even-length case is A114921.

The version with alternating parts unequal is A224958 (unordered: A000726).

The version with alternating parts equal is A342527.

A000041 counts weakly increasing (or weakly decreasing) compositions.

A000203 adds up divisors.

A002843 counts compositions with all adjacent parts x <= 2y.

A003242 counts anti-run compositions.

A069916/A342492 = decreasing/increasing first quotients.

A070211/A325546 = weakly decreasing/increasing differences.

A175342/A325545 = constant/distinct differences.

A342495 = constant first quotients (unordered: A342496, strict: A342515, ranking: A342522).

Cf. A001522, A008965, A048004, A059966, A062968, A064410, A064428, A065608, A167606, A325557, A342519.

Programs

Maple

b:= proc(n, i, j) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1, j)+b(n-i, min(n-i, j), min(n-i, i))))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..42);  # Alois P. Heinz, Jan 16 2025

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],GreaterEqual@@Plus@@@Reverse/@Partition[#,2,1]&]],{n,0,15}]

PARI

seq(n)={my(p=1/prod(k=1, n, 1-y*x^k + O(x*x^n))); Vec(1+sum(k=1, n, polcoef(p,k,y)*(polcoef(p,k-1,y) + polcoef(p,k,y))))} \\ Andrew Howroyd, Mar 24 2021

Formula

G.f.: Sum_{k>=0} ([y^k] P(x,y))*([y^k] (1 + y)*P(x,y)), where P(x,y) = Product_{k>=1} 1/(1 - y*x^k). - Andrew Howroyd, Jan 16 2025

Extensions

Terms a(21) and beyond from Andrew Howroyd, Mar 24 2021