A342343 Number of strict compositions of n with alternating parts strictly decreasing.

1, 1, 1, 3, 3, 5, 8, 10, 13, 18, 27, 32, 44, 55, 73, 97, 121, 151, 194, 240, 299, 384, 465, 576, 706, 869, 1051, 1293, 1572, 1896, 2290, 2761, 3302, 3973, 4732, 5645, 6759, 7995, 9477, 11218, 13258, 15597, 18393, 21565, 25319, 29703, 34701, 40478, 47278, 54985

Offset

0,4

Comments

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

Links

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

Formula

G.f.: Sum_{k>=0} binomial(k,floor(k/2)) * [y^k](Product_{j>=1} 1 + y*x^j). - Andrew Howroyd, Apr 16 2021

Example

The a(1) = 1 through a(8) = 13 compositions:
  (1)  (2)  (3)    (4)    (5)    (6)      (7)      (8)
            (1,2)  (1,3)  (1,4)  (1,5)    (1,6)    (1,7)
            (2,1)  (3,1)  (2,3)  (2,4)    (2,5)    (2,6)
                          (3,2)  (4,2)    (3,4)    (3,5)
                          (4,1)  (5,1)    (4,3)    (5,3)
                                 (2,3,1)  (5,2)    (6,2)
                                 (3,1,2)  (6,1)    (7,1)
                                 (3,2,1)  (2,4,1)  (2,5,1)
                                          (4,1,2)  (3,4,1)
                                          (4,2,1)  (4,1,3)
                                                   (4,3,1)
                                                   (5,1,2)
                                                   (5,2,1)

Mathematica

ici[q_]:=And@@Table[q[[i]]>q[[i+2]], {i, Length[q]-2}];
Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n], UnsameQ@@#&], ici]], {n, 0, 15}]

Prog

(PARI) seq(n)={my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); Vec(sum(k=0, n, binomial(k, k\2) * polcoef(p, k, y)))} \\ Andrew Howroyd, Apr 16 2021

Crossrefs

The non-strict case is A000041 (see A342528 for a bijective proof).

The non-strict odd-length case is A001522.

Strict compositions in general are counted by A032020

The non-strict even-length case is A064428.

The case of reversed partitions is A065033.

A000726 counts partitions with alternating parts unequal.

A003242 counts anti-run compositions.

A027193 counts odd-length compositions.

A034008 counts even-length compositions.

A064391 counts partitions by crank.

A064410 counts partitions of crank 0.

A224958 counts compositions with alternating parts unequal.

A257989 gives the crank of the partition with Heinz number n.

A325548 counts compositions with strictly decreasing differences.

A342194 counts strict compositions with equal differences.

A342527 counts compositions with alternating parts equal.

Cf. A000009, A000670, A008965, A062968, A065608, A109613, A114921, A325546, A332304, A332305, A342532.

Sequence in context: A039868 A015723 A333150 * A116645 A177739 A323581

Adjacent sequences: A342340 A342341 A342342 * A342344 A342345 A342346

Keyword

nonn

Author

Gus Wiseman, Apr 01 2021

Status

approved