組合數C(k,n)的定義：從n個不同元素中選取k個進行組合的個數。
基本介紹
- 中文名：組合恆等式
- 類別：公式
- 定義：含有組合數的恆等式
- 公式：C(m,n)=C(n-m,n)
性質,套用,
性質
基本的組合恆等式
kC(k,n)=nC(k-1,n-1)
C(k,n)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(k,n)+C(k,n+1)+……+C(k,n+m)=C(k+1,n+m+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的求和
