组合求和

qianyb

从1-N中取m个数（12，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$的系数即所求