組合數(shù)學(xué)課件(第四章二項式系數(shù))

1、目錄（目錄（1）第第1章章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué)1.1引例引例1.2組合數(shù)學(xué)研究對象、內(nèi)容和方法組合數(shù)學(xué)研究對象、內(nèi)容和方法第第2章章 鴿巢原理鴿巢原理2.1 鴿巢原理：簡單形式鴿巢原理：簡單形式2.2 鴿巢原理：加強(qiáng)形式鴿巢原理：加強(qiáng)形式2.3 Ramsey定理定理2.4 鴿巢原理與鴿巢原理與Ramsey定理的應(yīng)用定理的應(yīng)用本章小結(jié) 習(xí)題第第3章章 排列與組合排列與組合3.1 兩個基本的計數(shù)原理兩個基本的計數(shù)原理3.2 集合的排列與組合集合的排列與組合3.3 多重集的排列與組合多重集的排列與組合本章小結(jié) 習(xí)題第四章第四章 二項式系數(shù)二項式系數(shù)4.1 二項式定理二項式定理4.2組合恒等

2、式組合恒等式4.3非降路徑問題非降路徑問題4.4牛頓二項式定理牛頓二項式定理4.5多項式定理多項式定理4.6 基本組合計數(shù)的應(yīng)用基本組合計數(shù)的應(yīng)用本章小結(jié) 習(xí)題第五章第五章 包含排斥原理包含排斥原理5.1 包含排斥原理包含排斥原理5.2 多重集的多重集的r-組合數(shù)組合數(shù)5.3錯位排列錯位排列5.4 有限制條件的排列問題有限制條件的排列問題5.5有禁區(qū)的排列問題有禁區(qū)的排列問題本章小結(jié) 習(xí)題目目 錄錄目錄（目錄（2） 第六章第六章 遞推關(guān)系遞推關(guān)系6.1 Fibonacci數(shù)列6.2 常系數(shù)線性齊次遞推關(guān)系的求解6.3 常系數(shù)線性非齊次遞推關(guān)系的求解6.4 用迭代和歸納法求解遞推關(guān)系本章小結(jié) 習(xí)

3、題第七章第七章 生成函數(shù)生成函數(shù)7.1生成函數(shù)的定義和性質(zhì)7.2多重集的r-組合數(shù)7.3正整數(shù)的劃分7.4指數(shù)生成函數(shù)與多重集的排列問題7.5 Catalan數(shù)和Stiring數(shù)本章小結(jié) 習(xí)題 第八章第八章 Polya定理定理8.1置換群中的共軛類與軌道8.2 Polya定理的特殊形式及其應(yīng)用本章小結(jié) 習(xí)題*課程總結(jié)課程總結(jié)第第4章章 二項式定理二項式定理教學(xué)目標(biāo)：教學(xué)目標(biāo)： 1掌握二項式定理、證明方法及其應(yīng)用；掌握二項式定理、證明方法及其應(yīng)用；2掌握推廣的二項式定理；掌握推廣的二項式定理；3掌握多項式定理、證明方法及其應(yīng)用；掌握多項式定理、證明方法及其應(yīng)用；4理解一些組合恒等式的意義及其證明

4、方法；理解一些組合恒等式的意義及其證明方法；5非降路徑問題的組合意義及應(yīng)用；非降路徑問題的組合意義及應(yīng)用；重點：重點：二項式定理、多項式定理證明方法及其應(yīng)用；二項式定理、多項式定理證明方法及其應(yīng)用；難點：難點：一些組合恒等式證明方法，非降路徑問題組合意一些組合恒等式證明方法，非降路徑問題組合意義及應(yīng)用。義及應(yīng)用。4.1二項式定理1.二項式系數(shù)組合數(shù)C(n,k)或者 也叫二項式系數(shù).2. 組合數(shù)的定義第第4章章 二項式定理二項式定理( )nk.0,)!( !, 0nkknknnkkn3.組合數(shù)的一些恒等式（1）對稱式（2）抽取式（3）Pascal公式4.1 二項式定理二項式定理knnkn(4.1

5、).,11為正整數(shù)knnnknkn(4.2).,111為正整數(shù)knknknkn (4.3)4.2 組合恒等式及其含義抽取式(4.2) knknnkn14.1二項式定理二項式定理 抽取式（抽取式（4.2）：）：如如n,kN，有有C(n,k)=(n/k)C(n-1,k-1)證明：證明：從從n個元素中取個元素中取k個的組合可先從個的組合可先從n個元素中取個元素中取1個，再從個，再從剩下的剩下的n-1個元素中選擇個元素中選擇k-1個，組合數(shù)為個，組合數(shù)為C(n-1,k-1)。選出的。選出的k個個元素都有可能被第一次選中，因是組合，故重復(fù)度為元素都有可能被第一次選中，因是組合，故重復(fù)度為k。得證。得證。

6、或通過計算證明：或通過計算證明： ) )nnnknkkkknn nnknkk knnnnknnkkkkk1, 011,(1).(1)(1).1(1)(2).(1)11(1)(2).1若若若若有有 11knkknkn4.1二項式定理4.1 二項式定理二項式定理定理定理 4.1 )0,()nnkn kknnNx yRxyx yk如如有有證明：證明：因為因為(x+y)n=(x+y)(x+y)(x+y)，等式右端有，等式右端有n個因子，項個因子，項xkyn-k是從這是從這n個因子中選取個因子中選取k個因子，個因子，k=0,1,n。在這。在這k個個(x+y)里都取里都取x，而從剩下的，而從剩下的n-k個

7、因子個因子(x+y)中選取中選取y作乘積得到，因此作乘積得到，因此xkyn-k的系數(shù)為上述選法的個數(shù)的系數(shù)為上述選法的個數(shù)C(n,k)。故有。故有證畢。證畢。注：可用數(shù)學(xué)歸納法證明，證明略；注：可用數(shù)學(xué)歸納法證明，證明略； C(n, k)又稱又稱二項式系數(shù)二項式系數(shù)。 )0()nnkn kknxyx yk4.1二項式定理推論14. 1二項式定理二項式定理四個推論四個推論推論推論4.1.1：推論推論4.1.2：推論推論4.1.3：) )000,()nnkn kknnn kkn kkkknnNx yRxyx ynknnxyxyknk如如有有 )00,(1)nnnkkkknnnNxRxxxknk 如

