排列組合公式及恒等式推導證明

1、名師推薦精心整理學習必備排列組合公式及恒等式推導、證明（word 版）說明：因公式編輯需特定的公式編輯插件，不管是word 還是 pps 附帶公式編輯經(jīng)常是出錯用不了。下載此word 版的，記得下載MathType 公式編輯器哦，否則亂碼一堆。如果想偷懶可下截同名的截圖版。另外，還有PPt 課件（包含了排列組合的精典解題方法和精典試題）供學友們下載。一、排列數(shù)公式：Anm = n(n - 1)(n - 2)(n - m +1) =n!(n - m)!Ann = n (n - 1)(n - 1)3創(chuàng)2 1推導：把 n 個不同的元素任選m個排次序或 n 個全排序，按計數(shù)原理分步進行 ：第一步，排第

2、一位：有n種選法；第二步，排第二位：有（n-1 ） 種選法；第三步，排第三位：有（n-2 ） 種選法；第 m步，排第 m位： 有（n-m+1）種選法；最后一步，排最后一位：有1種選法。根據(jù)分步乘法原理，得出上述公式。二、組合數(shù)公式：m= n(n - 1)(n - 2) (n - m +1) =Cnm = Anmn!Amm!m!(n - m)!C nn = 1名師推薦精心整理學習必備推導：把 n 個不同的元素任選m個不排序，按計數(shù)原理 分步進行 ：第一步，取第一個：有n種取法；第二步，取第二個：有（n-1 ） 種取法；第三步，取第三個：有（n-2 ） 種取法；第 m步，取第 m個：有（n-m+1

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

4、 m)!名師推薦精心整理學習必備組合公式也適用于全組合的情況，即求C(n,n) 的問題。根據(jù)上述公式，C(n,n)=n!/n!(n-n)!=n!/n!0!=1。這一結(jié)果是完全合理的，然只有 1 種方法。因為從n 個球中抽取所有n 個出來，當三、重復組合數(shù)公式：重復組合 定義 : 從 n 個不同的元素中每次取一個，放回后再取下一個，如此連續(xù) m次所得的組合。重復組合數(shù)公式：Rnm =C nm+ m - 1 （m可小于、大于、等于n,n 1）推導： 可以把該過程看作是一個“放球模型”：n 個不同的元素看作是 n 個格子，其間一共有（ n-1 ）塊相同的隔板，用 m 個相同的小球代表取 m 次；則原

5、問題可以簡化為將 m 個不加區(qū)別的小球放進 n 個格子里面，問有多少種放法；這相當于 m 個相同的小球和（ n-1 ）塊相同的隔板先進行全排列：一共有（m+n-1 ）！種排法，再由于 m 個小球和（ n-1 ）塊隔板是分別不加以區(qū)分的，所以除以重復的情況： m ！* （n-1 ）！于是答案就是：R m = ( m + n - 1)! = C mnn +m - 1四、不全相異的全排列名師推薦精心整理學習必備在不全相異的 n 個物體中，假設有 n1 個物體是相同的， n2 個五題是相同的， ， nk 個物體是相同的。 n 個物體中不相同的物體種類數(shù)一共有 k 種。那么，這些物體的全排列數(shù)是 n!/

6、(n 1!n 2! nk!) 。可以想成： n 個物體直接全排列，排列完了以后，去重，第一種物體有 n1! 種，第二種物體有 n2! 種，以此類推。例：有 3 個紅球， 2 個白球，把這五個球排成一行，問有多少種排法？紅球和紅球沒有區(qū)別，白球和白球沒有區(qū)別。答：一共有 10 種，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa 。五、排列恒等式的證明： A nm = ( n - m + 1) A nm - 1n !n !m證明：右邊 = ( n - m + 1)( n - m + 1)!=( n - m )!= A n左邊

