排列組合公式及恒等式推導(dǎo)、證明(word版)及排列組合分房問(wèn)題總結(jié)

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

根據(jù)乘法原理，即：組合公式也適用于全組合的情況，即求

C(n,

n)的問(wèn)題。根據(jù)上述公式，C(n,

n)

=

n!/n!(n-n)!

=

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ù)公式：（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）！種排法，再由于m個(gè)小球和（n-1）塊隔板是分別不加以區(qū)分的，所以除以重復(fù)的情況：m！*（n-1）！于是答案就是：四、不全相異的全排列在不全相異的n個(gè)物體中，假設(shè)有n1個(gè)物體是相同的，n2個(gè)五題是相同的，……，nk個(gè)物體是相同的。n個(gè)物體中不相同的物體種類數(shù)一共有k種。那么，這些物體的全排列數(shù)是n!/(n1!n2!…nk!)?？梢韵氤桑簄個(gè)物體直接全排列，排列完了以后，去重，第一種物體有n1!種，第二種物體有n2!種，以此類推。例：有3個(gè)紅球，2個(gè)白球，把這五個(gè)球排成一行，問(wèn)有多少種排法？紅球和紅球沒(méi)有區(qū)別，白球和白球沒(méi)有區(qū)別。答：一共有10種，aaabb,aabab,aabba,abaab,ababa,baaab,baaba,abbaa,babaa,bbaaa。五、排列恒等式的證明：①證明：右邊=左邊=右邊②②證明：右邊=③左邊=右邊③證明：右邊=左邊=右邊④④證明：右邊=⑤ 右邊⑤ 證明：右邊=⑥⑥ 證明：左邊=(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！=右邊六、組合恒等式的證明互補(bǔ)性質(zhì)：取出有多少種，剩下就有多少種根據(jù)分類計(jì)數(shù)原理:要么含有新加元素要么不含新加元素分類計(jì)數(shù)原理互補(bǔ)性質(zhì)：取出有多少種，剩下就有多少種根據(jù)分類計(jì)數(shù)原理:要么含有新加元素要么不含新加元素分類計(jì)數(shù)原理:要么含有新加元素要么不含新加元素①① 證明：② ②證明：右邊=③③證明：右邊= =左邊⑤⑤ 證明：根據(jù)組合性質(zhì)，左邊各式可寫成：左右兩邊相加即得：⑥⑥證明：用數(shù)學(xué)歸納法證明。

1）當(dāng)n=1時(shí)，所以等式成立。

2）假設(shè)n=k時(shí)，（k≥1，k∈N*）時(shí)等式成立。

即：

當(dāng)n=k+1時(shí)，

∴等式也成立由1)、2)得，等式對(duì)n∈N*都成立。也可用二項(xiàng)式定理證明（略）⑦⑦證明：用歸納法同上（略）也可利用上述結(jié)論證明（略）本課件盡量避開(kāi)用二項(xiàng)式定理，但這比較簡(jiǎn)單，暫且用一下：設(shè)由（1+1）n可得：a+b=2n=2×2n-1由（1-1）n可得a-b=0∴a=b=2n-1(不懂的去學(xué)學(xué)二項(xiàng)式定理)⑧⑧證明：由可得:（還記得這個(gè)恒等式嗎，不記得就回過(guò)頭去看③的證明）左邊注：同時(shí)利用了⑥的結(jié)論。

