離散數(shù)學(xué)第12章基本的組合計數(shù)公式

1、離 散 數(shù) 學(xué)第12章基本的組合計數(shù)公式25 七月 2022前言 組合數(shù)學(xué)是一個古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方.前言幻方可以看作是一個3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對角線的和都是15。519372486前言 賈憲 北宋數(shù)學(xué)家（約11世紀(jì)） 著有黃帝九章細(xì)草、算法斅古集斅 音“笑（“古算法導(dǎo)引”）都已失傳。楊輝著詳解九章算法（1261年）中曾引賈憲的“開方作法本源”圖（即指數(shù)為正整數(shù)的二項式展開系數(shù)表，現(xiàn)稱“楊輝三角形”）和“增乘開方法”（求高次冪的正根法）。前者比帕斯卡三角形早600年，后者比霍納（William Geoge

2、Horner，17861837）的方法（1819年）早770年。前言 1666年萊布尼茲所著組合學(xué)論文一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。前言 組合數(shù)學(xué)的蓬勃發(fā)展則是在計算機(jī)問世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對照。前言 組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計數(shù)時的合理分類和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。計數(shù)問題 計數(shù)問題是組合數(shù)學(xué)研究的主要問題之一。西班牙數(shù)學(xué)家Abraha

3、m ben Meir ibn Ezra(10921167)和法國數(shù)學(xué)家、哲學(xué)家、天文學(xué)家Levi ben Gerson(12881344)是排列與組合領(lǐng)域的兩位早期研究者。另外，法國數(shù)學(xué)家Blaise Pascal還發(fā)明了一種機(jī)械計算器，這種計算器非常類似于20世紀(jì)40年代在數(shù)字電子計算機(jī)發(fā)明之前使用的一種機(jī)械計算器。同時，計數(shù)技術(shù)在數(shù)學(xué)和計算機(jī)科學(xué)中是很重要的，特別是在數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計等后續(xù)課程中有非常重要的應(yīng)用。 內(nèi)容提要二項式定理與組合恒等式3多項式定理4加法法則與乘法法則1排列與組合2 本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11加法法則和原理法則2排列組合的計算 31 離散概率2 離

4、散概念的計 算公式及性質(zhì) 2二項式定理與組合恒等式計算 組合問題的處理技巧一一對應(yīng)數(shù)學(xué)歸納法上下界逼近一一對應(yīng)與上下界逼近例1 在允許移動被切割的物體的情況下，最少用多少次切割可以將 333 的立方體切成 27個單位邊長的立方體？ 中間的小立方體的6個面都是切割產(chǎn)生的面，每次切割至多產(chǎn)生一個面，至少需要6次切割。存在一種切割方法恰好用 6 次切割。例2 100個選手淘汰賽，為產(chǎn)生冠軍至少需要多少輪比賽？ 方法1：50+25+12+6+3+2+1=99 方法2：比賽次數(shù)與淘汰人數(shù)之間存在一一對應(yīng)，總計淘汰99人，因此至少需要99場比賽.加法法則與乘法法則開胃食品主食飲料種類價格(元)種類價格種類

5、價格玉米片(Co)2.15漢堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85魚排(F)3.15可樂(C)0.75啤酒(B)0.75表1 乘法法則 如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇， ，第t步有nt種不同的選擇，那么完成這項工作所有可能的選擇種數(shù)為：例1 Melissa病毒1990年，一種名叫Melissa的病毒利用侵吞系統(tǒng)資源的方法來破壞計算機(jī)系統(tǒng)，通過以含惡意宏的字處理文檔為附件的電子郵件傳播。當(dāng)字處理文檔被打開時，宏從用戶的地址本中找出前50個地址，并將病毒轉(zhuǎn)發(fā)給他們。用戶接收到這些被轉(zhuǎn)發(fā)的附件并將字處

