加权植树问题

hujunhua

n 棵树3棵一行的有t₃行，4棵一行的有t₄行，没有更多棵的行。
求行数的加权和\[S(n)=t_3+2t_4\]的最大值。

hujunhua

为什么是`t_3+2t_4`, 而不是`3t_3+4t_4`?

起初是想用`3t_3+4t_4`, 因为有`3t_3+4t_4=\sum d\cdot V_d`, (`V_d`---度为d的点数)，似有一定的图论意义。
但是，一来担心系数3与4差别较小，可能导致最大解全是3树行，没有4树以上行。
二则，同一行的树，应该认为两两有边相连，而不是仅相邻的树关联。
如此，一个 3树行就有3条边, 一个4树行就有6条边，使上述关系式仍然成立。约去公因子3，系数便取成了1和2。

mathe

https://bbs.emath.ac.cn//forum.p ... 0028&fromuid=20
t2≥3+t4
C(n,2)≥t2+3t3+6t4≥3+3t3+7t4, 看来还是应该尽量取3树行

hujunhua

起初并没有想要限制在最多4树行，想的是求 `3t_3+4t_4+\cdots+k\cdot t_k+\cdots+n\cdot t_n`。
但是感觉线性权重系数梯度较缓，不利于多树行，可能结果都是3树行。
改为考察  `3t_3+6t_4+\cdots+C_k^2\cdot t_k+\cdots+C_n^2\cdot t_n`，
又发现权重系数梯度太大，导致 n 树全在一行，结果就是`C_n^2`。
我无法提出一个介于 k 与 C(k,2)之间具有明显图论意义的权重系数，只好限制同行的树数。
2树总有一行，所以3树是基本约束，4树可关联到射影几何的不变量---交比，5树以上我不知道有什么意义
所以，就限制到最多4树行了。
由于C(k,2)是加速增长的，在k较小时加速度小，系数差别可能还是嫌小，不利于4树行。
如果真如 mathe 楼上所说，4树行不给力，那也许放宽到`3t_3+6t_4+10t_5`就能抑制3树行了。
或者，能否提出一个介中的权重系数`a_k`，使得`\sum a_k\cdot t_k`的驻点不走极端？