8、如有有 )0,2nnknnNk如如有有證明：證明：在推論在推論4.1.2中令中令x=1，即可得證。，即可得證。利用組合分析，等式左端相當(dāng)于從利用組合分析，等式左端相當(dāng)于從A=an中任意選擇中任意選擇k(0kn)個個元素的所有可能數(shù)目，即對元素的所有可能數(shù)目，即對n個元素，每一個都有被選擇和不被個元素，每一個都有被選擇和不被選擇的可能，總的可能數(shù)為選擇的可能，總的可能數(shù)為2n。另外，該等式還表明另外，該等式還表明A的所有子集個數(shù)為的所有子集個數(shù)為2n。(4.4) 4.1二項式定理推論24.1 二項式定理二項式定理四個推論四個推論推論推論4.1.1：推論推論4.1.2：推論推論4.1.3：推論推論

9、4.1.4：) )000,()nnkn kknnn kkn kkkknnNx yRxyx ynknnxyxyknk如如有有 )00,(1)nnnkkkknnnNxRxxxknk 如如有有 )0,2nnknnNk如如有有 )0,( 1)0nkknnNk如如有有證明：證明：在推論在推論4.1.2中令中令x=-1，即可得證。，即可得證。另外，該等式還表明另外，該等式還表明A=an的偶數(shù)子集個數(shù)和奇數(shù)子集個數(shù)相等。的偶數(shù)子集個數(shù)和奇數(shù)子集個數(shù)相等。(4.5).3120nnnn(4.5)即即 4.2 組合恒等式及其含義恒等式(4.6) 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(4.6)

10、 ：11,( , )2nnknNkC n kn如如有有證明：證明：考慮盒子考慮盒子1中有中有n個有區(qū)別的球，從中取一個球放入盒子個有區(qū)別的球，從中取一個球放入盒子2中，再取任意多個球放入盒子中，再取任意多個球放入盒子3中。等式左端表示先從盒子中。等式左端表示先從盒子1中中取取k(k=1,2,n)個球，再從中取一個放入盒子個球，再從中取一個放入盒子2中，剩下的中，剩下的k-1個個球放入盒子球放入盒子3中。等式右端表示先從盒子中。等式右端表示先從盒子1中取一個放入盒子中取一個放入盒子2中，中，剩下的剩下的n-1個球是否放入盒子個球是否放入盒子3中均有兩種可能。顯然兩種取法中均有兩種可能。顯然兩種取

11、法結(jié)果是一樣的。得證。結(jié)果是一樣的。得證?；蛲ㄟ^或通過計算計算證明：證明： )111110111111112nnnkkknnkknnnnnkknkkkknnnnkkn11: )2 . 4(nnknkn由式4.2 組合恒等式及其含義恒等式(4.6) 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(4.6) ：11,( , )2nnknNkC n kn如如有有證明：證明：證法證法3 由二項式定理有由二項式定理有對上式兩邊微商得對上式兩邊微商得然后令然后令x=1得得,1)1 (1nkknxknx,)1 (111nkknxknkxn.211nknknkn注：如令注：如令x=- -1，可證明

12、下面，可證明下面恒等式恒等式 。4.2 組合恒等式及其含義恒等式(4.6) 4. 2 組合恒等式及其含義組合恒等式及其含義類（類（4.6）恒等式）恒等式(習(xí)題習(xí)題4.7) ：0,( 1)( , )0nkknNkC n k如如有有證明：證明：將等式兩邊對將等式兩邊對x微分得微分得在上式中，令在上式中，令x=-1得得即即得證。得證。 ) ) ) )01111110(1)(1)( 1)0( 1)0nnkknnkknkknkknxxknnxkxknkknkk4.2組合恒等式及其含義恒等式(4.6) 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(習(xí)題習(xí)題4.8積分方法積分方法)：10121

13、,( , )11nnknNC n kkn如如有有證明：證明：將等式兩邊對將等式兩邊對x從從0到到1積分得積分得即即得證。得證。 ) ) ) )011000111100010(1)(1)(1)1121111nnkknnkknknknnknxxknxdxx dxkxxnknknknk4.2 組合恒等式及其含義恒等式(4.7) 4. 2 組合恒等式及其含義組合恒等式及其含義類恒等式類恒等式(4.7) ：恒等式恒等式(4.7)：120,( 1)( , )0nkknNkC n k如如有有220,( , )(1) 2nnknNkC n kn n如如有有證明：證明：將等式兩邊對將等式兩邊對x微分得微分得將等

14、式兩邊同乘以將等式兩邊同乘以x后再對后再對x微分得微分得在上式中，令在上式中，令x=1得得得證。得證。注：如令注：如令x=-1，即可證明另一，即可證明另一恒等式恒等式(4.7) 。 ) ) ) )011112211221(1)(1)(1)(1) (1)(1)2nnkknnkknnnkknnknxxknnxkxknnxnxxkxknkn nk4.2 組合恒等式及其含義恒等式(4.8) rnrlrnrnrlln 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(4.8)：如如n,l,rN,lr，有有C(n,l)C(l,r)=C(n,r)C(n-r,l-r)證明：證明：等式的左端可看作是先

15、從等式的左端可看作是先從n個元素中取個元素中取l個元素，然后再從個元素，然后再從所得的所得的l個元素中再選擇個元素中再選擇r個元素的方法數(shù)。這種選法與直接從個元素的方法數(shù)。這種選法與直接從n個元素中選取個元素中選取r個元素的選法不同個元素的選法不同. 因為同樣的因為同樣的r個元素可以多次個元素可以多次出現(xiàn)出現(xiàn). 例如例如7元集元集a,b,c,d,e,j,k，從中選，從中選5個元素，比如說個元素，比如說a,b,c,d,e和和a,b,c,j,k，它們都可以選出同樣的，它們都可以選出同樣的3個元素個元素a,b,c，不難看出，不難看出，某某r個元素可以重復(fù)出現(xiàn)的次數(shù)就是包含它們的個元素可以重復(fù)出現(xiàn)的次

