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

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

Offset: 1

Author

R. J. Mathar, Mar 13 2021

Keywords

• nonn
• tabl

Comments

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.

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.

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

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

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

Examples

			For n=6 and k=3 for example 6 = 2+3+1 = 1+3+2 obtain 2*3+3*1 = 9 = T(6,3).
For n=6 and k=4 for example 6 = 1+2+2+1 obtains 1*2+2*2+2*1=8 =T(6,4).
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).
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).
The triangle starts with n>=1 and 1<=k<=n as:
  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  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  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  36  31  27  23  20  17  15  13  12
  0  49  49  48  42  37  32  28  24  21  18  16  14  13
  0  56  56  55  49  43  38  33  29  25  22  19  17  15  14
		

Crossrefs

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

Programs

Maple

# Maximum of Sum_i  p_i*p(i+1) over all combinations n=p_1+p_2+..p_k
A342472 := proc(n,k)
    local s,c;
    s := 0 ;
    for c in combinat[composition](n,k) do
        add( c[i]*c[i+1],i=1..nops(c)-1) ;
        s := max(s,%) ;
    end do:
    s ;
end proc:
for n from 1 to 15 do
    for k from 1 to n do
        printf("%3d ",A342472(n,k)) ;
    end do:
    printf("\n") ;
end do:

Formula

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

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

T(n,k) >= 2*n-k+((n-k)^2-5)/4, n-k odd, k>=4. - R. J. Mathar, Mar 14 2021

T(n,k) >= n-2+(n-k+2)^2/4, n-k even, k>=4. - R. J. Mathar, Mar 14 2021