A333150 Number of strict compositions of n whose non-adjacent parts are strictly decreasing.

1, 1, 1, 3, 3, 5, 8, 10, 13, 18, 26, 31, 42, 52, 68, 89, 110, 136, 173, 212, 262, 330, 398, 487, 592, 720, 864, 1050, 1262, 1508, 1804, 2152, 2550, 3037, 3584, 4236, 5011, 5880, 6901, 8095, 9472, 11048, 12899, 14996, 17436, 20261, 23460, 27128, 31385, 36189

Offset

0,4

Comments

A composition of n is a finite sequence of positive integers summing to n. It is strict if there are no repeated parts.

Links

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

Formula

G.f.: Sum_{k>=0} Fibonacci(k+1) * [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)
For example, (3,5,1,2) is such a composition, because the non-adjacent pairs of parts are (3,1), (3,2), (5,2), all of which are strictly decreasing.

Mathematica

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

Prog

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

Crossrefs

The case of permutations appears to be A000045(n + 1).

Unimodal strict compositions are A072706.

A version for ordered set partitions is A332872.

The non-strict version is A333148.

Cf. A001523, A028859, A056242, A059204, A107429, A115981, A329398, A332578, A332669, A332673, A332724, A332834, A333193.

Sequence in context: A123632 A039868 A015723 * A342343 A116645 A177739

Adjacent sequences: A333147 A333148 A333149 * A333151 A333152 A333153

Keyword

nonn

Author

Gus Wiseman, May 16 2020

Status

approved