16、數(shù)就是包含它們的l元子集的個數(shù)，元子集的個數(shù)，而這種而這種l元子集的其余元子集的其余l(xiāng)-r個元素可以取自個元素可以取自n元集的元集的n-r個元素個元素, 所以所以這種這種l元子集有元子集有 個個 . 綜上所述，通過先選綜上所述，通過先選l個元素然后個元素然后再選再選r個元素的選法應(yīng)該有個元素的選法應(yīng)該有C(n,r)C(n-r,l-r)種。得證。種。得證?；蛲ㄟ^計算證明：或通過計算證明： ) ) )nlnnllrlnlrlrrnllrnnrrnrlrnlnnrrlr!()!()!()!()!()!()!()!()!),(rlrnC恒等式恒等式(4.9)：Vandermonde恒等式，如恒等式，如

17、n,mN且且rmin(m,n)，有，有C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0)4.2 組合恒等式及其含義恒等式(4.9) 4. 2 組合恒等式及其含義組合恒等式及其含義證明：證明：設(shè)設(shè)A=am,B=bn,且且AB=，則則AB=C有有m+n個元素。個元素。C的的r組合個數(shù)為組合個數(shù)為C(m+n,r)，而，而C的每個的每個r組合無非是先從組合無非是先從A中取中取k個元素，再從個元素，再從B中取出中取出r-k個元素組成個元素組成(k=0,1,r)。由乘法法則。由乘法法則共有共有C(m,k)C(n,r-k)種取法，再由加法法則即可得證。種取法，

18、再由加法法則即可得證?；蛲ㄟ^或通過比較系數(shù)法比較系數(shù)法證明：證明：比較等式兩邊比較等式兩邊xr的系數(shù)即可得證。的系數(shù)即可得證。) ) ) )00000(1)(1) (1)m nmnm nmnrijrijm nrrrkxxxmnmnxxxrijmnxkrk 0,(, )( , )(,)mkm nNC m kC n kC mn m如如有有0,( , )( , )(2 , )nknNC n kC n kCn n如如有有4.2 組合恒等式及其含義恒等式(4.10) 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(4.10)：恒等式恒等式(4.10特例特例)：恒等式恒等式(4.9)：Vand

19、ermonde恒等式，如恒等式，如n,mN且且rmin(m,n)，有有C(m+n,r)=C(n,0)C(m,r)+C(n,1)C(m,r-1)+C(n,r)C(m,0)恒等式恒等式(4.10)：).,(),(),(,0nnmCknCkmCNnmnk有如4.2 組合恒等式及其含義恒等式(4.11) 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(4.11)：0,0,( , )(1,1)nin kZn kC i kC nk如如且且有有證明：證明：利用利用組合分析法組合分析法，在集合，在集合A=an+1的的n+1個不同元素選出個不同元素選出k+1個元素的組合可分為以下多種情況：如個元素的

20、組合可分為以下多種情況：如k+1個元素中包含個元素中包含a1，相當(dāng)于從除去相當(dāng)于從除去a1的的n個元素中選出個元素中選出k個元素的組合，組合數(shù)為個元素的組合，組合數(shù)為C(n,k)；如不包含；如不包含a1但包含但包含a2，相當(dāng)于從除去，相當(dāng)于從除去a1,a2的的n-1個元素中個元素中選出選出k個元素的組合，再加上個元素的組合，再加上a2而得到，組合數(shù)為而得到，組合數(shù)為C(n-1,k), ,同同理如不包含理如不包含a1,a2,an-k+1，但包含，但包含an-k+2，相當(dāng)于從剩下的，相當(dāng)于從剩下的k個元個元素中選出素中選出k個元素的組合，再加上個元素的組合，再加上an-k+2而得到，組合數(shù)為而得到

21、，組合數(shù)為C(k,k)；注意，注意，ik時時，C(k,k)=0。由加法法則得。由加法法則得或?qū)潭ǖ幕驅(qū)潭ǖ膋，對，對n使用使用歸納法歸納法，當(dāng)，當(dāng)n=0時，有時，有可見，當(dāng)可見，當(dāng)n=0時，等式成立。時，等式成立。如對任意如對任意n等式成立，則有等式成立，則有可見等式對可見等式對n+1也成立。由歸納原理，得證。也成立。由歸納原理，得證。 ) ) ) ) ) ) ) )0100( , )(1,1)0110100111212ninniiC i kC nkkkkkiinnnnkkkkkk4.2 組合恒等式及其含義恒等式(4.12) 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(4.

22、12)：如如n,rN，有有C(n+r+1,r) = C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)證明證明I：反復(fù)利用反復(fù)利用Pascal公式，即可證明。公式，即可證明?；蚶媒M合分析法，在集合或利用組合分析法，在集合A=an+r+1的的n+r+1個不同元素選出個不同元素選出r個元素的組合可分為以下多種情況：如個元素的組合可分為以下多種情況：如r個元素中不包含個元素中不包含a1，相，相當(dāng)于從除去當(dāng)于從除去a1的的n+r個元素中選出個元素中選出r個元素的組合，組合數(shù)為個元素的組合，組合數(shù)為C(n+r,r)；如；如r個元素中包含個元素中包含a1但不包含但不包含a2，相當(dāng)