6、理文檔打開后，病毒會自動繼續(xù)轉(zhuǎn)發(fā)，不斷往復(fù)擴(kuò)散。病毒非?？焖俚剞D(zhuǎn)發(fā)郵件，將被轉(zhuǎn)發(fā)的郵件臨時存儲在某個磁盤上，當(dāng)磁盤占滿后，系統(tǒng)將會死鎖甚至崩潰。問經(jīng)過四次轉(zhuǎn)發(fā)，共有多少個接收者？解 根據(jù)Melissa病毒的擴(kuò)散原理，經(jīng)過四次轉(zhuǎn)發(fā)，共有50505050+505050+5050+ 50 +1= 6377551個接收者。例2在一幅數(shù)字圖像中，若每個像素點(diǎn)用8位進(jìn)行編碼，問每個點(diǎn)有多少種不同的取值。分析 用8位進(jìn)行編碼可分為8個步驟：選擇第一位，選擇第二位， ，選擇第八位。每一個位有兩種選擇，故根據(jù)乘法原理，8位編碼共有22222222 = 28 = 256種取值。解 每個點(diǎn)有256( = 28) 種

7、不同的取值。 加法法則 假定X1, X2, , Xt均為集合，第i個集合Xi有ni個元素。如X1, X2, , Xt為兩兩不相交的集合，則可以從X1, X2, , Xt中選出的元素總數(shù)為：n1 + n2 + + nt。即集合X1X2Xt含有n1 + n2 + + nt個元素。例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六個人組成的委員會，要選出一個主席、一個秘書和一個出納員。（1）共有多少種選法？（2）若主席必須從Alice和Ben種選出，共有多少種選法？（3）若Egbert必須有職位，共有多少種選法？（4）若Dolph和Francisco都有職位，共有

8、多少種選法？例3 解（1）根據(jù)乘法法則，可能的選法種數(shù)為654= 120；（2）法一 根據(jù)題意，確定職位可分為3個步驟：確定主席有2種選擇；主席選定后，秘書有5個人選；主席和秘書都選定后，出納有4個人選。根據(jù)乘法法則，可能的選法種數(shù)為254 = 40；法二若Alice被選為主席，共有54 = 20種方法確定其他職位；若Ben為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據(jù)加法法則，共有2020 = 40種選法；例3 解(續(xù))(3)法一 將確定職位分為3步：確定Egbert的職位,有3種方法；確定余下的較高職位人選, 有5個人選；確定最后一個職位的人選, 有4個人選。

9、根據(jù)乘法法則，共有354 = 60種選法；法二 根據(jù)(1)的結(jié)論，如果Egbert為主席，有20種方法確定余下的職位；若Egbert為秘書，有20種方法確定余下的職位；若Egbert為出納員，也有20種方法確定余下的職位。由于三種選法得到的集合不相交，根據(jù)加法法則，共有202020 = 60種選法； 例3 解(續(xù))（4）將給Dolph、Francisco和另一個人指定職位分為3步： 給Dolph指定職位，有3個職位可選； 給Francisco指定職位，有2個職位可選； 確定最后一個職位的人選，有4個人選。 根據(jù)乘法法則，共有324 = 24種選法。12.2 排列與組合 Zeke、Yung、Xe

10、no和Wilma四個候選人競選同一職位。為了使選票上人名的次序不對投票者產(chǎn)生影響，有必要將每一種可能的人名次序打印在選票上。會有多少種不同的選票呢？ 從某個集合中有序的選取若干個元素的問題，稱為排列問題。排列問題定義 （1） 從含n個不同元素的集合S中有序選取的r個元素叫做S的一個r -排列，不同的排列總數(shù)記為P(n, r)。如果r = n，則稱這個排列為S的一個全排列，簡稱為S的排列。顯然，當(dāng)rn時，P(n, r) = 0。 例1從含3個不同元素的集合S中有序選取2個元素的排列總數(shù)。解 從含3個元素的不同集合S中有序選取2個元素的排列總數(shù)為6種。如果將這3個元素記為A、B和C，則6個排列為A

