login
Number of compositions of n whose non-adjacent parts are weakly decreasing.
5

%I #24 Oct 31 2024 21:53:07

%S 1,1,2,4,7,12,19,30,46,69,102,149,214,304,428,596,823,1127,1532,2068,

%T 2774,3697,4900,6460,8474,11061,14375,18600,23970,30770,39354,50153,

%U 63702,80646,101783,128076,160701,201076,250933,312346,387832,480409,593716,732105,900810,1106063,1355336,1657517,2023207,2464987,2997834,3639464

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

%H Alois P. Heinz, <a href="/A333148/b333148.txt">Table of n, a(n) for n = 0..700</a>

%F See Sage code for the formula. - _Max Alekseyev_, Oct 31 2024

%e The a(1) = 1 through a(6) = 19 compositions:

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

%e (11) (12) (13) (14) (15)

%e (21) (22) (23) (24)

%e (111) (31) (32) (33)

%e (121) (41) (42)

%e (211) (131) (51)

%e (1111) (212) (141)

%e (221) (222)

%e (311) (231)

%e (1211) (312)

%e (2111) (321)

%e (11111) (411)

%e (1311)

%e (2121)

%e (2211)

%e (3111)

%e (12111)

%e (21111)

%e (111111)

%e For example, (2,3,1,2) is such a composition, because the non-adjacent pairs of parts are (2,1), (2,2), (3,2), all of which are weakly decreasing.

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

%o (Sage) def a333148(n): return number_of_partitions(n) + sum( Partitions(m, max_part=l, length=k).cardinality() * Partitions(n-m-l^2, min_length=k+2*l).cardinality() for l in range(1, (n+1).isqrt()) for m in range((n-l^2-2*l)*l//(l+1)+1) for k in range(ceil(m/l), min(m,n-m-l^2-2*l)+1) ) # _Max Alekseyev_, Oct 31 2024

%Y Unimodal compositions are A001523.

%Y The case of normal sequences appears to be A028859.

%Y A version for ordered set partitions is A332872.

%Y The case of strict compositions is A333150.

%Y The version for strictly decreasing parts is A333193.

%Y Standard composition numbers (A066099) of these compositions are A334966.

%Y Cf. A056242, A059204, A072706, A107429, A115981, A329398, A332578, A332669, A332673, A332724, A332834.

%K nonn,changed

%O 0,3

%A _Gus Wiseman_, May 16 2020

%E Edited and terms a(21)-a(51) added by _Max Alekseyev_, Oct 30 2024