23、于從除去，相當(dāng)于從除去a1,a2的的n+r-1個元素中選出個元素中選出r-1個元素的組合，再加上個元素的組合，再加上a1而得到，組合數(shù)而得到，組合數(shù)為為C(n+r-1,r-1), ,同理如同理如r個元素中包含個元素中包含a1,a2,ar-1，但不包含，但不包含ar，相當(dāng)于從剩下的相當(dāng)于從剩下的n+1個元素中選出個元素中選出1個元素的組合，再加上個元素的組合，再加上a1,a2,ar-1而得到，組合數(shù)為而得到，組合數(shù)為C(n+1,1)；如；如r個元素中包含個元素中包含a1,a2,ar，相當(dāng)于從剩下的，相當(dāng)于從剩下的n個元素中選出個元素中選出0個元素的組合，組個元素的組合，組合數(shù)為合數(shù)為C(n,0)

24、 。由加法法則得。由加法法則得C(n+r+1,r)= C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)4.2 組合恒等式及其含義恒等式(4.12) 4. 2 組合恒等式及其含義組合恒等式及其含義恒等式恒等式(4.12) ：如如n,rN，有有C(n+r+1,r) = C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)證明證明II：等式的左端可看作是在集合等式的左端可看作是在集合A=an+2的的n+2個不同元素個不同元素允許重復(fù)允許重復(fù)的選出的選出r個元素的組合，可分為以下多種情況：如個元素的組合，可分為以下多種情況：如r個元個元素中不包含素中不包

25、含a1，相當(dāng)于從除去，相當(dāng)于從除去a1的的n+1個元素中允許重復(fù)的選出個元素中允許重復(fù)的選出r個元素的組合，組合數(shù)為個元素的組合，組合數(shù)為C(n+r,r)；如；如r個元素中只包含一個個元素中只包含一個a1，相當(dāng)于從除去相當(dāng)于從除去a1的的n+1個元素中允許重復(fù)的選出個元素中允許重復(fù)的選出r-1個元素的組合，個元素的組合，再加上再加上a1而得到，組合數(shù)為而得到，組合數(shù)為C(n+r-1,r-1)；如；如r個元素中包含兩個個元素中包含兩個a1，相當(dāng)于從除去，相當(dāng)于從除去a1的的n+1個元素中允許重復(fù)的選出個元素中允許重復(fù)的選出r-2個元素的個元素的組合，再加上兩個組合，再加上兩個a1而得到，組合數(shù)為

26、而得到，組合數(shù)為C(n+r-2,r-2), ,同理如同理如r個元素中包含個元素中包含r個個a1，其組合數(shù)為，其組合數(shù)為C(n,0) 。由加法法則得。由加法法則得C(n+r+1,r)= C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)4.2 組合恒等式證明方法 4. 2 組合恒等式及其含義組合恒等式及其含義常用的證明方法常用的證明方法 數(shù)學(xué)歸納法數(shù)學(xué)歸納法 二項式系數(shù)公式，特別是二項式系數(shù)公式，特別是Pascal 公式公式 比較級數(shù)展開式中的系數(shù)（二項式定理或母函數(shù)法）比較級數(shù)展開式中的系數(shù)（二項式定理或母函數(shù)法） 積分微分法積分微分法 組合分析法組合分析法4.2 組合

27、恒等式及其含義例4.1 4. 2 組合恒等式及其含義組合恒等式及其含義例例4.1 如如n,rN，r n, 有有C(n,r+1) = C(r,r)+C(r+1,r)+C(n-1,r)證明證明1).,()11(1),( )11()22() 11()1()1()(rnC,rnCrnC,rrC,rrC,rrC,rnC,rrCr,rC在上面的等式中，用n+r代替n，得恒等式(4.13) : C(n+r,r+1) = C(r,r)+C(r+1,r)+C(r+n-1,r).在式（4.13）中，如果令r=1，就得到 1+2+3+n=C(n+1,2)=n(n+1)/2.這是等差級數(shù)的求和公式.如果令r=2 ，則

28、有 1+C(3,2)+C(4,2)+C(n+1,2)= C(n+2,3) = n(n+1) (n+2)/6. 在這個等式中每相鄰兩項之差就是等差級數(shù)的項，稱這個等式叫做二階等差級數(shù)求和公式.如果令r=3 ，則有 1+C(4,3)+C(5,3)+C(n+2,3)= C(n+3,4).其中每相鄰兩項之差就是二階等差級數(shù)的項，把這個 等式叫做三階等差級數(shù)的求和公式. 4. 2 組合恒等式及其含義組合恒等式及其含義4.2 組合恒等式及其含義例4.2 4. 2 組合恒等式及其含義組合恒等式及其含義例例4.2 計算計算 12+22+32+n2, 13+23+33+n3.解解 對任何正整數(shù)對任何正整數(shù)k，有

29、，有k2 =2C(k,2)+C(k,1), k3 = 6C(k,3)+6C(k,2)+C(k,1).所以有所以有 12+22+n2 =2C(1,2)+C(2,2) +C(n,2)+C(1,1)+C(2,1)+C(n,1) =2(n+1)n(n-1)/6+(n+1)n/2 = n (n+1) (2n+1)/6. 13+23+n3 = 6C(1,3)+C(2,3) +C(n,3)+6C(1,2)+C(2,2) +C(n,2)+C(1,1)+C(2,1)+C(n,1) =6(n+1,4)+6(n+1,3)+(n+1,2) =2(n+1)n(n-1)/6+(n+1)n/2 = n (n+1)/22.4

30、.2 組合恒等式及其含義例4.3 4. 2 組合恒等式及其含義組合恒等式及其含義例例4.3 證明若證明若p是不等于是不等于2的素數(shù)，則當(dāng)?shù)乃財?shù)，則當(dāng)C(2p,p)被被p除時余數(shù)是除時余數(shù)是2. 證明證明 在恒在恒等式等式(4.10)中中令令m=n=p得得可以證明，如果可以證明，如果p為素數(shù)且為素數(shù)且0kp，則，則p|C(p,k). 因為由組合數(shù)因為由組合數(shù)C(p,k)的計算公式知的計算公式知k!整除整除p(p-1)(p-k+1). 又由于又由于p是素數(shù)且是素數(shù)且k1, 則則k!|(p-1) (p-k+1)；若；若k=1, 也有也有k!|(p-1) (p-k+1). 所以所以C(p,k)是是p的

