login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

T(n,k) is the maximum sum of products of adjacent parts in all compositions of n into k parts: triangle read by rows.
2

%I #7 Mar 14 2021 07:24:41

%S 0,0,1,0,2,2,0,4,4,3,0,6,6,5,4,0,9,9,8,6,5,0,12,12,11,9,7,6,0,16,16,

%T 15,12,10,8,7,0,20,20,19,16,13,11,9,8,0,25,25,24,20,17,14,12,10,9,0,

%U 30,30,29,25,21,18,15,13,11,10,0,36,36,35,30,26,22,19,16,14,12,11,0,42,42,41

%N T(n,k) is the maximum sum of products of adjacent parts in all compositions of n into k parts: triangle read by rows.

%C Denote compositions of n into k parts by n = p_1 +p_2 + .... +p_k, p_i>0. For these compositions let S(n,k,c) = p_1*p_2 +p_2*p_3 +.. +p_{k-1}*p_k. Then T(n,k) = max_c S(n,k,c), where c runs through all A007318(n-1,k-1) compositions.

%C Background: Let p_i be the number of elements in level i of a poset of n points. Connect all points on level i with all points on level i+1 "maximally" with p_i*p_{i+1} arcs in the Hasse diagram. So T(n,k) is a lower bound on the maximum number of arcs in a Hasse diagram with k levels, and the maximum T(n,k) (+1 to add the diagrams of n disconnected elements) of a row is a lower bound of the row lengths of A342447.

%C T(n,2)= A002620(n) has the standard interpretation of maximizing the area p_1*p_2 of a rectangle given the semiperimeter p_1+p_2=n. [S=p_1*p_2=p_1*(n-p_1) is a quadratic function of p_1 with well defined maximum.] - _R. J. Mathar_, Mar 14 2021

%C T(n,3) maximizes S = +p_1*p_2+p_2*p_3 = p_1*p_2+p_2*(n-p_1-p_2) = p_2*(n-p_2) which again is a quadratic function of p_2 with well defined maximum.] - _R. J. Mathar_, Mar 14 2021

%C For k>=4 and odd n-k consider p_1=1, p_2=(n-k+1)/2, p_3=p_2+1, p_4=p_5=..=p_k=1 which gives S= n+(n-k)+[(n-k)^2-5]/4, a lower bound (apparently strict). For k>=4 and even n-k consider p_1=1, p_2=p_3=(n-k+2)/2, p_4=p_5=...=p_k=1 which gives S=n-2+(n-k+2)^2/4, a lower bound (apparently strict). - _R. J. Mathar_, Mar 14 2021

%F T(n,n) = n-1; where all p_i=1.

%F T(n,2) = T(n,3) = A002620(n).

%F T(n,k) >= 2*n-k+((n-k)^2-5)/4, n-k odd, k>=4. - _R. J. Mathar_, Mar 14 2021

%F T(n,k) >= n-2+(n-k+2)^2/4, n-k even, k>=4. - _R. J. Mathar_, Mar 14 2021

%e For n=6 and k=3 for example 6 = 2+3+1 = 1+3+2 obtain 2*3+3*1 = 9 = T(6,3).

%e For n=6 and k=4 for example 6 = 1+2+2+1 obtains 1*2+2*2+2*1=8 =T(6,4).

%e For n=7 and k=4 for example 7 = 1+3+2+1 = 1+2+3+1 obtains 1*2+2*3+3*1 = 11 = T(7,4).

%e For n=7 and k=5 for example 7 = 1+1+2+2+1 = 1+2+2+1+1 obtains 1*2+2*2+2*1+1*1 = 9 = T(7,5).

%e The triangle starts with n>=1 and 1<=k<=n as:

%e 0

%e 0 1

%e 0 2 2

%e 0 4 4 3

%e 0 6 6 5 4

%e 0 9 9 8 6 5

%e 0 12 12 11 9 7 6

%e 0 16 16 15 12 10 8 7

%e 0 20 20 19 16 13 11 9 8

%e 0 25 25 24 20 17 14 12 10 9

%e 0 30 30 29 25 21 18 15 13 11 10

%e 0 36 36 35 30 26 22 19 16 14 12 11

%e 0 42 42 41 36 31 27 23 20 17 15 13 12

%e 0 49 49 48 42 37 32 28 24 21 18 16 14 13

%e 0 56 56 55 49 43 38 33 29 25 22 19 17 15 14

%p # Maximum of Sum_i p_i*p(i+1) over all combinations n=p_1+p_2+..p_k

%p A342472 := proc(n,k)

%p local s,c;

%p s := 0 ;

%p for c in combinat[composition](n,k) do

%p add( c[i]*c[i+1],i=1..nops(c)-1) ;

%p s := max(s,%) ;

%p end do:

%p s ;

%p end proc:

%p for n from 1 to 15 do

%p for k from 1 to n do

%p printf("%3d ",A342472(n,k)) ;

%p end do:

%p printf("\n") ;

%p end do:

%Y Cf. A002620 (columns 2,3,5 ?), A024206 (column 4?), A033638 (column 6?), A290743 (column 7?), A342447.

%K nonn,tabl

%O 1,5

%A _R. J. Mathar_, Mar 13 2021