1、離 散 數(shù) 學(xué),第12章 基本的組合計(jì)數(shù)公式,2020年7月31日星期五,2020/7/31,前言,組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說(shuō)，大禹在4000多年前就觀察到神龜背上的幻方.,2020/7/31,前言,幻方可以看作是一個(gè)3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對(duì)角線的和都是15。,5,1,9,3,7,2,4,8,6,2020/7/31,前言,賈憲 北宋數(shù)學(xué)家（約11世紀(jì)） 著有黃帝九章細(xì)草、算法斅古集斅 音“笑（“古算法導(dǎo)引”）都已失傳。楊輝著詳解九章算法（1261年）中曾引賈憲的“開(kāi)方作法本源”圖（即指數(shù)為正整數(shù)的二項(xiàng)式展開(kāi)系數(shù)表，現(xiàn)稱“楊輝三角形”）和“增乘開(kāi)

2、方法”（求高次冪的正根法）。前者比帕斯卡三角形早600年，后者比霍納（William Geoge Horner，17861837）的方法（1819年）早770年。,2020/7/31,前言,1666年萊布尼茲所著組合學(xué)論文一書(shū)問(wèn)世，這是組合數(shù)學(xué)的第一部專著。書(shū)中首次使用了組合論（Combinatorics）一詞。,2020/7/31,前言,組合數(shù)學(xué)的蓬勃發(fā)展則是在計(jì)算機(jī)問(wèn)世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒(méi)有一個(gè)統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對(duì)照。,2020/7/31,前言,組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類

3、和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。,2020/7/31,計(jì)數(shù)問(wèn)題,計(jì)數(shù)問(wèn)題是組合數(shù)學(xué)研究的主要問(wèn)題之一。西班牙數(shù)學(xué)家Abraham ben Meir ibn Ezra(10921167)和法國(guó)數(shù)學(xué)家、哲學(xué)家、天文學(xué)家Levi ben Gerson(12881344)是排列與組合領(lǐng)域的兩位早期研究者。另外，法國(guó)數(shù)學(xué)家Blaise Pascal還發(fā)明了一種機(jī)械計(jì)算器，這種計(jì)算器非常類似于20世紀(jì)40年代在數(shù)字電子計(jì)算機(jī)發(fā)明之前使用的一種機(jī)械計(jì)算器。同時(shí)，計(jì)數(shù)技術(shù)在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中是很重要的，特別是在數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計(jì)等后續(xù)課程中有非

4、常重要的應(yīng)用。,2020/7/31,內(nèi)容提要,2020/7/31,本章學(xué)習(xí)要求,2020/7/31,組合問(wèn)題的處理技巧,一一對(duì)應(yīng) 數(shù)學(xué)歸納法 上下界逼近,2020/7/31,一一對(duì)應(yīng)與上下界逼近,例1 在允許移動(dòng)被切割的物體的情況下，最少用多少次切割可以將 333 的立方體切成 27個(gè)單位邊長(zhǎng)的立方體？,中間的小立方體的6個(gè)面都是切割產(chǎn)生的面，每次切割至多產(chǎn)生一個(gè)面，至少需要6次切割。存在一種切割方法恰好用 6 次切割。,例2 100個(gè)選手淘汰賽，為產(chǎn)生冠軍至少需要多少輪比賽？ 方法1：50+25+12+6+3+2+1=99 方法2：比賽次數(shù)與淘汰人數(shù)之間存在一一對(duì)應(yīng)，總計(jì)淘汰99人，因此至少

5、需要99場(chǎng)比賽.,2020/7/31,12.1加法法則與乘法法則,表1,2020/7/31,乘法法則,如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇， ，第t步有nt種不同的選擇，那么完成這項(xiàng)工作所有可能的選擇種數(shù)為：,2020/7/31,例1 Melissa病毒,1990年，一種名叫Melissa的病毒利用侵吞系統(tǒng)資源的方法來(lái)破壞計(jì)算機(jī)系統(tǒng)，通過(guò)以含惡意宏的字處理文檔為附件的電子郵件傳播。當(dāng)字處理文檔被打開(kāi)時(shí)，宏從用戶的地址本中找出前50個(gè)地址，并將病毒轉(zhuǎn)發(fā)給他們。用戶接收到這些被轉(zhuǎn)發(fā)的附件并將字處理文檔打開(kāi)后，病毒會(huì)自動(dòng)繼續(xù)轉(zhuǎn)發(fā)，不斷往復(fù)擴(kuò)散。病毒非常快速地轉(zhuǎn)

