排列組合公式及恒等式推導(dǎo)、證明word

1、排列組合公式及恒等式推導(dǎo)、證明word版作者:日期:排列組合公式及恒等式推導(dǎo)、證明word版說(shuō)明：因公式編輯需特定的公式編輯插件，不管是word還是pps附帶公式編輯經(jīng)常是出錯(cuò)用不了。下載此 word版的，記得下載 MathType公式編輯器哦，否那么亂碼一堆。如果 想偷懶可下截同名的截圖版。另外，還有PPt課件包含了排列組合的精典解題方法和精典試題供學(xué)友們下載。n!(n - m)!一、排列數(shù)公式:Am 二 n(n -1)( n- 2)L (n - m+1) =A； = n(n -1)(n - 1)L 3創(chuàng)2 1推導(dǎo)：把n個(gè)不同的元素任選m個(gè)排次序或n個(gè)全排序，按計(jì)數(shù)原理分步進(jìn)行：第步，排第位

2、：有 n種選法;第二步，排第二位：有n-1種選法;第三步，排第三位：有n-2種選法;第m步，排第m位：有n-m+1種選法;IIII最后一步，排最后一位：有1種選法。根據(jù)分步乘法原理，得出上述公式。、組合數(shù)公式:m!n!m!(n- m)!m _Am _n(n- 1)(n- 2)L (n- m+1)_ Cn=AT推導(dǎo)：把n個(gè)不同的元素任選m個(gè)不排序，按計(jì)數(shù)原理分步進(jìn)行：第步，取第個(gè)：有n種取法；第二步，取第二個(gè)：有n-1種取法；第三步，取第三個(gè)：11有(n-2)種取法；11第m步，取第m個(gè)：11有(n-m+1)種取法;11最后一步，取最后一個(gè)：有1種取法。上述各步的取法相乘是排序的方法數(shù)，由于選

3、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)題Cnm ；第二步，那么是把這m個(gè)被抽出來(lái)的球全部排序，即全排列 A：。根據(jù)乘法原理,AmmAmnn m即:Cm A? n(n- 1)n_ 2)L (n_ m+1) n!Cn = m =a?m!m!(n- m)!組合公式也適用于全組合的情況，即求 C(n, n)的問(wèn)題。根據(jù)上述公式，C( n,n)二 n!/n!( n-n)

4、!二 n! / n !0! 二 1。這一結(jié)果是完全合理的，因?yàn)閺膎個(gè)球中抽取所有n個(gè)出來(lái)，當(dāng) 然只有1種方法。三、重復(fù)組合數(shù)公式：重復(fù)組合定義:從n個(gè)不同的元素中每次取一個(gè)，放回后再取下 一個(gè)，如此連續(xù)m次所得的組合。重復(fù)組合數(shù)公式：Rnm =cnT+m.i (m可小于、大于、等于n,n 1)推導(dǎo)：可以把該過(guò)程看作是一個(gè)“放球模型：n個(gè)不同的元素看作是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 )!種排

5、法，再由于 m個(gè)小球和(n-1 )塊隔板是分別不 加以區(qū)分的，所以除以重復(fù)的情況：m ! * (n-1 )!于是答案就是：Rnn=(m+n-1)! =Cn：m-1m !(n - 1)!四、不全相異的全排列在不全相異的n個(gè)物體中，假設(shè)有ni個(gè)物體是相同的，n2個(gè)五 題是相同的，nk個(gè)物體是相同的。n個(gè)物體中不相同的物體種 類數(shù)一共有k種。那么，這些物體的全排列數(shù)是 n!/(n 1X2!n!)?？梢韵氤桑簄個(gè)物體直接全排列，排列完了以后，去重，第一 種物體有ni!種，第二種物體有n2!種，以此類推。例：有3個(gè)紅球，2個(gè)白球，把這五個(gè)球排成一行，問(wèn)有多少 種排法？紅球和紅球沒(méi)有區(qū)別，白球和白球沒(méi)有區(qū)

