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