6、發(fā)郵件，將被轉(zhuǎn)發(fā)的郵件臨時(shí)存儲(chǔ)在某個(gè)磁盤(pán)上，當(dāng)磁盤(pán)占滿后，系統(tǒng)將會(huì)死鎖甚至崩潰。問(wèn)經(jīng)過(guò)四次轉(zhuǎn)發(fā)，共有多少個(gè)接收者？,解 根據(jù)Melissa病毒的擴(kuò)散原理，經(jīng)過(guò)四次轉(zhuǎn)發(fā)， 共有 50505050+505050+5050+ 50 +1 = 6377551個(gè)接收者。,2020/7/31,例2,在一幅數(shù)字圖像中，若每個(gè)像素點(diǎn)用8位進(jìn)行編碼，問(wèn)每個(gè)點(diǎn)有多少種不同的取值。 分析 用8位進(jìn)行編碼可分為8個(gè)步驟：選擇第一位，選擇第二位， ，選擇第八位。每一個(gè)位有兩種選擇，故根據(jù)乘法原理，8位編碼共有22222222 = 28 = 256種取值。 解 每個(gè)點(diǎn)有256( = 28) 種不同的取值。,2020/7/

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

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

9、法；確定余下的較高職位人選, 有5個(gè)人選；確定最后一個(gè)職位的人選, 有4個(gè)人選。根據(jù)乘法法則，共有354 = 60種選法； 法二 根據(jù)(1)的結(jié)論，如果Egbert為主席，有20種方法確定余下的職位；若Egbert為秘書(shū)，有20種方法確定余下的職位；若Egbert為出納員，也有20種方法確定余下的職位。由于三種選法得到的集合不相交，根據(jù)加法法則，共有 202020 = 60種選法；,2020/7/31,例3 解(續(xù)),（4）將給Dolph、Francisco和另一個(gè)人指定職位分為3步： 給Dolph指定職位，有3個(gè)職位可選； 給Francisco指定職位，有2個(gè)職位可選； 確定最后一個(gè)職位的人

10、選，有4個(gè)人選。 根據(jù)乘法法則，共有324 = 24種選法。,2020/7/31,12.2 排列與組合,Zeke、Yung、Xeno和Wilma四個(gè)候選人競(jìng)選同一職位。為了使選票上人名的次序不對(duì)投票者產(chǎn)生影響，有必要將每一種可能的人名次序打印在選票上。會(huì)有多少種不同的選票呢？ 從某個(gè)集合中有序的選取若干個(gè)元素的問(wèn)題，稱為排列問(wèn)題。,2020/7/31,排列問(wèn)題,定義12.1 （1） 從含n個(gè)不同元素的集合S中有序選取的r個(gè)元素叫做S的一個(gè)r -排列，不同的排列總數(shù)記為P(n, r)。如果r = n，則稱這個(gè)排列為S的一個(gè)全排列，簡(jiǎn)稱為S的排列。 顯然，當(dāng)rn時(shí)，P(n, r) = 0。,202

11、0/7/31,例1,從含3個(gè)不同元素的集合S中有序選取2個(gè)元素的排列總數(shù)。 解 從含3個(gè)元素的不同集合S中有序選取2個(gè)元素的排列總數(shù)為6種。 如果將這3個(gè)元素記為A、B和C，則6個(gè)排列為 AB, AC, BA, BC, CB, CA。,2020/7/31,定理12.1,對(duì)滿足rn的正整數(shù)n和r有,2020/7/31,注意：,n個(gè)不同元素的排列共有n！種，其中,2020/7/31,例2,A,B,C,D,E,F組成的排列中， （1）有多少含有DEF的子串？ （2）三個(gè)字母D、E和F相連的有多少種？ 解 (1)將DEF看成一個(gè)對(duì)象，根據(jù)定理，滿足條件的排列為A,B,C,DEF的全排列，共有4！=24

