排列組合公式及恒等式推導(dǎo)、證明(版)教學(xué)文稿

1、此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除排列組合公式及恒等式推導(dǎo)、證明（word 版）說(shuō)明：因公式編輯需特定的公式編輯插件，不管是word 還是 pps 附帶公式編輯經(jīng)常是出錯(cuò)用不了。下載此word 版的，記得下載MathType 公式編輯器哦，否則亂碼一堆。如果想偷懶可下截同名的截圖版。另外，還有PPt 課件（包含了排列組合的精典解題方法和精典試題）供學(xué)友們下載。一、排列數(shù)公式：Anm = n(n - 1)(n - 2)L(n - m +1) =n!(n - m)!n= n(n -1)(n -1)32 1AnL創(chuàng)推導(dǎo)：把 n 個(gè)不同的元素任選m個(gè)排次序或 n 個(gè)全排序，按計(jì)數(shù)原理分步進(jìn)行

2、 ：第一步，排第一位：有n種選法；第二步，排第二位：有（n-1 ） 種選法；第三步，排第三位：有（n-2 ） 種選法；第 m步，排第 m位： 有（n-m+1）種選法；最后一步，排最后一位：有1種選法。根據(jù)分步乘法原理，得出上述公式。二、組合數(shù)公式：m= n(n - 1)(n - 2)L (n - m +1) =Cnm = Anmn!Amm!m!(n - m)!C nn =1只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除推導(dǎo)：把 n 個(gè)不同的元素任選m個(gè)不排序，按計(jì)數(shù)原理 分步進(jìn)行 ：第一步，取第一個(gè)：有n種取法；第二步，取第二個(gè)：有（n-1 ） 種取法；第三步，取第三個(gè)：有（n-2

3、 ） 種取法；第 m步，取第 m個(gè)：有（n-m+1）種取法；最后一步，取最后一個(gè)：有1種取法。上述各步的取法相乘是排序的方法數(shù)，由于選 m個(gè)，就有 m!種排排法，選 n 個(gè)就有 n! 種排法。故取 m個(gè)的取法應(yīng)當(dāng)除以 m!, 取 n 個(gè)的取法應(yīng)當(dāng)除以 n! 。遂得出上述公式。證明：利用排列和組合之間的關(guān)系以及排列的公式來(lái)推導(dǎo)證明。將部分排列問(wèn)題Anm 分解為兩個(gè)步驟：第一步，就是從n 個(gè)球中抽 m個(gè)出來(lái)，先不排序，此即定義的組合數(shù)問(wèn)題 C nm ；第二步，則是把這m個(gè)被抽出來(lái)的球全部排序，即全排列Amm 。根據(jù)乘法原理， Anm = C nm Amm即：m= n(n - 1)(n - 2)L

4、(n - m+1)Cnm = Anm=n!Amm!m!(n - m)!只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除組合公式也適用于全組合的情況，即求C(n,n) 的問(wèn)題。根據(jù)上述公式，C(n,n)=n!/n!(n-n)!=n!/n!0!=1。這一結(jié)果是完全合理的， 因?yàn)閺?n 個(gè)球中抽取所有n 個(gè)出來(lái)，當(dāng)然只有 1 種方法。三、重復(fù)組合數(shù)公式：重復(fù)組合 定義 : 從 n 個(gè)不同的元素中每次取一個(gè)，放回后再取下一個(gè)，如此連續(xù) m次所得的組合。重復(fù)組合數(shù)公式：R nm = C nm+ m- 1（m可小于、大于、等于n,n 1）推導(dǎo)： 可以把該過(guò)程看作是一個(gè)“放球模型”：n 個(gè)不同的元

5、素看作是 n 個(gè)格子，其間一共有（ n-1 ）塊相同的隔板，用 m 個(gè)相同的小球代表取 m 次；則原問(wèn)題可以簡(jiǎn)化為將 m 個(gè)不加區(qū)別的小球放進(jìn) n 個(gè)格子里面，問(wèn)有多少種放法；這相當(dāng)于 m 個(gè)相同的小球和（ n-1 ）塊相同的隔板先進(jìn)行全排列：一共有（m+n-1 ）！種排法，再由于 m 個(gè)小球和（ n-1 ）塊隔板是分別不加以區(qū)分的，所以除以重復(fù)的情況： m ！* （n-1 ）！于是答案就是：R m = ( m + n - 1)! =C mnn +m - 1四、不全相異的全排列只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除在不全相異的 n 個(gè)物體中，假設(shè)有 n1 個(gè)物體是相同的，

6、n2 個(gè)五題是相同的， ， nk 個(gè)物體是相同的。 n 個(gè)物體中不相同的物體種類(lèi)數(shù)一共有 k 種。那么，這些物體的全排列數(shù)是 n!/(n 1!n 2! nk!) ?？梢韵氤桑?n 個(gè)物體直接全排列，排列完了以后，去重，第一種物體有 n1! 種，第二種物體有 n2! 種，以此類(lèi)推。例：有 3 個(gè)紅球， 2 個(gè)白球，把這五個(gè)球排成一行，問(wèn)有多少種排法？紅球和紅球沒(méi)有區(qū)別，白球和白球沒(méi)有區(qū)別。答：一共有 10 種，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa 。五、排列恒等式的證明： A nm = ( n - m + 1) A

