|
| |
|
|
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.
|
|
2
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,n) = n-1; where all p_i=1.
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
|
|
|
EXAMPLE
|
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
|
|
|
MAPLE
|
# Maximum of Sum_i p_i*p(i+1) over all combinations n=p_1+p_2+..p_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
end do:
printf("\n") ;
end do:
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
