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.
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 16 2020
STATUS
approved