12、種； （2）根據(jù)題意，滿足該條件的排列分為兩步：第一步確定D, E和F三個(gè)字母的全排列，有3！種排列，第二步將已排序的D, E和F看成一個(gè)整體，與A, B和C共4個(gè)元素構(gòu)造出A, B, C, D, E, F的全排列，有4！種排列。又根據(jù)乘法原理，滿足條件的排列總數(shù)有3！4！=144。,2020/7/31,例3,6個(gè)人圍坐在圓桌上，有多少種不同的坐法？通過(guò)轉(zhuǎn)圈得到的坐法視為同一種坐法。 解 6個(gè)人圍坐在圓桌上， 有120種不同的坐法。,n個(gè)人圍坐圓桌上，有(n-1)！種不同的坐法，我們稱這種排列為環(huán)排列，從n個(gè)人中選出r個(gè)人為圓桌而坐稱為環(huán)形r -排列。,2020/7/31,推論1,含n個(gè)不同元

13、素的集合的環(huán)形r-排列數(shù)Pc(n,r)是,2020/7/31,例4,求滿足下列條件的排列數(shù)。 (1)10個(gè)男孩和5個(gè)女孩站成一排，無(wú)兩個(gè)女孩相鄰。 (2)10個(gè)男孩和5個(gè)女孩站成一圓圈，無(wú)兩個(gè)女孩相鄰. 解 (1)根據(jù)定理，10個(gè)男孩的全排列為10!，5個(gè)女孩插入到10個(gè)男孩形成的11個(gè)空格中的插入方法數(shù)為P(11, 5)。根據(jù)乘法法則，10個(gè)男孩和5個(gè)女孩站成一排，沒(méi)有兩個(gè)女孩相鄰的排列數(shù)為： 10! P(11, 5) =（10!11!)/6! 。,2020/7/31,例4 解（續(xù)）,（2） 根據(jù)定理，10個(gè)男孩站成一個(gè)圓圈的環(huán)排列數(shù)為9！，5個(gè)女孩插入到10男孩形成的10個(gè)空中的插入方法數(shù)

14、為P(10, 5)。根據(jù)乘法原理，10個(gè)男孩和5個(gè)女孩站成一個(gè)圓圈，沒(méi)有兩個(gè)女孩相鄰的排列法為： 9! P(10, 5) =（9!10!)/5!。,2020/7/31,組合問(wèn)題,定義12.1 （2） 從含有n個(gè)不同元素的集合S中無(wú)序選取的r個(gè)元素叫做S的一個(gè)r -組合，不同的組合總數(shù)記為C(n, r)。 當(dāng)nr = 0時(shí)，規(guī)定C(n, r) = 1。 顯然，當(dāng)rn時(shí)，C(n, r) = 0。,2020/7/31,定理12.1（2）,對(duì)滿足0 r n的正整數(shù)n和r有，即 證明 先從n個(gè)不同元素中選出r個(gè)元素，有C(n, r)種選法，再把每一種選法選出的r個(gè)元素做全排列，有r！種排法。,2020/

15、7/31,定理12.1（2）（續(xù)）,根據(jù)乘法法則，n個(gè)元素的r排列數(shù)為： 即,2020/7/31,例5,一副52張的撲克牌含有4種花色：梅花、方片、紅桃和黑桃；各有13種點(diǎn)數(shù)，分別為A, 210, J, Q, K。試求滿足下列條件的組合數(shù)。 （1）手中持有5張牌稱為一手牌，一手牌共有多少種可能的組合？ （2）一手牌中的5張都是同一花色，共有多少種可能的組合？ （3）一手牌中有3張牌點(diǎn)數(shù)相同，另外兩張牌點(diǎn)數(shù)相同，共有多少種可能的組合？,2020/7/31,例5 解,（1）一手牌可能的組合數(shù)等于從52張牌中選出5張的可能組合數(shù)，有C(52,5)種可能的組合； （2）選同一花色的5張牌分兩步進(jìn)行：一

