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

%I #11 Apr 17 2021 03:42:16

%S 1,1,1,3,3,5,8,10,13,18,26,31,42,52,68,89,110,136,173,212,262,330,398,

%T 487,592,720,864,1050,1262,1508,1804,2152,2550,3037,3584,4236,5011,

%U 5880,6901,8095,9472,11048,12899,14996,17436,20261,23460,27128,31385,36189

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

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

%H Andrew Howroyd, <a href="/A333150/b333150.txt">Table of n, a(n) for n = 0..1000</a>

%F G.f.: Sum_{k>=0} Fibonacci(k+1) * [y^k](Product_{j>=1} 1 + y*x^j). - _Andrew Howroyd_, Apr 16 2021

%e The a(1) = 1 through a(8) = 13 compositions:

%e (1) (2) (3) (4) (5) (6) (7) (8)

%e (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)

%e (2,1) (3,1) (2,3) (2,4) (2,5) (2,6)

%e (3,2) (4,2) (3,4) (3,5)

%e (4,1) (5,1) (4,3) (5,3)

%e (2,3,1) (5,2) (6,2)

%e (3,1,2) (6,1) (7,1)

%e (3,2,1) (2,4,1) (2,5,1)

%e (4,1,2) (3,4,1)

%e (4,2,1) (4,1,3)

%e (4,3,1)

%e (5,1,2)

%e (5,2,1)

%e 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.

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

%o (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

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

%Y Unimodal strict compositions are A072706.

%Y A version for ordered set partitions is A332872.

%Y The non-strict version is A333148.

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

%K nonn

%O 0,4

%A _Gus Wiseman_, May 16 2020