⑨r≤⑨r≤min{m,n}用二項(xiàng)式定理證明太麻煩了。能偷懶就不要太勤快了。觀察左邊的每一項(xiàng)，發(fā)現(xiàn)均是分別從m個(gè)不同素和n個(gè)不同元素中取r個(gè)元素的一個(gè)組合，其各項(xiàng)之和就是所有取法，即所有組合數(shù)。其所有組合數(shù)當(dāng)然等于右邊。 ⑩⑩還是用偷懶法：根據(jù)第⑨的結(jié)論并結(jié)合組合的互補(bǔ)性質(zhì)，若r=m=n即得些結(jié)論。排列組合分房問(wèn)題首先看一個(gè)例子：10個(gè)人進(jìn)8個(gè)房間，有多少種進(jìn)法？為什么是，因?yàn)榧?，乙，丙，?..這10個(gè)人要住A,B,C,D...這8個(gè)房，甲可以有8種選擇，乙也可以有8種選擇...但是如果房子A選人，有10種選擇，房子B選人，有10種選擇，房子A.B是不能同時(shí)選擇甲，或乙的，因?yàn)橐粋€(gè)人不能同時(shí)住兩個(gè)或兩個(gè)以上的房子，顯然，讓房子選人是錯(cuò)誤的，一定是人選房子?？偨Y(jié)：這就是住店法，要客去選擇店，不能反過(guò)來(lái)。從例子中看，一個(gè)人是不能同時(shí)住多間房的，所以把這類不能重復(fù)的元素看做“客”，一間房子可以同時(shí)住多個(gè)人，把這類可以重復(fù)的元素看做“店”，然后讓客去選店。練習(xí)：1.4名候選人中，評(píng)選出1名三好學(xué)生，1名優(yōu)秀干部，1名先進(jìn)團(tuán)員，允許一人同時(shí)得幾個(gè)稱號(hào)，有多少種選法？如，甲乙丙丁4人，甲獲得三好學(xué)生，乙獲得優(yōu)秀干部，丙獲得先進(jìn)團(tuán)員;甲獲得三好學(xué)生，優(yōu)秀干部，乙獲得先進(jìn)團(tuán)員答案：先分析一下，4個(gè)人評(píng)出三個(gè)獎(jiǎng)項(xiàng)，說(shuō)明每一個(gè)獎(jiǎng)項(xiàng)都必有一名獲得者，每一個(gè)人可以獲得多個(gè)獎(jiǎng)項(xiàng)，如果這里面讓人去選獎(jiǎng)項(xiàng)，第一個(gè)人有3種選擇，第二個(gè)人有3種選擇...此時(shí)可能出現(xiàn)第一個(gè)人，第二個(gè)人甚至第三，四人全部選了三好學(xué)生，這樣顯然是錯(cuò)誤的，因?yàn)?個(gè)人要評(píng)出3個(gè)獎(jiǎng)，不能出現(xiàn)所有人都得了一種獎(jiǎng)的情況。所以，換個(gè)思維，同一個(gè)獎(jiǎng)項(xiàng)不能同時(shí)被頒給所有的4個(gè)人（其實(shí)應(yīng)該只能有是3個(gè)人或更少的人獲獎(jiǎng)），所以把獎(jiǎng)項(xiàng)看做不能重復(fù)的元素“客”，但是一個(gè)人可以同時(shí)擁有多個(gè)獎(jiǎng)項(xiàng)，（比如甲獲得了所有獎(jiǎng)項(xiàng)，那么三個(gè)人就無(wú)法獲獎(jiǎng)），所以把人看作是可以重復(fù)的元素“店”，然后讓“客”選“店”，即讓獎(jiǎng)項(xiàng)選人，每個(gè)獎(jiǎng)項(xiàng)選擇的可能性是4種，答案為。汽車上有10名乘客，沿途設(shè)有5個(gè)車站，乘客下車的不同方式有多少種？答案：如果讓人選車站，1個(gè)人可以有5種選擇自己在哪個(gè)車站下車，如果讓車站選人，如果車站A，車站B都選了人甲，甲不可能同時(shí)從兩個(gè)車站下車，顯然是錯(cuò)誤的。這里面一個(gè)人不能同時(shí)從多個(gè)車站下車，是不可重復(fù)的元素，看做“客”，一個(gè)車站可以同時(shí)下多個(gè)人，是可以重復(fù)的，看做“店”，然后讓客選店。3.5名學(xué)生爭(zhēng)奪三項(xiàng)比賽冠軍，獲得冠軍的可能情況種樹(shù)是？答案：人選獎(jiǎng)項(xiàng)，可能大家都選同一種，但是一共有三種，顯然錯(cuò)誤。這里同一個(gè)獎(jiǎng)項(xiàng)不能同時(shí)頒給所有的參賽學(xué)生，是不可重復(fù)的元素，看做“客”，但是如果一個(gè)學(xué)生比較全能他可以一個(gè)人獲得多個(gè)獎(jiǎng)項(xiàng)，是可重復(fù)元素，看做“店”。4.8封信放入3個(gè)郵箱中，有多少不同結(jié)果？答案：信選郵箱，每個(gè)新可以有3種選擇。如果讓郵箱選信，郵箱A,B,C有可能都選了第一封信，顯然一封信不能同時(shí)投遞到多個(gè)郵箱中去，那么信就是不可重復(fù)元素，看做“客”，一個(gè)郵箱可以同時(shí)接納多封信，是可重復(fù)元素，看做“店”