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,3

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

Links

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

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

Example

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)

Mathematica

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

Prog

(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

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.

Sequence in context: A128129 A014968 A289115 * A126348 A006731 A222036

Adjacent sequences: A342525 A342526 A342527 * A342529 A342530 A342531

Keyword

nonn

Author

Gus Wiseman, Mar 24 2021

Extensions

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

Status

approved