組合恆等式

組合恆等式就是含有組合數的恆等式,組合數的兩個性質:Cn^m=Cn^n-m和Cn+1^m=Cn^m+Cn^m-1

組合數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的求和

相關搜尋

熱門詞條

聯絡我們