7、=右邊A nm=nA nm - 1n- mn?( n - 1)n != A nm證明 ： 右邊 = n - m( n- m - 1)!( n - m )!左邊 =右邊m= nAm - 1A nn - 1證明：右邊 = n( n- 1)!=n != A nm( n -m )!( n - m )!名師推薦精心整理學習必備左邊 =右邊 nAnn = Ann+11 - Ann證明：右邊 = Ann+11 - Ann =(n +1)!- n! = (n +1) n!- n! = n n! = nAnn右邊 =左邊 Anm+1 = A nm + mA nm - 1mmm -n +1An +1= An+=m

8、An= (n - m +1)n!- m n! =證明：右邊n!+mn!(n +1)!= Am(n - m)!(n - m +1)!(n- m +1)!(n - m +1)! 1!+ 2?2! 3?3!+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！=右邊六、組合恒等式的證明首先明弄清組合的兩個性質(zhì)公式：Cnm =C nn - m互補性質(zhì)： 取出有多少種，剩下就有多少種分類計數(shù)原C nm+1 =C nm +C nm - 1根據(jù)分類計數(shù)原理 :要么含有新

9、加元素要么不含新加元素 C nm = m +1 C nm +1 n - m= n - m +1C mm - 1n名師推薦精心整理學習必備m +1m +1(m +1)n !n !mn - mC n =m !( n - m)!= C n(n - m)( m +1)!(n - m - 1)!證明：n - m +1 m - 1n - m +1n !n !mC n =m=m !( n - m )!= C nm(m - 1)!(n - m +1)! Cm=nmn-C n - 1nm證明：右邊 =nCnm-1 =n(n - 1) ! =n ! =Cnmn - mn - m m!(n - m- 1) ! m

10、n!-(m) ! CmnCm- 1n=n -1m證明：n(m -( n - 1 ) !m=n != C nm右邊 = m1 ) ! n(-) ! m -!n(m) !=左邊rrrrr +1C r+ C r +1+ C r + 2+ + C n= C n +1證明：根據(jù)組合性質(zhì)，左邊各式可寫成：名師推薦精心整理學習必備C rr = C rr+11C rr+1 = C rr+21 - C rr +11C rr+2 =C rr+31 - C rr+21C rr+3 =C rr+41 - C rr+31C nr - 1 =C nr +1 - C nr -+11C nr = C nr+11 - C nr

11、 +1左右兩邊相加即得：C rr +Crr+1 +Crr+2 +Cnr =Cnr +11 C n0 + C n1 + C nn= 2 n證明：用數(shù)學歸納法 證明。1）當 n=1 時， C10 +C11 = 2 = 21 所以等式成立。2）假設 n=k 時，（ k1，kN*）時等式成立。即：C k0 +C k1 +C k2 + +C kkk= 2當 n=k+1 時，C k0 +1 +C 1k +1 +C k2+1 +C kk +1 +C kk+11=C k0 +1 + (C k0 +C k1 ) +(C k1 +C k2 ) +(C kk - 1 +C kk ) +C kk +11= (C k0

12、 +C k1 +C k2 +C kk ) + (C k0 +C k1 +C k2 +C kk )= 2 2k= 2k +1等式也成立由 1)、2)得，等式對 nN*都成立。名師推薦精心整理學習必備也可用二項式定理證明（略） Cn1 +Cn3 +Cn5=Cn0 +Cn2 +Cn4= 2n -1證明：用歸納法同上（略）也可利用上述結(jié)論證明（略）本課件盡量避開用二項式定理，但這比較簡單，暫且用一下：135設 a =C n +C n +C n +024b =C n +C n +C n +由（ 1+1）n 可得： a+b=2n=2×2n-1由（ 1-1 ）n 可得 a-b=0a=b=2n-1(不懂的去學學二項式定理) C n1 + 2C n2 + 3C n3 + nC nn = n 2n - 1證明：m m - 1由 mC n = nC n - 1 可得 :（還記得這個恒等式嗎，不記得就回過頭去看的證明）左邊0123n-1=nCn-1 +nCn-1 +nCn-1 +nCn-1 + nCn-1=n 2n-1注：同時利用了的結(jié)論。名師推薦精心整理學習必備 CmrCn0 +Cmr- 1Cn1