组合数C(k,n)的定义：从n个不同元素中选取k个进行组合的个数。

组合恒等式的定义：含有组合数的恒等式。

基本的组合恒等式

C(m,n)=C(n-m,n)

kC(k,n)=nC(k-1,n-1)

C(n,k)C(m,k)=C(m,n)C(k-m,n-m)

∑C(i,n)=2^n

∑[(-1)^i]*C(i,n)=0

C(m,n+1)=C(m-1,n)+C(m,n)（这个性质叫组合的【聚合性】）

C(e,n)+C(e,n+1)+……+C(e,n+k)=C(e+1,n+k+1)

C(0,n)C(p,m)+C(1,n)C(p-1,m)+C(2,n)C(p-2,m)＋……＋C(p-1,n)C(1,m)+C(p,n)C(0,m)=C(p,m+n)

组合恒等式的应用

(一)多项式的求和

例一

∑i^2

=∑i(i-1)+∑i

=2∑C(2,i)+∑C(1,i)

=2C(3,n+1)+C(2,n+1)

=(n+1)n(n-1)/3+(n+1)n/2

=(1/6)n(n+1)(2n+1)

例二

∑i^3

=∑(i+1)i(i-1)+∑i

=6∑C(3,i+1)+∑C(1,i)

=6C(4,n+2)+C(2,n+1)

=(n+2)(n+1)n(n-1)/4+(n+1)n/2

=[n(n+1)/2]^2

例三

∑i^4＝∑(i+1)i(i-1)i+∑i^2

=∑(i+1)i(i-1)(i-2)+∑i^2+2∑(i+1)i(i-1)

=∑(i+1)i(i-1)(i-2)+∑i(i-1)+∑i+2∑(i+1)i(i-1)

=24∑C(4,i+1)+12∑C(3,i+1)+∑C(1,i)+2∑C(2,i)

=24C(5,n+2)+12C(4,n+2)+C(2,n+1)+2C(3,n+1)

=n(n+1)(2n+1)(3n^2+3n-1)/30

一般地，我们有i^n=i!+(n-1)A(n-1,i)+(n-2)A(n-2,i)+...+1*A(1,i)

设i(max)=m

从而∑i^n=∑i!+(n-1)∑A(n-1,i)+...+∑A(1,i)

=∑C(n,i)/n!+∑C(n-1,i)/(n-2)!...+∑C(1,i)/0!

=C(n+1,m+1)/(n+1)!+C(n,m+1)/(n-1)!+...+C(2,m+1)/0!

该式展开后可用于i<n+1时的级数求和，不展开只可用于i>=n+1的求和