6、別。答：一共有10種，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa。五、排列恒等式的證明：Anm=(n - m + 1) A證明：右邊=(n+ 1)(nn ! m + 1)!n !(n - m )!左邊=右邊nmA n -1n -n !(n - m )!n ? (n - 1) 證明：右邊=n - m (n - m - 1)!左邊=右邊AnmnA證明：右邊二n (n - 1)!= 訃(n - m )!( n - m )!左邊=右邊nAn = A：；An證明：右邊二A：+1- An =(n+1)!- n! = (n +10!

7、- n!二ngi!=nA：右邊=左邊Anm+1Anm+ mA證明：右邊二+m =(n-m+1)n!-嘰(n+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ì)公式：mn- mCn =Cn互補(bǔ)性質(zhì)：取出有多少種，剩下就有多少種分類計(jì)數(shù)原-1C n +1 =C n +C n根據(jù)分類計(jì)數(shù)原

8、理：要么含有新加元素要么不含新加元素Cmnm +1m +1 nn - m +1m-1C n m(m +1)n!m +1m+1Cnn - m證明：n-口+1嚴(yán)1 二n-m+1= n! 二嚴(yán)m(xù)m (m -1)!(n- m+1)!m!(n- m)!=C (n - m)(m+1)!( n-m-1)! m!(n- m)!n!n!C m二n=nC nm 1n - mn- mn(n -1)!g n- m m!(n- m-1)!n!m!(n- m)!CmC m =n_nQm - 1C n - 1m證明：右邊二證明:右邊二(n - 1)!(m - 1)!( n -m )!n !m !( n - m )!=左邊r

9、rrC r +C r+1 +C r+2 + L+ C；r +1 n +1證明：根據(jù)組合性質(zhì)，左邊各式可寫(xiě)成:rn-1=Cr+1n-Cr +1n-1rr+1C n =C n+1-Cr +1 nC；=審C rr+1r+1=Cr+2 -r +1Cr+1C rr+2r+1=C r+3 -r +1_ Cr+2C rr+3r+1= Cr+4 -r +1Cr+3左右兩邊相加即得:Crr +Crr+1+C；+2+L +C； =Cr +1n+1 c n + c n + l證明:用數(shù)學(xué)歸納法證明1) 當(dāng) n=1時(shí)，C10+C11 = 2 = 21所以等式成立。2)假設(shè)n=k時(shí)，(k 1 , k N* )時(shí)等式成立

10、k即：C：+Ck +C：+L +C： =2當(dāng)n=k+1 時(shí)，C 0 +c 1 +c 2 +l +C k +c k+1Ck +1 +C k+1 +Ck+1 +L +C k +1 +Ck+100112k-1 kk +1= Ck+1+(Ck+Ck)+(Ck+Ck)+L +(Ck +Ck )+Ck+1= (C；+C： +C：+L +C) + (Ck+Ck +C+L +Ckk) = 2g2k= 2k+1二等式也成立由1)、2)得，等式對(duì)n N*都成立。也可用二項(xiàng)式定理證明略 c；+c3+c：L =C0+C：+C：L =2n-1證明：用歸納法同上略也可利用上述結(jié)論證明略 本課件盡量避開(kāi)用二項(xiàng)式定理，但這比擬簡(jiǎn)單，暫且用一下:135.a =Cn +Cn +Cn +L b =c n +c n +C：+L由1+1 n可得：a+b=2n=2x 2n-1由1-1 n可得 a-b=0 a=b=2n-1不懂的去學(xué)學(xué)二項(xiàng)式定理 Cn+2C：+3C；+L +nC； =ng2n-1證明：亠m 亠m-1由mCn二nCn-1可得：還記得這個(gè)恒等式嗎，不記得就回過(guò)頭去看的證明左邊=rC0-1 +10 +nCn-1 +nC；-1 +L nC；=n C-1V-1+C-1+C-1+L cn-11)n-1=ng2注：同時(shí)利用了的結(jié)論 cmco+cm-icn+L +cmc：