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

排列組合公式及恒等式推導(dǎo)、證明（word版）說明：因公式編輯需特定的公式編輯插件，不管是word還是pps附帶公式編輯經(jīng)常是出錯(cuò)用不了。下載此word版的，記得下載MathType公式編輯器哦，否則亂碼一堆。如果想偷懶可下截同名的截圖版。另外，還有PPt課件（包含了排列組合的精典解題方法和精典試題）供學(xué)友們下載。、排列數(shù)公式:n!Am=n(n-1)(n-2)L(n-m+1)=.n(n-m)!An=n（n-1）（n-1）L3創(chuàng)21n推導(dǎo)：把n個(gè)不同的元素任選m個(gè)排次序或n個(gè)全排序，按計(jì)數(shù)原理分步進(jìn)行第一步，排第一位:第二步，排第二位:第三步，排第三位:■■第一步，排第一位:第二步，排第二位:第三步，排第三位:■■■I第m步，排第m位:有n種選法；有（n-1）種選法；有（n-2）種選法；有（n-m+1）種選法;根據(jù)分步乘法原理，得出上述公式。八組合數(shù)公式:C_Am_n(n-1)(n-2)L(n-m+1=n!mAmm!m!(n-mHmCn=1推導(dǎo)：把n個(gè)不同的元素任選m個(gè)不排序，按計(jì)數(shù)原理分步進(jìn)行:第一步，取第一個(gè)：有n種取法；第二步，取第二個(gè)：有(n-1)種取法；第三步，取第三個(gè)：有(n-2)種取法；■■■I第m步，取第m個(gè)：有(n-m+1)種取法；■■■I最后一步，取最后一個(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)系以及排列的公式來推導(dǎo)證明。將部分排列問題Am分解為兩個(gè)步驟：n第一步，就是從n個(gè)球中抽m個(gè)出來，先不排序，此即定義的組合數(shù)問題C；mn第二步，則是把這m個(gè)被抽出來的球全部排序，即全排列Am。m根據(jù)乘法原理，Am=CmAm即：nnmAmn(n-1)n-2)L(n-m+Dn!c==nAmm!m!(n-m)!m

組合公式也適用于全組合的情況，即求C(n,n)的問題。根據(jù)上述公式，C(n,n)=n!/n!(n-n)!=n!/n!0!=1。這一結(jié)果是完全合理的，因?yàn)閺膎個(gè)球中抽取所有n個(gè)出來，當(dāng)然只有1種方法。三、重復(fù)組合數(shù)公式：重復(fù)組合定義:從n個(gè)不同的元素中每次取一個(gè)，放回后再取下一個(gè)，如此連續(xù)m次所得的組合。重復(fù)組合數(shù)公式：Rm=Cm(m可小于、大于、等于n,nN1)nn+m-1推導(dǎo)：可以把該過程看作是一個(gè)“放球模型”：n個(gè)不同的元素看作是n個(gè)格子，其間一共有(n-1)塊相同的隔板，用m個(gè)相同的小球代表取m次；則原問題可以簡(jiǎn)化為將n個(gè)不加區(qū)別的小球放進(jìn)n個(gè)格子里面，問有多少種放法；這相當(dāng)于m個(gè)相同的小球和(n-1)塊相同的隔板先進(jìn)行全排列：一共有(m+n-1)!種排法，再由于m個(gè)小球和(n-1)塊隔板是分別不加以區(qū)分的，所以除以重復(fù)的情況：m!*(n-1)!于是答案就是:Rm(m于是答案就是:Rm(m+n-1)!

m!(n-1)!二Cmn+m-1四、不全相異的全排列在不全相異的n個(gè)物體中，假設(shè)有n個(gè)物體是相同的，n個(gè)五TOC\o"1-5"\h\z12題是相同的，……，n個(gè)物體是相同的。n個(gè)物體中不相同的物體種k類數(shù)一共有k種。那么，這些物體的全排列數(shù)是n!/(n!n!???n!)。12k可以想成：n個(gè)物體直接全排列，排列完了以后，去重，第一種物體有n!種，第二種物體有n!種，以此類推。12例：有3個(gè)紅球，2個(gè)白球，把這五個(gè)球排成一行，問有多少種排法？紅球和紅球沒有區(qū)別，白球和白球沒有區(qū)別。答：一共有10種，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa。五、排列恒等式的證明：①Am=(n-m+1)Am.in+1)(n-m+1)!(n-m)!證明：右邊=(n-m左邊二右邊n證明：右邊-n-m(n-1)(n-m-1)!n!(n-m)!=Am

n左邊二右邊③Am+1)(n-m+1)!(n-m)!n證明：右邊-n-m(n-1)(n-m-1)!n!(n-m)!=Am

n左邊二右邊nAn=An+i-Annn+n1證明：右邊二An+i-An=(n+1)!n!=(n+1)gn-n!=ngn=nAn+lnn右邊=左邊IAm=Am+mAm-in+1nn證明：右邊二n!n!_(n-m+1)n!-mgh(n+1)!_+111=_=^A.(n-m)!(n-m+1)!(n-m+1)!~(n-m+1)!n+11!+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ì)公式:類計(jì)數(shù)原理互補(bǔ)性質(zhì)：取出有多:類計(jì)數(shù)原理根據(jù)分類計(jì)數(shù)原理:m+1(m+1)n!n!n-mrm+1=(n-m)(m+1)!(n-m-1)=m!(n-1孔!=』^"證明：n-m+1—m—m-1nn-m+1n!n!—m—*m-1)!(n-m+1)=m!(n-m)!=牛證明：右邊二③ncn(n-1)!n!n-mm1=nmBr!(nm1)=m!(nm)=C證明：n(n-1)!n!_g,、，=—、，=Cm右邊二m*m——1)!(n——m)^m!(n——m)^n二左邊證明：根據(jù)組合性質(zhì)，左邊各式可寫成:C；=C"Cr+1「r+1_r+2r+1Cr=Cr+1-Cr+1r+2r+3r+2Cr=Cr+1-Cr+1M+3r+4r+3cr=Cr+1-Cr+1n-1nn-1Cr=Cr+1-CrM+3r+4r+3Cr+Cr+Cr+L+Cr=Cr+1rr+1r+2nn+1⑥證明：用數(shù)學(xué)歸納法證明。當(dāng)n=1時(shí)，C0+0=2=21所以等式成立。11假設(shè)n=k時(shí)，(kN1,kEN*)時(shí)等式成立。即：C0+C1+C2+L+Ck=2kkkkk當(dāng)n=k+1時(shí)，C0+C1+C2+L+Ck+Ck+1=C+1+7Co+C1)+(c++C2)+L1+(Ck-1+Ck)+Ck+1k+1kkkkkkk+1=(Co+G+C2+L+Ck)+(C0+C1+C2+L+Ck)=2g2kkkkkkkk=2k+1等式也成立由1）、2）得，等式對(duì)nEN*都成立。也可用二項(xiàng)式定理證明（略）⑦證明：用歸納法同上（略）也可利用上述結(jié)論證明（略）本課件盡量避開用二項(xiàng)式定理，但這比較簡(jiǎn)單，暫且用一下:設(shè)a=G+C3+C5+Lb^nnn__.=C0+C2+C4+L

nnn由（1+1）n可得：a+b=2n=2X2n_1由（1-1）n可得a-b=0/.a=b=2n-1（不懂的去學(xué)學(xué)二項(xiàng)式定理）⑧證明：由mCm=nCm-1可得：（還記得這個(gè)恒等式嗎，不記得就回過頭去看③的證明）nn-1左邊一一一,一-《0+nCi+nC2+nC3+LnCn-i=n&+日+宜+51仁-廣n-1n-1n-1n-1n-1=ng2n-1注：同