16、選花色，有C(4, 1)種，二在選定的花色中選5張牌，有C(13, 5)種。據(jù)乘法原理，有C(4,1)C(13,5)種；,2020/7/31,例5 解（續(xù)）,（3）該組合問(wèn)題需四步完成： 一選第一個(gè)點(diǎn)數(shù)，有C(13,1)種； 二選第二個(gè)點(diǎn)數(shù)，有C(12,1)種： 三選第一點(diǎn)數(shù)的3張牌，有C(4, 3)種； 四選第二點(diǎn)數(shù)的2張牌，有C(4,2)種。 根據(jù)乘法法則，共有 C(13,1)C(12, 1)C(4, 3)C(4, 2) = 131246 = 3744種選法。,2020/7/31,集合的排列,定義12.1 從 n 元集 S 中有序、不重復(fù)選取的 r 個(gè)元素稱為 S 的一個(gè) r 排列，S 的

17、所有 r 排列的數(shù)目記作 P(n,r) 定理12.1 證明 使用乘法法則 推論1 S 的環(huán)排列數(shù) =,2020/7/31,集合的組合,定義12.1 從 n 元集 S 中無(wú)序、不重復(fù)選取的 r 個(gè)元素稱為 S 的一個(gè) r 組合，S 的所有 r 組合的數(shù)目記作 C(n,r) 定理12.1,推論2 設(shè)n, r為正整數(shù)，則 (1) C(n, r)= (2) C(n, r) = C(n, nr) (3) C(n, r)=C(n1,r1)+C(n1,r),2020/7/31,證明方法,方法1：公式代入并化簡(jiǎn) 方法2：組合證明 實(shí)例：證明 C(n, r) = C(n, nr) 證 設(shè) S =1, 2, ,

18、n是n元集合，對(duì)于S 的任意 r-組合 A=a1, a2, , ar，都存在一個(gè)S 的 nr 組合SA與之對(duì)應(yīng). 顯然不同的 r 組合對(duì)應(yīng)了不同的 nr 組合，反之也對(duì)，因 此 S 的 r 組合數(shù)恰好與 S 的(nr)組合數(shù)相等. C(n, r)=C(n1,r1)+C(n1,r) 稱為 Pascal公式，也對(duì)應(yīng)了楊輝三角形， 兩種證明方法都適用.,2020/7/31,楊輝三角,2020/7/31,基本計(jì)數(shù)公式的應(yīng)用,解 分類選取 A = 1, 4, ,298 B = 2, 5, ,299 C = 3, 6, , 300 分別取自 A, B, C: 各 C(100,3) A, B, C 各取 1

19、 個(gè)（分步處理）： C(100,1)3 N= C(100,3) + 1003 = 1485100,例1 從1300中任取3個(gè)數(shù)使得其和能被3整除有多少種方法？,2020/7/31,基本計(jì)數(shù)公式的應(yīng)用(續(xù)),解: 1000!=1000 999 998 21 將上面的每個(gè)因子分解，若分解式中共有i 個(gè)5, j 個(gè)2， 那么min(i, j)就是0的個(gè)數(shù). 1, ,1000中有 500個(gè)是 2 的倍數(shù)，j 500; 200個(gè)是 5 的倍數(shù)， 40個(gè)是 25 的倍數(shù)（多加 40 個(gè) 5）， 8個(gè)是 125 的倍數(shù)（再多加 8 個(gè) 5）， 1個(gè)是 625 的倍數(shù)（再多加 1 個(gè) 5） i = 200+4

20、0+8+1 = 249. min(i, j)=249.,例2 求1000！的末尾有多少個(gè)0？,2020/7/31,基本計(jì)數(shù)公式的應(yīng)用(續(xù)),例3 設(shè)A為 n 元集，問(wèn) (1) A上的自反關(guān)系有多少個(gè)？ (2) A上的反自反關(guān)系有多少個(gè)？ (3) A上的對(duì)稱關(guān)系有多少個(gè)？ (4) A上的反對(duì)稱關(guān)系有多少個(gè)？ (5) A上既不對(duì)稱也不是反對(duì)稱 的關(guān)系有多少個(gè)？,2020/7/31,多重集的排列,定理12.2 多重集S=n1a1, n2a2, , nkak，0 ni + (1) 全排列 r = n, n1 + n2 + + nk = n 證明：分步選取. 先放a1, 有C(n,n1) 種方法；再放a