31、倍數(shù)的倍數(shù). 在等式在等式(4.14)中，中，C(p,1)2+C(p,2)2+C(p,p-1)2一定是一定是p的倍的倍數(shù)，而數(shù)，而C(p,0)2+C(p,p)2 =1+1=2，故當(dāng)，故當(dāng)p2時，時，C(2p,p)除以除以p的的余數(shù)是余數(shù)是2. ),2(),(02mkppCkpC. ),(),(),(0mkmnmCknCkmC(4.14 )例4.4證明： 從n名女同學(xué)和n名男同學(xué)中，選出n名同學(xué)組成一個社團(tuán)，其中一人擔(dān)任社團(tuán)主席，且必須由女同學(xué)擔(dān)任，問有多少種選法？ 112221222nnnnnnnn 4. 2 組合恒等式及其含義組合恒等式及其含義 knnkknknnknkknk1124.3非降

32、路徑問題引非降路徑問題引例 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題引例、引例、非降路徑問題非降路徑問題從從(0,0)點點出發(fā)沿出發(fā)沿X軸或軸或Y軸的正方向每步軸的正方向每步走一個單位，最終走到走一個單位，最終走到(m,n)點，點，有多少條路徑？有多少條路徑？解：解：設(shè)從設(shè)從(0,0)點水平方向向前進(jìn)一步為點水平方向向前進(jìn)一步為x，垂直方向向上進(jìn)一步，垂直方向向上進(jìn)一步為為y。于是從。于是從(0,0)點到點到(m,n)點，水平方向走點，水平方向走m步，垂直方向走步，垂直方向走n步。一條從步。一條從(0,0)點到點到(m,n)點的非降路徑與重集點的非降路徑與重集m*x,n*y的一

33、個的一個全排列全排列一一對應(yīng)，故所求非降路徑數(shù)為一一對應(yīng)，故所求非降路徑數(shù)為(m+n)!/(m!n!)=C(m+n,m)。另外，垂直方向需要走另外，垂直方向需要走n步，相當(dāng)于在步，相當(dāng)于在X軸軸0,1,m共共m+1個端點個端點處處重復(fù)的選擇重復(fù)的選擇n個位置向上走，與一條從個位置向上走，與一條從(0,0)點到點到(m,n)點的非降點的非降路徑一一對應(yīng)，故所求非降路徑數(shù)為路徑一一對應(yīng)，故所求非降路徑數(shù)為F(m+1,n)=C(m+n,n)。Y (m-1,n)(m,n) (m,n-1)(0,0) X 多重集多重集S=*a1, *a2, , *ak 的的r組合數(shù)組合數(shù)F(k,r) = C(k+r-1,

34、 r)4.3 非降路徑問題例2 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題 由引例，我們已經(jīng)知道，從由引例，我們已經(jīng)知道，從(0,0)點到點到(m,n)點的非降路徑數(shù)點的非降路徑數(shù)就是組合數(shù)就是組合數(shù)C(m+n,m), 而且從而且從(0,0)點到點到(m,n)點的非降路徑數(shù)等點的非降路徑數(shù)等于從于從(0,0)點到點到(n,m) 點的非降路徑數(shù)點的非降路徑數(shù),即即C(m+n,m)= C(m+n,n). 另外，一條從另外，一條從(0,0)點到點到(m,n)點的路徑可分為兩類情況，一種點的路徑可分為兩類情況，一種是從是從(0,0)點到點到(m,n-1)點的非降路徑，另一種是從點的非降路

35、徑，另一種是從(0,0)點到點到(m-1,n-1)點的非降路徑，根據(jù)上述結(jié)論，有點的非降路徑，根據(jù)上述結(jié)論，有C(m+n,n)=C(m+n-1,m)+C(m+n-1,m-1)這是這是Pascal公式的另一種形式。公式的另一種形式。例例2、非降路徑問題非降路徑問題從從(0,0)點出點出發(fā)沿發(fā)沿X軸或軸或Y軸的正方向每步走軸的正方向每步走一個單位，最終走到一個單位，最終走到(m,n)點，點，有多少條路徑？有多少條路徑？Y (m-1,n)(m,n) (m,n-1)(0,0) X 4.3 非降路徑問題例3 4.3 非降路徑問題非降路徑問題格路問題格路問題證明：證明：這是上一小節(jié)的組合恒等式。等式左端表

36、示從這是上一小節(jié)的組合恒等式。等式左端表示從(0,0)點到點到(n+1,r)點的非降路徑數(shù)，右端第點的非降路徑數(shù)，右端第1項表示從項表示從(0,0)點到點到(n,r)點的路點的路徑數(shù)，右端第徑數(shù)，右端第2項表示從項表示從(0,0)點到點到(n,r-1)點的非降路徑數(shù)，點的非降路徑數(shù)，右端最后右端最后1項表示從項表示從(0,0)點到點到(n,0)點的非降路徑數(shù)。點的非降路徑數(shù)。這說明從這說明從(0,0)點到點到(n+1,r)點的非降路徑根據(jù)是否經(jīng)過點的非降路徑根據(jù)是否經(jīng)過(n,i)到到(n+1,i)(i= 0,1,r)，可分為，可分為r+1類，根據(jù)加法法則即可得證。類，根據(jù)加法法則即可得證。Y

37、(n,r)(n+1,r) (0,0) (n,0) X 例例3、如如n,rN，有有C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1) +C(n+1,1)+C(n,0) Y P(0,n) P1(1,n-1) X (0,0) Q(n,0)4.3 非降路徑問題例4 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例4、如如nN，有有C(n,0)+C(n,1)+C(n,n)=2n組合含義：組合含義：這是推論這是推論4.1.3。等式左端第。等式左端第1項表示從項表示從(0,0)點到點到P(0,n)點的非降路徑數(shù)，第點的非降路徑數(shù)，第2項表示從項表示從(0,0)點到點到P1(1,n-

38、1)點的非降路徑點的非降路徑數(shù)，數(shù)，左端最后，左端最后1項表示從項表示從(0,0)點到點到Q(n,0)點的非降路徑數(shù)。點的非降路徑數(shù)。這說明從這說明從(0,0)點到點到PQ上各格子點的非降路徑總和為上各格子點的非降路徑總和為2n。也說明。也說明2n個人從個人從(0,0)點出發(fā)，每到一個十字路口便分成兩組，直至到達(dá)點出發(fā)，每到一個十字路口便分成兩組，直至到達(dá)PQ線為止，能保證每個人所走的非降路徑不同。線為止，能保證每個人所走的非降路徑不同。4.3 非降路徑問題例5 4.3非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例5、Vandermonde恒等式恒等式如如n,mN,rmin(m,n)，有