11、B, AC, BA, BC, CB, CA。定理對滿足rn的正整數(shù)n和r有第r位第r-1位第3位第2位第1位nn-1n-2 n-(r-2)n-(r-1)注意：n個不同元素的排列共有n！種，其中 例2 A,B,C,D,E,F組成的排列中， （1）有多少含有DEF的子串？（2）三個字母D、E和F相連的有多少種？解 (1)將DEF看成一個對象，根據(jù)定理，滿足條件的排列為A,B,C,DEF的全排列，共有4！=24種；（2）根據(jù)題意，滿足該條件的排列分為兩步：第一步確定D, E和F三個字母的全排列，有3！種排列，第二步將已排序的D, E和F看成一個整體，與A, B和C共4個元素構(gòu)造出A, B, C, D

12、, E, F的全排列，有4！種排列。又根據(jù)乘法原理，滿足條件的排列總數(shù)有3！4！=144。例36個人圍坐在圓桌上，有多少種不同的坐法？通過轉(zhuǎn)圈得到的坐法視為同一種坐法。解 6個人圍坐在圓桌上，有120種不同的坐法。AEFBDCn個人圍坐圓桌上，有(n-1)！種不同的坐法，我們稱這種排列為環(huán)排列，從n個人中選出r個人為圓桌而坐稱為環(huán)形r -排列。推論1含n個不同元素的集合的環(huán)形r-排列數(shù)Pc(n,r)是例4求滿足下列條件的排列數(shù)。(1)10個男孩和5個女孩站成一排，無兩個女孩相鄰。(2)10個男孩和5個女孩站成一圓圈，無兩個女孩相鄰.解 (1)根據(jù)定理，10個男孩的全排列為10!，5個女孩插入到

13、10個男孩形成的11個空格中的插入方法數(shù)為P(11, 5)。根據(jù)乘法法則，10個男孩和5個女孩站成一排，沒有兩個女孩相鄰的排列數(shù)為：10! P(11, 5) =（10!11!)/6! 。例4 解（續(xù)）（2） 根據(jù)定理，10個男孩站成一個圓圈的環(huán)排列數(shù)為9！，5個女孩插入到10男孩形成的10個空中的插入方法數(shù)為P(10, 5)。根據(jù)乘法原理，10個男孩和5個女孩站成一個圓圈，沒有兩個女孩相鄰的排列法為： 9! P(10, 5) =（9!10!)/5!。 組合問題定義（2） 從含有n個不同元素的集合S中無序選取的r個元素叫做S的一個r -組合，不同的組合總數(shù)記為C(n, r)。當(dāng)nr = 0時，規(guī)

14、定C(n, r) = 1。顯然，當(dāng)rn時，C(n, r) = 0。定理（2）對滿足0 500; 200個是 5 的倍數(shù)， 40個是 25 的倍數(shù)（多加 40 個 5）， 8個是 125 的倍數(shù)（再多加 8 個 5）， 1個是 625 的倍數(shù)（再多加 1 個 5）i = 200+40+8+1 = 249. min(i, j)=249. 例2 求1000！的末尾有多少個0？基本計數(shù)公式的應(yīng)用(續(xù))例3 設(shè)A為 n 元集，問(1) A上的自反關(guān)系有多少個？(2) A上的反自反關(guān)系有多少個？(3) A上的對稱關(guān)系有多少個？(4) A上的反對稱關(guān)系有多少個？(5) A上既不對稱也不是反對稱 的關(guān)系有多少個？多重集的排列定理12.2 多重集S=n1a1, n2a2, , nkak，0 ni + (1) 全排列 r = n, n1 + n2 + + nk = n 證明：分步選取. 先放a1, 有C(n,n1) 種方法；再放a2, 有C(n n1,n2)種方法, . , 放ak,有C(nn1n2 nk1,nk) 種方法 (2) 若r ni 時，每個位置都有 k 種選法，得