21、2, 有 C(n n1,n2)種方法, . , 放ak,有C(nn1n2 nk1,nk) 種方法 (2) 若r ni 時(shí)，每個(gè)位置都有 k 種選法，得 kr.,2020/7/31,多重集的組合,定理12.3 多重集 S=n1a1, n2a2, , nkak，0ni + 當(dāng) r ni , S的r 組合數(shù)為 N = C(k+r1,r), 證明 一個(gè) r 組合為 x1a1, x2a2, , xkak， 其中 x1 + x2 + + xk = r , xi 為非負(fù)整數(shù). 這個(gè)不定方程的非負(fù)整數(shù)解對(duì)應(yīng)于下述排列 11 0 11 0 11 0 0 11 x1個(gè) x2個(gè) x3個(gè) xk個(gè) r 個(gè)1，k1個(gè) 0

22、 的全排列數(shù)為,2020/7/31,實(shí)例,例5 排列26個(gè)字母，使得 a 與 b 之間恰有7個(gè)字母，求方法數(shù).,解： 設(shè)盒子的球數(shù)依次記為 x1, x2, , xn, 則滿足 x1 + x2 + + xn = r， x1, x2, , xn 為非負(fù)整數(shù) N = C(n+r1, r),例4 r 個(gè)相同的球放到 n 個(gè)不同的盒子里，每個(gè)盒子球數(shù)不限，求放球方法數(shù).,解： 固定a 和 b, 中間選7個(gè)字母，有2 P(24,7)種方法， 將它看作大字母與其余17個(gè)字母全排列有18！種，共 N = 2 P(24,7) 18!,2020/7/31,實(shí)例(續(xù)),例6 (1) 10個(gè)男孩，5個(gè)女孩站成一排，若

23、沒(méi)有女孩相鄰， 有多少種方法？ (2) 如果站成一個(gè)圓圈，有多少種方法？,解: (1) P(10,10) P(11,5) (2) P(10,10) P(10,5)/10,解：相當(dāng)于2n 不同的球放到 n 個(gè)相同的盒子，每個(gè)盒子2個(gè)，放法為,例7 把 2n 個(gè)人分成 n 組，每組2人，有多少分法？,2020/7/31,實(shí)例(續(xù)),解 使用一一對(duì)應(yīng)的思想求解這個(gè)問(wèn)題. a1, a2, , ak ：k個(gè)不相鄰的數(shù), 屬于集合1, 2, , n b1, b2, , bk：k個(gè)允許相鄰的數(shù), 屬于集合1, , n(k1) 對(duì)應(yīng)規(guī)則是 bi = ai(i1). i =1, 2, , k 因此 N = C(

24、nk+1,k),例8 從S=1, 2, , n中選擇 k 個(gè)不相鄰的數(shù)，有多少種方法？,2020/7/31,12.3二項(xiàng)式定理與組合恒等式,12.3.1 二項(xiàng)式定理 12.3.2 組合恒等式 12.3.3 非降路徑問(wèn)題,2020/7/31,二項(xiàng)式定理,定理12.4設(shè) n 是正整數(shù)，對(duì)一切 x 和 y 證明方法: 數(shù)學(xué)歸納法、組合分析法. 證 當(dāng)乘積被展開(kāi)時(shí)其中的項(xiàng)都是下述形式：xi yni, i = 0, 1, 2, , n. 而構(gòu)成形如 xiyni 的項(xiàng)，必須從n 個(gè) 和 (x+y) 中選 i 個(gè)提供 x，其它的 ni 個(gè)提供 y. 因此， xiyni 的系數(shù)是 ，定理得證.,2020/7/

25、31,二項(xiàng)式定理的應(yīng)用,例1 求在(2x3y)25的展開(kāi)式中x12y13的系數(shù). 解 由二項(xiàng)式定理 令i =13 得到展開(kāi)式中x12y13的系數(shù)，即,2020/7/31,組合恒等式遞推式,證明方法：公式代入、組合分析 應(yīng)用： 1式用于化簡(jiǎn) 2式用于求和時(shí)消去變系數(shù) 3式用于求和時(shí)拆項(xiàng)（兩項(xiàng)之和或者差），然后合并,2020/7/31,組合恒等式變下項(xiàng)求和,證明公式4. 方法：二項(xiàng)式定理或者組合分析. 設(shè)S=1,2,n，下面計(jì)數(shù)S 的所有子集. 一種方法就是分類處理，n元集合的 k子集個(gè)數(shù)是,根據(jù)加法法則，子集總數(shù)是,另一種方法是分步處理，為構(gòu)成 S 的子集A，每個(gè)元素有 2 種選擇，根據(jù)乘法法則