39、，有C(m+n,r)=C(m,0)C(n,r) +C(m,1)C(n,r-1) +C(m,r)C(n,0)證明：證明：等式左端表示從等式左端表示從(0,0)點到點到(m+n-r,r)點的非降路徑數(shù)。從點的非降路徑數(shù)。從(0,0)點到點到(m+n-r,r)點的每一條路徑均穿過點的每一條路徑均穿過PQ線上的格子點線上的格子點(m-l,l),l=0,1,r，從，從(0,0)點到點到(m-l,l)點的非降路徑數(shù)為點的非降路徑數(shù)為C(m,l)，再從，再從(m-l,l)點到點到(m+n-r,r)點的非降路徑數(shù)為點的非降路徑數(shù)為C(n,r-l)，由乘法法則，從，由乘法法則，從(0,0)點出發(fā)經(jīng)過點出發(fā)經(jīng)過(

40、m-l,l)點到點到(m+n-r,r)點的非降路徑數(shù)為點的非降路徑數(shù)為C(m,l)C(n,r-l)，再由加法法則，即可得證。，再由加法法則，即可得證。 Y P(m-r,r) (m+n-r,r) (0,0) Q(m,0) X (m-l,l)4.3 非降路徑問題例6-1 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例6、求從求從(0,0)點到點到(n,n)點點的除端點外不接觸直線的除端點外不接觸直線y=x的非降路徑數(shù)？的非降路徑數(shù)？解：解：先考慮對角線下方的路徑先考慮對角線下方的路徑. 這種路徑都是這種路徑都是從從(0,0)點出發(fā)經(jīng)過點出發(fā)經(jīng)過(1,0)點及點及(n,n-1)點到達(dá)點

41、到達(dá)(n,n)的的. 我們可以把它看作是從我們可以把它看作是從(1,0)點出點出發(fā)到達(dá)發(fā)到達(dá)(n,n-1)點的不接觸對角線的非降路徑點的不接觸對角線的非降路徑. 從從(1,0)點到達(dá)點到達(dá)(n,n-1)點的所有的非降路徑數(shù)是點的所有的非降路徑數(shù)是C(2n-2,n-1),對對其中的任意一條接觸對角線的路徑，我們可以把它從最后離開其中的任意一條接觸對角線的路徑，我們可以把它從最后離開對角線的點（如對角線的點（如A點）到點）到(1,0)點之間的部分關(guān)于對角線作一個反點之間的部分關(guān)于對角線作一個反射，就得到一條從射，就得到一條從(0,1)點出發(fā)經(jīng)過點出發(fā)經(jīng)過A點到達(dá)點到達(dá)(n,n-1)點的非降路徑點的

42、非降路徑. Y (n,n-1) (0,1) (0,0 ) (1,0) Q(n,0) X (n,n)A4.3 非降路徑問題例6-2 反之，任何一條從反之，任何一條從(0,1)點出發(fā)，穿過對角點出發(fā)，穿過對角線而到達(dá)線而到達(dá)(n,n-1)點的非降路徑，也可以通過點的非降路徑，也可以通過這樣的反射對應(yīng)到一條從這樣的反射對應(yīng)到一條從(1,0)點出發(fā)接觸到點出發(fā)接觸到對角線而到達(dá)對角線而到達(dá)(n,n-1)點的非降路徑點的非降路徑. 從從(0,1)點點到達(dá)到達(dá)(n,n-1)點的非降路徑數(shù)是點的非降路徑數(shù)是C(2n-2,n)，從，從而在對角線下方的路徑數(shù)是而在對角線下方的路徑數(shù)是C(2n-2,n-1)-C(

43、2n-2,n). 由對稱性可知，所求的路徑數(shù)是由對稱性可知，所求的路徑數(shù)是 2 C(2n-2,n-1)-C(2n-2,n) =2C(2n-2,n-1)/n =C(2n,n)/(2n-1). 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例6、求從求從(0,0)點到點到(n,n)點的除端點外點的除端點外不接觸直線不接觸直線y=x的非降路徑數(shù)？的非降路徑數(shù)？ 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例6、求從求從(0,0)點到點到(n,n)點的除端點外點的除端點外不穿過直線不穿過直線y=x的非降路徑數(shù)？的非降路徑數(shù)？解：采用分類處理的方法。解：采用分類處理的方法。 將

44、所有從將所有從(0,0)點到點到(n,n)的非降路徑分成兩類：穿過對角線的與的非降路徑分成兩類：穿過對角線的與不穿過對角線的。只要求出穿過對角線的路徑數(shù)不穿過對角線的。只要求出穿過對角線的路徑數(shù)N1，那么從總數(shù)，那么從總數(shù)中減去中減去N1就得到所求的路徑條數(shù)。就得到所求的路徑條數(shù)。 任何一條從任何一條從(0,0)點到點到(n,n)的穿過對角線的路徑一定要接觸直線的穿過對角線的路徑一定要接觸直線y=x+1,有可能接觸多次，但最后離開這條直線上的一點有可能接觸多次，但最后離開這條直線上的一點P，沿直線，沿直線y=x+1下方的一條非降路徑到達(dá)下方的一條非降路徑到達(dá)(n,n)點。把這條路徑的前半段，即

