排列與組合
預(yù)備知識 在概率的計算中經(jīng)常要用到一些排列組合知識，也常常用到牛頓二項式定理。 這里羅列一些同學(xué)們在中學(xué)里已學(xué)過的有關(guān)公式，并適當(dāng)作一點推廣。 一. 兩個原理 1. 乘法原理: 完成一項工作有m個步驟，第一步有[pic]種方法，第二步有[pic]種方法，…， 第m步有[pic]種方法，且完成該項工作必須依次通過這m個步驟， 則完成該項工作一共有 [pic][pic]…[pic] 種方法，這一原理稱為乘法原理。 2. 加法原理: 完成一項工作有m種方式，第一種方式有[pic]種方法，第二種 方式有[pic]種方法，…，第m種方式有[pic]種方法，且完成該項工作只 需 選擇這m種方式中的一種，則完成這項工作一共有 [pic]+[pic]+…+[pic] 種方法，這一原理稱為加法原理。 二. 排列: 從n個元素里每次取出r個元素，按一定順序排成一列，稱為 從n個元素里每次取r個元素的排列，這里n和Z。均為正整數(shù)(以 下同)。 當(dāng)這n個元素全不相同時，上述的排列稱為無重復(fù)排列，我 們關(guān)心的是可以做成多少個排列，即排列數(shù)。 對于無重復(fù)排列，要求當(dāng) [pic] 時 [pic] 稱為選排列，而當(dāng) r＝n時稱為全排列。我們記排列數(shù)分別為[pic] 即將全排列看成選排列的特例。 利用乘法原理不難得到 由階乘的定義 [pic] 由階乘的定義 [pic] [pic] 將上面的n個不同的元素改為n類不同的元素，每一類元素 都有無數(shù)多個。今從這n類元素中取出r個元素，這r個元素可 以有從同一類元素中的兩個或兩個以上，將取出的這r個元素dl 成一列，稱為從n類元素中取出r個元素的可重復(fù)排列，排列數(shù)記 作[pic]，由乘法原理得 [pic] 顯然，此處r可以大于n 例3 將三封信投入4個信箱，問在下列兩種情形下各有幾 種投法? 1)每個信箱至多只許投入一封信； 2)每個信箱允許投入的信的數(shù)量不受限制。 解 1)顯然是無重復(fù)排列問題，投法的種數(shù)為 [pic] 2)是可重復(fù)排列問題，投法的種數(shù)為 [pic] 三、組合 從“個元素中每次取出r個元素，構(gòu)成的一組，稱為從n個元 素里每次取出r個元素的組合。 設(shè)這n個元素全不相同，即得所謂無重復(fù)組合，我們來求組合數(shù)，記作 [pic] 將一個組合中的r個元素作全排列，全排列數(shù)為 [pic]， 所有組合中的元素作全排列，共有 [pic] 個排列，這相當(dāng)于從n個元素里每次取r個元素的選排列，排列總數(shù)為 [pic] 故有 [pic] [pic] 性質(zhì)(2)的左端表示 [pic] 從 [pic] 中取出r個的組合數(shù)。我們可以固定這n十1個元素中的任意一個，不妨固定 [pic] 于是考察所有取[pic]及所有不取[pic]。的組合數(shù)， 前者即從[pic]個中取r—1個的組合數(shù)，而后者即 從[pic]個中取r個的組合數(shù) [pic] 類似于可重復(fù)排列，也有可重復(fù)組合，即從n類不同元素中每次取出r個元素，這r個 元素可以從同一類元素中取兩個或兩 [pic] 例4 擲兩顆銀子可以有多少種點子的排列?多少種點子的 組合? 解 每顆銀子各有六面，分別刻有1，2，3，4，5，6個點，擲出的 結(jié)果可以重復(fù)。 [pic] 四、較復(fù)雜的排列、組合問題 問題1，不全相異元素的全排列 [pic]將一個包含n 個元素的整體分成r個有序的部分，其中第一部分包含[pic]個元 素，第二部分包含[pic]個元素，…，第r部分包含[pic]個元素，分法數(shù) 共有 [pic] 種，上式稱為多項式系數(shù)。 例5 將15名新生平均分配到三個班級中去，這15名新生中 有3名優(yōu)秀生。問：1)15名新生平均分配到三個班級中有多少種 分法?2)每個班級各分配到一名優(yōu)秀生有多少種分法?3)3名優(yōu) 秀生分配在同一個班級有多少種分法? 解 1)15名新生平均分配到三個班級中的分法總數(shù)為 [pic] 2)將3名優(yōu)秀生分配到三個班級使每個班級都有一名優(yōu) 秀生的分法共3!種。對于其中每一種分法，其余12名新生平均 到三個班級中的分法共有[pic]種，由乘法原理不難得到每個 班級各分配到一名優(yōu)秀牛的分法總數(shù)為 [pic] 3)將3名優(yōu)秀生分配在同一班級內(nèi)的分法共有3種(因 有3個班級)。對于這每一種分法，其余12名新生的分法是將其 中的2名分配到已有3名優(yōu)秀生的班級，而另二個班級各5名，因 此分法數(shù)為[pic]種，由乘法原理得3名優(yōu)秀生分配在同一班級的分法總數(shù)為 [pic] 例 ：將3個白球、4個紅球和4個黑球排成一行．如果顏色相同的球彼此不加區(qū)別， 問有多少種排法？ 解：有 [pic] 種排法 問題2，不全相異元素的組合 仍設(shè)[pic]有r種不同元素，第一種有[pic]個 元素，第二種有[pic]個元素，…，第r種有[pic]個元素，今從這n個元 素中，每次取[pic]，其取法總數(shù)為下列乘積 [pic] 例6 由[pic]詞中的字母，每次擇取4個，共有幾種 不同的選擇法? 解 此詞中有8種字母，其中包括3個a，2個m，2個，以及 [pic] 各一個，每次擇取4個，故所求的取法數(shù)由 [pic] [pic] ∴[pic] 例： 要求某學(xué)生會主席指定一個委員會，包括5名男 生和3名女生，在提供的候選人名單中有10名男生和7名女生。 問可能有多少個委員會可供他選擇？ 解 在某一委員會中，如果改變委員的順序，結(jié)果仍相同， 因此，這是一個求組合的問題。從lo名男生中，主席能選出每組 有5名男生的組合數(shù)為 5．5 組合與排列個元素的整體分成r個有序的部分，其中第一部分包含Rt個元 素，第二部分包含n2個元素，…，第r部分包含n r個元素，分法數(shù) 共有 組合與排列研究事物的分組與排列，在計算概串方面，它們 可以用來決定一切可能情況的總數(shù)以及有利情況數(shù)。 定義5—8 每一個集合可以由給定事物的部分或全體組成， 可以不管集合中事物的順序則這一集合稱作組合。 定義5—9 事物的全部集合或部分集合的每一種不同的順序 或排列即稱為排列。 例5—14 在A，B，C，D四個字母中求每組三個字母的(a) 組合數(shù)，(b)排列數(shù)。 解 (a)字母A，B，C，D每組可以取三個，不計順序，有以 下取法：ABC，ABD，ACD和BCD。因此，共有4種組合，即 4個物件中每次取三個共有4種組合。 (b)如果還考慮順序，在字母A，B，C，D中每組有三個， 共有以下排列：ABC，ACB，BAC， BCA，CAB，CBA， ABD，ADB，BAD，BDA，DAB，DBA，ACD，ADC，CAD， CDA，DAC，DCA，BCD， BDC， CBD，CDB，DBC，DCB。 因此，共有24種排列：即從4物件中每次取三個共有24種排 列。 例5—15 排列數(shù)。 解 求四物件在每次取4件時的(a)組合數(shù)； (b)A，B，C，D四個 字母的順序數(shù)容易求出為24，于是4 物件每次取4件有24種排列。 為了求出計算組合數(shù)與排列數(shù)的簡易公式，我們首先考慮一 個特例，求n個物件(例如字母)每組有n項的排列數(shù)。 把這些排列都寫出來，我們就可以看到第一個字母有n種選 擇；每一種選擇對應(yīng)于圖5—3中的一個分校圖，這里表示的是 n＝4的情形。在選定第一個字母后(例如A)，在第二個字母就 余下(n—1)種選擇，于是對前面兩個字母就有n(n—1)種可能 的選擇，與固5—3中從左邊頂端發(fā)散的分技數(shù)一樣多的選擇。在 前兩個字母選定以后，對第三個字母還有n—2種選擇，于是對前 三個字母就有n(n—1)(n—2)種選擇。繼續(xù)這一過程，我們看 到對第n個字母就只留有一種選擇；因而n個字母有n(n—1) (n—2)·。2．1種排列法。 用符號nI(讀作“n的階乘”)表示前面n個正整數(shù)的乘積， 即 n?。絥(n—1)(n—2)·．．2．1 (5—9) 用Pn，n表示n個物件每組有n個的排列數(shù)，我們已經(jīng)表明 Pa，n＝n1 (5——10) [pic]
排列與組合