26、，子集總數(shù)是2n.,2020/7/31,恒等式求和變系數(shù)和,證明方法： 二項(xiàng)式定理、級(jí)數(shù)求導(dǎo) 其他組合恒等式代入,2020/7/31,證明公式6 (二項(xiàng)式定理+求導(dǎo)),2020/7/31,證明公式7 (已知恒等式代入),2020/7/31,恒等式變上項(xiàng)求和,證明 組合分析. 令S=a1, a2, , an+1為n+1元集合. 等式右邊是 S 的 k+1子集數(shù). 考慮另一種分類計(jì)數(shù)的方 法. 將所有的k+1元子集分成如下n+1類： 第1類：含a1, 剩下 k個(gè)元素取自a2,an+1,第2類：不含a1,含a2, 剩下k個(gè)元素取自 a3, , an+1, 不含a1, a2, , an, 含an+1,

27、剩下k個(gè)元素取自空集,由加法法則公式得證,2020/7/31,恒等式乘積轉(zhuǎn)換式,證明方法：組合分析. n 元集中選取 r 個(gè)元素，然后在這 r 個(gè)元素中再選 k個(gè) 元素. 不同的 r 元子集可能選出相同的 k子集，例如 a, b, c, d, e a, b, c, d b, c, d b, c, d, e b, c, d 重復(fù)度為： 應(yīng)用：將變下限 r 變成常數(shù) k，求和時(shí)提到和號(hào)外面.,2020/7/31,恒等式積之和,關(guān)系,證明思路：考慮集合A=a1,a2,am，B=b1,b2,bn. 等 式右邊計(jì)數(shù)了從這兩個(gè)集合中選出r個(gè)元素的方法. 將這 些選法按照含有A中元素的個(gè)數(shù) k 進(jìn)行分類，k

28、=0,1,r. 然后使用加法法則.,2020/7/31,組合恒等式解題方法小結(jié),證明方法： 已知恒等式帶入 二項(xiàng)式定理 冪級(jí)數(shù)的求導(dǎo)、積分 歸納法 組合分析 求和方法： Pascal公式 級(jí)數(shù)求和 觀察和的結(jié)果，然后使用歸納法證明 利用已知的公式,2020/7/31,非降路徑問(wèn)題,基本計(jì)數(shù)模型 限制條件下的非降路徑數(shù) 非降路徑模型的應(yīng)用 證明恒等式 單調(diào)函數(shù)計(jì)數(shù) 棧的輸出,2020/7/31,基本計(jì)數(shù)模型,(0,0) 到 (m,n) 的非降路徑數(shù)：C(m+n, m) (a,b) 到 (m,n)的非降路徑數(shù)： 等于 (0,0) 到 (ma,nb) 的非降路徑數(shù) (a,b) 經(jīng)過(guò) (c,d) 到

29、(m,n) 的非降路徑數(shù)：乘法法則,2020/7/31,限制條件的非降路徑數(shù),從(0,0)到(n,n)不接觸對(duì)角線的非降路徑數(shù) N N1：從(0,0) 到 (n,n) 下不接觸對(duì)角 線非降路徑數(shù) N2：從(1,0)到(n,n1) 下不接觸對(duì)角 線非降路徑數(shù) N0: 從(1,0)到(n,n1) 的非降路徑數(shù) N3: 從(1,0)到(n,n1) 接觸對(duì)角線的 非降路徑數(shù) 關(guān)系: N=2N1=2N2=2N0 N3,2020/7/31,一一對(duì)應(yīng),N3: 從(1,0)到(n,n1) 接觸對(duì)角線的 非降路徑數(shù) N4: 從(0,1)到(n,n1) 無(wú)限制條件的 非降路徑數(shù) 關(guān)系: N3=N4,2020/7/