45、點。把這條路徑的前半段，即(0,0)點點到到P點的部分，以直線點的部分，以直線y=x+1為軸進(jìn)行翻轉(zhuǎn)，生成一段新的為軸進(jìn)行翻轉(zhuǎn)，生成一段新的從從(-1,1)點到點到P點的部分非降路徑。用這段新路徑替換原來路徑的點的部分非降路徑。用這段新路徑替換原來路徑的前半段，就得到一條從前半段，就得到一條從(-1,1)點到點到(n,n)點非降路徑點非降路徑.而這種路徑與從而這種路徑與從中間穿過對角線的非降路徑之間是一一對應(yīng)的。因此，從點中間穿過對角線的非降路徑之間是一一對應(yīng)的。因此，從點(0,0)點到點到(n,n)的穿過對角線的非降路徑數(shù)的穿過對角線的非降路徑數(shù)N1=C(2n,n-1)。 從點從點(0,0)

46、點到點到(n,n)的非降路徑總數(shù)為的非降路徑總數(shù)為C(2n,n)條，從而得到條，從而得到不穿過對角線的非降路徑數(shù)是不穿過對角線的非降路徑數(shù)是N=C(2n,n)-C(2n,n-1)=nnn211 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例6、求從求從(0,0)點到點到(n,n)點的除端點外點的除端點外不穿過直線不穿過直線y=x的非降路徑數(shù)？的非降路徑數(shù)？4.3 非降路徑問題例7-1 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例7、求集合求集合1,2, ,n上上的單調(diào)遞增函數(shù)的個數(shù)的單調(diào)遞增函數(shù)的個數(shù).解：解：任給集合任給集合1,2,n上的一個單調(diào)遞增函數(shù)，我上的

