【正文】 稱 “ 楊輝三角形 ” ） 和 “ 增乘開(kāi)方法 ” （ 求高次冪的正根法 ） 。離 散 數(shù) 學(xué) 第 12章 基本的組合計(jì)數(shù)公式 2022年 7月 13日星期三 832 2022/7/13 前言 組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支 。 前者比帕斯卡三角形早600年 ， 后者比霍納 （ William Geoge Horner， 1786—1837） 的方法 （ 1819年 ） 早 770年 。 由于組合數(shù)學(xué)涉及面廣 ， 內(nèi)容龐雜 ， 并且仍在很快地發(fā)展著 ， 因而還沒(méi)有一個(gè)統(tǒng)一而有效的理論體系 。 但是 ， 要學(xué)好組合數(shù)學(xué)并非易事 ， 既需要一定的數(shù)學(xué)修養(yǎng) ， 也要進(jìn)行相當(dāng)?shù)挠?xùn)練 。 同時(shí) ， 計(jì)數(shù)技術(shù)在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中是很重要的 ， 特別是在 《 數(shù)據(jù)結(jié)構(gòu) 》 、 《 算法分析與設(shè)計(jì) 》 等后續(xù)課程中有非常重要的應(yīng)用 。 當(dāng)字處理文檔被打開(kāi)時(shí) ，宏從用戶的地址本中找出前 50個(gè)地址 ， 并將病毒轉(zhuǎn)發(fā)給他們 。 8316 2022/7/13 例 2 在一幅數(shù)字圖像中 ， 若 每個(gè)像素點(diǎn)用 8位進(jìn)行編碼 ，問(wèn) 每個(gè)點(diǎn)有多少種不同的取值 。 8317 2022/7/13 加法法則 假定 X1, X2, … , Xt均為集合 ， 第 i個(gè)集合 Xi有ni個(gè)元素 。 （ 1） 共有多少種選法 ？ （ 2） 若 主席必須從 Alice和 Ben種選出 ， 共有多少種選法 ？ （ 3） 若 Egbert必須有職位 ， 共有多少種選法 ？ （ 4） 若 Dolph和 Francisco都有職位 ， 共有多少種選法 ？ 8319 2022/7/13 例 3 解 （ 1） 根據(jù) 乘法法則 ， 可能的選法種數(shù)為 6 5 4= 120； （ 2） [法一 ] 根據(jù)題意 ， 確定職位可分為 3個(gè)步驟：確定主席有 2種選擇；主席選定后 ， 秘書(shū)有 5個(gè)人選；主席和秘書(shū)都選定后 ， 出納有 4個(gè)人選 。 由于三種選法得到的集合不相交 ， 根據(jù) 加法法則 ， 共有 20＋ 20＋ 20 = 60種選法； 8321 2022/7/13 例 3 解 (續(xù) ) （ 4） 將給 Dolph、 Francisco和另一個(gè)人指定職位分為 3步： 給 Dolph指定職位 ， 有 3個(gè)職位可選； 給 Francisco指定職位 ， 有 2個(gè)職位可選； 確定最后一個(gè)職位的人選 ， 有 4個(gè)人選 。會(huì)有多少種不同的選票呢 ？ 從某個(gè)集合中有序的選取若干個(gè)元素的問(wèn)題 ， 稱為排列問(wèn)題 。 8324 2022/7/13 例 1 從含 3個(gè)不同元素的集合 S中有序選取 2個(gè)元素的排列總數(shù) 。又根據(jù)乘法原理 ， 滿足條件的排列總數(shù)有 3！ 4！ =144。 8329 2022/7/13 推論 1 含 n個(gè)不同元素的集合的 環(huán)形 r排列數(shù) Pc(n,r)是 cP(n, r) n!P (n, r) = =r r (n r)!8330 2022/7/13 例 4 求滿足下列條件的排列數(shù) 。 8331 2022/7/13 例 4 解（續(xù)） （ 2） 根據(jù)定理 ， 10個(gè)男孩站成一個(gè)圓圈的環(huán)排列數(shù)為 9！ ， 5個(gè)女孩插入到 10男孩形成的 10個(gè)空中的插入方法數(shù)為 P(10, 5)。 顯然 ， 當(dāng) rn時(shí) ， C(n, r) = 0。 （ 1） 手中持有 5張牌稱為一手牌 ， 一手牌共有多少種可能的組合 ？ （ 2） 一手牌中的 5張都是同一花色 ， 共有多少種可能的組合 ？ （ 3） 一手牌中有 3張牌點(diǎn)數(shù)相同 ， 另外 兩張牌點(diǎn)數(shù)相同 ， 共有多少種可能的組合 ？ 8336 2022/7/13 例 5 解 （ 1） 一手牌可能的組合數(shù)等于 從 52張牌中選出 5張的可能組合數(shù) ， 有 C(52,5)種可能的組合； （ 2） 選同一花色的 5張牌分 兩步進(jìn)行 ： 一選花色 ，有 C(4, 1)種 ， 二在選定的花色中選 5張牌 ， 有 C(13, 5)種 。 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+40+8+1 = 249. min(i, j)=249. 例 2 求 1000！的末尾有多少個(gè) 0？ 8344 2022/7/13 基本計(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è) ？ nn ?22nn ?222222222 nnnnn ?? ?2232nnn?nnnnnnn )( 23222 22222 ??? ??8345 2022/7/13 多重集的排列 定理 多重集 S={n1?a1, n2?a2, …, nk?ak}， 0 ni ?+∞ (1) 全排列 r = n, n1 + n2 + … + nk = n 證明：分步選取 . 先放 a1, 有 C(n,n1) 種方法；再放 a2, 有 C(n? n1,n2)種方法 , ... , 放 ak,有 C(n?n1?n2? … ? nk?1,nk) 種方法 (2) 若 r ? ni 時(shí)，每個(gè)位置都有 k 種選法，得 kr. ??????????kk nnnn...nnnnN...!!!!2121!!!!!0!)!. . .(. . .)!(!)!()!(!!2111212111121211kkkkk. . . nnnnnnnnnnnnnnnnnn),nn. . .nn) . . . C ( n,nn) C ( nC ( n , nN?????????????????8346 2022/7/13 多重集的組合 定理 多重集 S={n1?a1, n2?a2, …, nk?ak}， 0ni ?+∞ 當(dāng) r ? ni , S的 r 組合數(shù)為 N = C(k+r?1,r), 證明 一個(gè) r 組合為 {x1?a1, x2?a2, …, xk?ak}， 其中 x1 + x2 + … + xk = r , xi 為非負(fù)整數(shù) . 這個(gè)不定方程的非負(fù)整數(shù)解對(duì)應(yīng)于下述排列 1…1 0 1…1 0 1…1 0 …… 0 1…1 x1個(gè) x2個(gè) x3個(gè) xk個(gè) r 個(gè) 1， k?1個(gè) 0 的全排列數(shù)為 ),1()!1(! )!1( rrkCkr krN ???????8347 2022/7/13 實(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+r?1, 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! 8348 2022/7/13 實(shí)例 (續(xù) ) 例 6 (1) 10個(gè)男孩， 5個(gè)女孩站成一排，若沒(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è)，放法為 !2)!(22!0!2. . .2)!42()!22(22 ) !(2!2!1( 2 , 2 ). . .2 , 2 )(2, 2 )(2!1 nnnnnnnCnCnnNn???????例 7 把 2n 個(gè)人分成 n 組，每組 2人，有多少分法？ 8349 2022/7/13 實(shí)例 (續(xù) ) 解 使用一一對(duì)應(yīng)的思想求解這個(gè)問(wèn)題 . a1, a2, …, ak ：