组合求和

qianyb

从1-N中取m个数（1<m<N,N>2，m,N为自然数），然后求m个数的所有组合之积的和(Sum)的公式。
例：N=6，m=2,求Sum的值，Sum=1*2+1*3+1*4+1*5+1*6+2*3+2*4+2*5+2*6+3*4+3*5+3*6+4*5+4*6+5*6

如果有求和公式的话，那么所有组合之积的平方和立方之和又怎么求？

mathe

这些都是对称多项式的问题.
理论上,我们只要得出若干个数前k次幂之和的公式,那么所有次数不超过k次的对称多项式就可以用前面几个数来表示.只是一个计算的问题

qianyb

mathe能帮忙找出这个公式吗？
我还是不明白怎么找这个公式

282842712474

如果m=2，那么结果应该等于
$S_2=\frac{1}{2}[(1+2+3+...+n)^2-1^2-2^2-3^2-...-n^2]=1/2 [\frac{n^2 (n+1)^2}{4}-1/6 n(n+1)(2n+1) ]$
$={n^4}/8+{n^3}/{12}-{n^2}/8-n/{12}$

282842712474

当m=3时，令$1+2+3+...+n=K$
考虑$K^3$的展开式，所有的带有三次方因子的项的系数为1，所有带有2次方因子的项的系数为3，楼主所求的各项的系数为6.于是
$S_3=1/6 [K^3+2(1^3+2^3+...+n^3)-3K(1^2+2^2+...+n^2)]$
$={n^6}/{48}-{n^5}/{48}-{n^4}/{16}+{n^3}/{48}+{n^2}/{24}$

282842712474

接下来的方法应该可以类比吧？
$S_4=1/{24}[K^4+3(1^4+2^4+...+n^4)-4K(1^3+2^3+...+n^3)+6(1^4+2^4+...+n^4)-6K^2(1^2+2^2+...+n^2)]$

规律大概就是
$S_m=1/{m!}[K^m+(C_m^1-1)(1^m+2^m+...+n^m)-C_m^1 K(1^{m-1}+2^{m-1}+...+n^{m-1})+C_m^2(1^m+2^m+...+n^m)-C_m^2 K^2(1^{m-2}+2^{m-2}+...+n^{m-2})+...$
$+C_m^{m-2}(1^m+2^m+...+n^m)-C_m^{m-2} K^{m-2}(1^2+2^2+...+n^2)]$

$S_m=\frac{1}{m!}[K^m+(2^m-m-3)\sum_{i=1}^n i^m-\sum_{i=1}^{m-2}(C_m^i K^i \sum_{j=1}^{n}j^{m-i})]$

qianyb

谢谢282842712474
这个结论看起来还是很复杂，运算量很大的

不知有没有简化此、运算量小一些的公式

282842712474

谢谢282842712474
这个结论看起来还是很复杂，运算量很大的

不知有没有简化此、运算量小一些的公式
qianyb 发表于 2011-1-26 17:27

就目前的结果，可以针对特定的m得出一道多项式。我觉得这已经是最简了，不过具体化简方面我也不了解。

northwolves

然后求m个数的所有组合之积的和(Sum)的公式。
可以构造函数$f(x)=(1+x)(1+2x)(1+3x)...(1+nx)$,$x^m$的系数即所求

northwolves

所有组合之积的平方和怎么求？
可以构造函数$f(x)=(1+x)(1+2^2x)(1+3^2x)...(1+n^2x)$,$x^m$的系数即所求

所有组合之积的立方之和
可以构造函数$f(x)=(1+x)(1+2^3x)(1+3^3x)...(1+n^3x)$,$x^m$的系数即所求