47、一個單調(diào)遞增函數(shù)，我們可以作一條對應(yīng)的折線們可以作一條對應(yīng)的折線. 以橫坐標(biāo)代表以橫坐標(biāo)代表x, 縱坐標(biāo)代縱坐標(biāo)代表表f(x), 在圖中可以得到在圖中可以得到n個格點個格點：(1, f(1),(2, f(x),(n, f(n). 從從(1,1)點出發(fā)向上作連線到點出發(fā)向上作連線到(1, f(1)點點. 如果如果f(2)=f(1), 則繼續(xù)向右連線到則繼續(xù)向右連線到(2, f(2); 如果如果f(2)f(1), 則由則由(1, f(1)點向右經(jīng)過點向右經(jīng)過(2, f(1)再向上連線再向上連線到到(2, f(2)點點. 按照這種方法一直將折線連到按照這種方法一直將折線連到(n, f(n)點點. 4

48、.3 非降路徑問題例7-2 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例7、求集合求集合1,2, ,n上上的單調(diào)遞增函數(shù)的個數(shù)的單調(diào)遞增函數(shù)的個數(shù).解：解：若若f(n)=n,就將折線向右連到就將折線向右連到(n+1,n)點，若點，若f(n)n,則向右經(jīng)則向右經(jīng)(n+1, f(n)點再向上到點再向上到(n+1,n)點。這樣就得點。這樣就得到一條從到一條從(1,1)點到點到(n+1,n)點的非降路徑。點的非降路徑。 不難看出，所求的單調(diào)遞增函數(shù)與這種非降路徑不難看出，所求的單調(diào)遞增函數(shù)與這種非降路徑之間存在著一一對應(yīng)，因此集合之間存在著一一對應(yīng)，因此集合1,2,n上的單調(diào)上的單調(diào)函

49、數(shù)有函數(shù)有C(2n-1,n)個個. 4.3 非降路徑問題例8-1 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題例例8、從從(0,0)點到點到(m,n)點點(mn)的，要求中間經(jīng)過的，要求中間經(jīng)過的每一個格子點的每一個格子點(a,b)恒滿足恒滿足ab關(guān)系，問有多少條路關(guān)系，問有多少條路徑？徑？解：解：從從(0,0)點到點到(m,n)點的路徑數(shù)為點的路徑數(shù)為C(m+n,m)，但需要排除碰到，但需要排除碰到或穿過或穿過y=x格子點的路徑數(shù)，即去掉格子點的路徑數(shù)，即去掉ab的情況。第一步必須從的情況。第一步必須從(0,0)點到點到(1,0)點，因此問題等價于求從點，因此問題等價于求從(1,

50、0)點到點到(m,n)點的路徑數(shù)。點的路徑數(shù)。因為因為mn，故從，故從(0,1)點到點到(m,n)點的路徑必然穿過點的路徑必然穿過y=x上的格子點。上的格子點。下面建立從下面建立從(0,1)點到點到(m,n)點的每一條路徑，與從點的每一條路徑，與從(1,0)點到點到(m,n)點但經(jīng)過點但經(jīng)過y=x上的格子點的路徑時一一對應(yīng)的。上的格子點的路徑時一一對應(yīng)的。 Y (m,n) (0,1) (0,0 ) (1,0) Q(m,0) X 4.3 非降路徑問題例8-2 4.3 非降路徑問題非降路徑問題非降路徑問題非降路徑問題 Y (m,n) (0,1) (0,0 ) (1,0) Q(m,0) X 若從若從

51、(0,1)點到點到(m,n)點的路徑與點的路徑與y=x的交點從左往右數(shù)最后一的交點從左往右數(shù)最后一個是個是P，作從，作從(1,0)點到點到P點關(guān)于點關(guān)于y=x的與上述的與上述(0,1)點到點到P點的路徑對點的路徑對稱的一條路徑，于是從稱的一條路徑，于是從(0,1)點到點到(m,n)點的一條路徑，就有一條從點的一條路徑，就有一條從(1,0)點到點到(m,n)點但經(jīng)過點但經(jīng)過y=x上的格子點的路徑與之對應(yīng)。反之，上的格子點的路徑與之對應(yīng)。反之，一條從一條從(1,0)點到點到(m,n)點但經(jīng)過點但經(jīng)過y=x上的格子點的路徑，必存在一上的格子點的路徑，必存在一條從條從(0,1)點到點到(m,n)點的一

52、條路徑與之對應(yīng)。點的一條路徑與之對應(yīng)。 故所求的路徑數(shù)為故所求的路徑數(shù)為C(m+n-1,n)-C(m+n-1,n-1)=(m-n)(m+n-1)!/(m!n!)例例8、從從(0,0)點到點到(m,n)點點(mn)的，要求中間經(jīng)過的，要求中間經(jīng)過的每一個格子點的每一個格子點(a,b)恒滿足恒滿足ab關(guān)系，問有多少條路關(guān)系，問有多少條路徑？徑？4.4牛頓二項式定理4.4 牛頓二項式定理牛頓二項式定理定理定理 4.2定義定義 4.1 )( , ),(1).(1)/!01000CkRkZkkkkkk 廣義廣義二項式系數(shù)二項式系數(shù) 為：為： )kkkR x yxyx yk0,|1,() 如如有有牛頓二項

53、式定理：牛頓二項式定理：4.4 牛頓二項式定理牛頓二項式定理 )0(11為實數(shù)，為整數(shù)，rkkkrkrkr4.4 牛頓二項式定理恒等式牛頓二項式定理恒等式恒等式恒等式(4.15)：恒等式恒等式(4.16)：恒等式恒等式(4.17)：)(111為實數(shù)為整數(shù)，rkkrkrkr ),(為實數(shù)為整數(shù)，rmkkmkrkrkmmr4.4 牛頓二項式定理牛頓二項式定理 4.4 牛頓二項式定理恒等式牛頓二項式定理恒等式恒等式恒等式(4.18)：0,0,(, )(1, )kjR kZkCj jCkk如如且且有有證明：證明：注意，這個恒等式與前面的有一個很不一樣的地方，就注意，這個恒等式與前面的有一個很不一樣的地

54、方，就是是C(+j,j),C(+k+1,k)是廣義的二項式系數(shù)。根據(jù)廣義的二項式是廣義的二項式系數(shù)。根據(jù)廣義的二項式系數(shù)的定義，系數(shù)的定義，Pascal公式公式C(,k)=C(-1,k)+C(-1,k-1)對實數(shù)對實數(shù)和整和整數(shù)數(shù)k同樣成立。與恒等式同樣成立。與恒等式1類似，反復(fù)使用類似，反復(fù)使用Pascal公式即可得證。公式即可得證。4.4 牛頓二項式定理推論14.1 牛頓二項式定理牛頓二項式定理六個推論六個推論推論推論4.2.1：推論推論4.2.2： )kkzzzk0| |1,(1) 有有)nkkknkzzzk01| |1,(1)( 1)有有證明：證明：)0000(1).(1)(1)!(

55、1)(1).(1)!1( 1)nkkkkkkkkkknnnknzzzkkn nnkzknkzk (4.19)(4.19)(4.20)(4.21)(4.22)4.4牛頓二項式定理推論24.1 牛頓二項式定理牛頓二項式定理六個推論六個推論推論推論1.10.1：推論推論1.10.2：推論推論1.10.3：推論推論1.10.4：推論推論1.10.5： )kkzzzk0| |1,(1) 有有)nkkknkzzzk01| |1,(1)( 1)有有kkkzzz10| |1,(1)( 1)有有kkzzz10| |1,(1)有有)kkkkkzzzkk1211( 1)22| |1,1112 有有證明：證明：當(dāng)當(dāng)=

56、1/2時，時，C(,0)=1，而對于，而對于k0，有，有將上式代入推論將上式代入推論4.2.1即可得證。即可得證。 )1112121211 2(1 21).(1 21)!( 1)13. (23)2!( 1)1234. (23)(22)224. (22)!( 1)(22)!2(1)!)( 1)2212kkkkkkkkkkkkkkkkkkkkkkk 4.4 牛頓二項式定理推論34. 1 牛頓二項式定理牛頓二項式定理六個推論六個推論推論推論4.2.1：推論推論4.2.2：推論推論4.2.3：推論推論4.2.4：推論推論4.2.5：推論推論4.2.6： )kkzzzk0| |1,(1) 有有)nkkk

57、nkzzzk01| |1,(1)( 1)有有kkkzzz10| |1,(1)( 1)有有kkzzz10| |1,(1)有有)kkkkkzzzkk1211( 1)22| |1,1112 有有)nkkkrzzr rnkrzr zk0| |1,| |1 | |,01(1)即即是是非非 常常數(shù)數(shù)，有有(4.19)(4.20)(4.21)(4.22)4.5多項式定理 定理4.3（多項式定理）設(shè)n是正整數(shù)，則對一切實數(shù)x1, x2, , xt有)ttntnnnnnntntxxxnnnnxxx2121212121! 4.5 多項式定理多項式定理ttntnnnnnntxxxnnnn21212121多項式定理證

58、明 對于對于n個因子中的每一個，選取個因子中的每一個，選取 m 個數(shù)個數(shù)x1, x2,xt中的一中的一個并形成乘積。個并形成乘積。 用這種方法得到的結(jié)果共有用這種方法得到的結(jié)果共有t n項，并且每一項都可以寫項，并且每一項都可以寫成成 的形式，其中的形式，其中n1,n2,，nt是非負(fù)數(shù)，且其是非負(fù)數(shù)，且其和為和為n。 通過選擇通過選擇n個因子中的個因子中的n1個為個為x1，剩下的，剩下的n-n1個因子中的個因子中的n2個為個為x2,剩下的剩下的n-n1-nt-1個因子中的個因子中的nt個為個為xt,得到得到 項。項。 由乘法原理得到該項出現(xiàn)的次數(shù)為由乘法原理得到該項出現(xiàn)的次數(shù)為tntnnxxx.2121tntnnxxx.2121!.2111211tttnnnnnnnnnnnnn 4.5