30、31,應(yīng)用證明恒等式,例2 證明 證： 計(jì)數(shù)(0,0)到(m+nr,r) 的非降路徑數(shù) 按照 k分類，再分步. (0,0)到(mk,k)路徑數(shù)， (mk,k)到(m+nr,r)的路徑數(shù),2020/7/31,應(yīng)用單調(diào)函數(shù)計(jì)數(shù),例3 A=1,2,m, B=1,2,n， N1:B上單調(diào)遞增函數(shù)個(gè) 數(shù)是(1,1)到 (n+1,n) 的非降路徑數(shù) N: B上單調(diào)函數(shù)個(gè)數(shù) N=2N1 N2: A到B單調(diào)遞增函數(shù)個(gè) 數(shù)是從(1,1)到 (m+1,n) 的非降路徑數(shù) N: A到B的單調(diào)函數(shù)個(gè)數(shù)，N =2N2 嚴(yán)格單調(diào)遞增函數(shù)、遞減函數(shù)個(gè)數(shù)都是C(n,m),2020/7/31,函數(shù)計(jì)數(shù)小結(jié),A = 1, 2,

31、, m, B = 1, 2, , n f: AB,2020/7/31,應(yīng)用棧輸出的計(jì)數(shù),例4 將1,2,n按照順序輸入棧,有多少個(gè)不同的輸出序列？ 解：將進(jìn)棧、出棧分別記作 x,y, 出棧序列是n個(gè)x，n個(gè)y的排列，排列中任何前綴的 x 個(gè)數(shù)不少于y 的個(gè)數(shù). 等于從 (0,0) 到 (n,n) 的不穿過(guò)對(duì)角線的非降路徑數(shù). 實(shí)例：n=5 x, x, x ,y, y, x, y, y, x, y 進(jìn),進(jìn),進(jìn),出,出,進(jìn),出,出,進(jìn),出 3, 2, 4, 1, 5,2020/7/31,應(yīng)用棧輸出的計(jì)數(shù)(續(xù)),N: 堆棧輸出個(gè)數(shù) N:(0,0)到(n,n)不 穿過(guò)對(duì)角線的 非降路徑數(shù) N0:(0,

32、0)到(n,n)的 非降路徑總數(shù) N1:(0,0)到(n,n)的 穿過(guò)對(duì)角線的 非降路徑數(shù) N2:(1,1)到(n,n) 的非降路徑數(shù). 關(guān)系：N=N =N0N1, N1=N2,2020/7/31,8.4.1 多項(xiàng)式定理 8.4.2 多項(xiàng)式系數(shù),12.4 多項(xiàng)式定理,2020/7/31,多項(xiàng)式定理,.,2020/7/31,推論,推論1 多項(xiàng)式展開(kāi)式中不同的項(xiàng)數(shù)為方程 的非負(fù)整數(shù)解的個(gè)數(shù) C(n+ t 1,n) 推論2,例1 求 (2x13x2+5x3)6 中 x13x2x32 的系數(shù). 解 由多項(xiàng)式定理得,2020/7/31,多項(xiàng)式系數(shù),組合意義 多項(xiàng)式系數(shù) 多重集 S=n1 a1, n2a2

33、, , nt at 的全排列數(shù) n個(gè)不同的球放到 t 個(gè)不同的盒子使得第一個(gè)盒子 含n1個(gè)球，第二個(gè)盒子含n2個(gè)球，第 t 個(gè)盒子 含 nt 個(gè)球的方案數(shù),2020/7/31,多項(xiàng)式系數(shù)(續(xù)),恒等式,推論2,定理12.5,組合證明,2020/7/31,補(bǔ)充 計(jì)數(shù)問(wèn)題的應(yīng)用,例1 7個(gè)科學(xué)工作者從事一項(xiàng)機(jī)密的技術(shù)研究，他們的工作室裝有電子鎖，每位科學(xué)工作者都有打開(kāi)電子鎖用的“鑰匙”。為了安全起見(jiàn)，必須有4位在場(chǎng)時(shí)才能打開(kāi)大門(mén)。試問(wèn)該電子鎖至少應(yīng)具備多少個(gè)特征？每位科學(xué)工作者的“鑰匙”至少應(yīng)有多少種特征？ 解 為了使任意3個(gè)人在場(chǎng)時(shí)至少缺少一個(gè)特征而打不開(kāi)門(mén)，該電子鎖應(yīng)具備C(7,3)=35種特征；每個(gè)科學(xué)工作者的“鑰匙”至少要有C(6,3)= 2