7、 nm - 1n !n !m證明：右邊 = ( n - m + 1)( n - m + 1)!=( n - m )!= A n左邊 =右邊 A nm=nmA nm- 1n -證明 ： 右邊 = nn?( n - 1)n != A nm- m( n - m - 1)!( n - m )!左邊 =右邊m= nAm - 1A nn - 1( n- 1)!n !m證明：右邊 = n=( n - m )!= A n( n -m )!只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除左邊 =右邊 nAnn = Ann+11 - Ann證明：右邊 = Ann+11 - Ann = (n +1)!-

8、n! = (n +1)gn!- n! = ngn! = nAnn右邊 =左邊 A nm+1 = A nm + mA nm - 1證明：右邊 =n!+mn!= (n - m +1)n!- mgn! =(n +1)! = Anm+1(n - m)!(n - m +1)!(n- m +1)!(n - m +1)!1!+ 2?2! 3?3! L + n ?n ! (n +1)!- 1證明：左邊 =(2-1)1！+（3-1）2！+（4-1）3!+ （ n+1-1）n!=2!-1!+3!-2!+4!-3!(n+1)!-n!=(n+1)!-1！=右邊六、組合恒等式的證明首先明弄清組合的兩個(gè)性質(zhì)公式：C nm

9、 = C nn - m互補(bǔ)性質(zhì)： 取出有多少種，剩下就有多少種要么含有新C nm+1 =C nm +C nm - 1根據(jù)分類(lèi)計(jì)數(shù)原理 :要么含有新加元素要么不含新加元素 C nm = m +1 C nm +1 = n - m +1C nm - 1n - mm只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除m +1m +1(m +1)n !n !mn - mC n =m !( n - m)!= C n(n - m)( m +1)!(n - m - 1)!證明：n - m +1C nm - 1 = n - m +1gn !=n != C nmmm(m - 1)!(n - m +1)!m

10、!( n - m)!m=nm C n-C n - 1nm證明：右邊 =nCnm-1 =ng(n - 1)!=n!=Cnmn - mn - m m!(n - m- 1)!m!(n - m)! Cm=nCm- 1nmn- 1證明：ng( n- 1)!=mn != Cnm右邊 = m( m - 1)!(n-m )!( n -m )!=左邊rrrrr +1C r+ C r +1+ C r + 2+ L + C n= C n +1證明：根據(jù)組合性質(zhì)，左邊各式可寫(xiě)成：只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除rr +1C r =C r +1rr +1C r +1 =C r +2rr +1C

11、 r +2 = C r +3rr +1C r +3 = C r +4M- C rr +11- C rr+21- C rr+31C nr - 1 = C nr +1 - C nr -+11C nr =C nr +11 - C nr +1左右兩邊相加即得：Crr +Crr+1 +Crr+2 +L +Cnr =Cnr+11 C n0 + C n1 + L+ C nn= 2 n證明：用數(shù)學(xué)歸納法 證明。1）當(dāng) n=1 時(shí)， C 10 +C11= 2 = 21 所以等式成立。2）假設(shè) n=k 時(shí)，（k 1 ， k N* ）時(shí)等式成。立即：C k0 +C k1 +C k2 +L +C kkk= 2當(dāng) n=

12、k+1 時(shí)，012kk +1C k +1+C k +1+C k +1+L +C k +1+C k +100112k - 1kk +1= C k +1+ (C k+C k) + (C k+C k) +L + (C k+C k) +C k +1= (C k0 +C k1 +C k2 +L +C kk ) + (C k0 +C k1 +C k2 +L +C kk )= 2g2k= 2k +1等式也成立由 1) 、2)得，等式對(duì) n N* 都成立。只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除也可用二項(xiàng)式定理證明（略） Cn1 +Cn3 +C n5 L =C n0 +Cn2 +C n4 L

13、 = 2n - 1證明：用歸納法同上（略）也可利用上述結(jié)論證明（略）本課件盡量避開(kāi)用二項(xiàng)式定理，但這比較簡(jiǎn)單，暫且用一下：135設(shè) a =C n +C n +C n +L024b =C n +C n +C n +L由（ 1+1）n 可得： a+b=2n=2×2n-1由（ 1-1 ）n 可得 a-b=0a=b=2n-1(不懂的去學(xué)學(xué)二項(xiàng)式定理) C n1 + 2C n2 + 3C n3 +L+ nC nn = n g2n - 1證明：m m - 1由 mC n = nC n - 1 可得 :（還記得這個(gè)恒等式嗎，不記得就回過(guò)頭去看的證明）左邊=nCn0-1 +nCn1- 1 +nCn2- 1 +nCn3-1 +L nCnn-11=n(Cn0-1 +Cn1-1 +Cn2-1 +Cn3-1 +L Cnn-11)=ng2n-1注：同時(shí)利用了的結(jié)論。只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 CmrCn0 +Cmr- 1C