【正文】 離 散 數(shù) 學(xué) 第 12章 基本的組合計(jì)數(shù)公式 2022年 7月 13日星期三 832 2022/7/13 前言 組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支 。 據(jù)傳說(shuō) ， 大禹在 4000多年前就觀察到神龜背上的幻方 … ... 833 2022/7/13 前言 幻方可以看作是一個(gè) 3階方陣 ，其元素是 1到 9的正整數(shù) ， 每行 、 每列以及兩條對(duì)角線的和都是 15。 5 1 9 3 7 2 4 8 6 834 2022/7/13 前言 賈憲 北宋數(shù)學(xué)家 （ 約 11世紀(jì) ） 著有 《 黃帝九章細(xì)草 》 、 《 算法斅古集 》 斅 音 “ 笑 （ “ 古算法導(dǎo)引 ” ） 都已失傳 。 楊輝著 《 詳解九章算法 》 （ 1261年 ）中曾引賈憲的 “ 開(kāi)方作法本源 ” 圖 （ 即指數(shù)為正整數(shù)的二項(xiàng)式展開(kāi)系數(shù)表 ， 現(xiàn)稱 “ 楊輝三角形 ” ） 和 “ 增乘開(kāi)方法 ” （ 求高次冪的正根法 ） 。 前者比帕斯卡三角形早600年 ， 后者比霍納 （ William Geoge Horner， 1786—1837） 的方法 （ 1819年 ） 早 770年 。 835 2022/7/13 前言 1666年萊布尼茲所著 《 組合學(xué)論文 》 一書問(wèn)世 ， 這是組合數(shù)學(xué)的第一部專著 。 書中首次使用了組合論 （ Combinatorics） 一詞 。 836 2022/7/13 前言 組合數(shù)學(xué)的蓬勃發(fā)展則是在計(jì)算機(jī)問(wèn)世和普遍應(yīng)用之后 。 由于組合數(shù)學(xué)涉及面廣 ， 內(nèi)容龐雜 ， 并且仍在很快地發(fā)展著 ， 因而還沒(méi)有一個(gè)統(tǒng)一而有效的理論體系 。 這與數(shù)學(xué)分析形成了對(duì)照 。 837 2022/7/13 前言 組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜 。最主要的方法是 計(jì)數(shù)時(shí)的合理分類 和 組合模型的轉(zhuǎn)換 。 但是 ， 要學(xué)好組合數(shù)學(xué)并非易事 ， 既需要一定的數(shù)學(xué)修養(yǎng) ， 也要進(jìn)行相當(dāng)?shù)挠?xùn)練 。 838 2022/7/13 計(jì)數(shù)問(wèn)題 計(jì)數(shù)問(wèn)題是組合數(shù)學(xué)研究的主要問(wèn)題之一 。 西班牙數(shù)學(xué)家 Abraham ben Meir ibn Ezra(1092～1167)和法國(guó)數(shù)學(xué)家 、 哲學(xué)家 、 天文學(xué)家 Levi ben Gerson(1288～ 1344)是排列與組合領(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ù)課程中有非常重要的應(yīng)用 。 839 2022/7/13 內(nèi)容提要 二項(xiàng)式定理與組合恒等式 3 多項(xiàng)式定理 4 加法法則與乘法法則 1 排列與組合 2 8310 2022/7/13 本章學(xué)習(xí)要求 重點(diǎn)掌握 一般掌握 了解 1 1加法法則和原理法則 2排列組合的計(jì)算 3 1 離散概率 2 離散概念的計(jì) 算公式及性質(zhì) 2 二項(xiàng)式定理與組合恒等式計(jì)算 8311 2022/7/13 組合問(wèn)題的處理技巧 ?一一對(duì)應(yīng) ?數(shù)學(xué)歸納法 ?上下界逼近 8312 2022/7/13 一一對(duì)應(yīng)與上下界逼近 例 1 在允許移動(dòng)被切割的物體的情況下，最少用多少次切割可以將 3?3?3 的立方體切成 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人，因此至少需要 99場(chǎng)比賽 . 8313 2022/7/13 開(kāi)胃食品 主食 飲料 種類 價(jià)格(元 ) 種類 價(jià)格 種類 價(jià)格 玉米片(Co) 漢堡 (H) 茶水 (T) 色拉 (Sa) 三明治(S) 牛奶(M) 魚排 (F) 可樂(lè) (C) 啤酒 (B) 表 1 8314 2022/7/13 乘法法則 如果一些工作需要 t步完成 ， 第一步有 n1種不同的選擇 ， 第二步有 n2種不同的選擇 ， … ，第 t步有 nt種不同的選擇 ， 那么完成這項(xiàng)工作所有可能的選擇種數(shù)為： 1 2 tn n n8315 2022/7/13 例 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ò)散 。 病毒非?？焖俚剞D(zhuǎn)發(fā)郵件 ， 將被轉(zhuǎn)發(fā)的郵件臨時(shí)存儲(chǔ)在某個(gè)磁盤上 ， 當(dāng)磁盤占滿后 ， 系統(tǒng)將會(huì)死鎖甚至崩潰 。問(wèn)經(jīng)過(guò)四次轉(zhuǎn)發(fā) ， 共有多少個(gè)接收者 ？ 解 根據(jù) Melissa病毒的擴(kuò)散原理，經(jīng)過(guò)四次轉(zhuǎn)發(fā)， 共有 50 50 50 50+50 50 50+50 50+ 50 +1 = 6377551個(gè)接收者。 8316 2022/7/13 例 2 在一幅數(shù)字圖像中 ， 若 每個(gè)像素點(diǎn)用 8位進(jìn)行編碼 ，問(wèn) 每個(gè)點(diǎn)有多少種不同的取值 。 分析 用 8位進(jìn)行編碼可分為 8個(gè)步驟：選擇第一位 ，選擇第二位 ， … ， 選擇第八位 。 每一個(gè)位有兩種選擇 ， 故 根 據(jù) 乘 法 原 理 ， 8 位 編 碼 共 有2 2 2 2 2 2 2 2 = 28 = 256種取值 。 解 每個(gè)點(diǎn)有 256( = 28) 種不同的取值 。 8317 2022/7/13 加法法則 假定 X1, X2, … , Xt均為集合 ， 第 i個(gè)集合 Xi有ni個(gè)元素 。 如 {X1, X2, … , Xt}為 兩兩不相交 的集合 ， 則可以從 X1, X2, … , Xt中選出的元素總數(shù)為： n1 + n2 + … + nt。 即集合 X1∪X 2∪ … ∪X t含有 n1 + n2 + … + nt個(gè)元素。 8318 2022/7/13 例 3 由 Alice 、 Ben 、 Connie 、 Dolph 、 Egbert 和Francisco六個(gè)人組成的委員會(huì) ， 要 選出一個(gè)主席 、一個(gè)秘書和一個(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種選擇；主席選定后 ， 秘書有 5個(gè)人選；主席和秘書都選定后 ， 出納有 4個(gè)人選 。 根據(jù) 乘法法則 ， 可能的選法種數(shù)為 2 5 4 = 40； [法二 ]若 Alice被選為主席 ， 共有 5 4 = 20種方法確定其他職位；若 Ben為主席 ， 同樣有 20種方法確定其他職位 。 由于兩種選法得到的集合不相交 ， 所以根據(jù) 加法法則 ， 共有 20＋ 20 = 40種選法； 8320 2022/7/13 例 3 解 (續(xù) ) (3)[法一 ] 將確定職位分為 3步： 確定 Egbert的職位 ,有 3種方法； 確定余下的較高職位人選 , 有 5個(gè)人選； 確定最后一個(gè)職位的人選 , 有 4個(gè)人選 。 根據(jù) 乘法法則 ， 共有 3 5 4 = 60種選法； [法二 ] 根據(jù) (1)的結(jié)論 ， 如果 Egbert為主席 ， 有 20種方法確定余下的職位； 若 Egbert為秘書 ， 有 20種方法確定余下的職位； 若 Egbert為出納員 ， 也有 20種方法確定余下的職位 。 由于三種選法得到的集合不相交 ， 根據(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è)人選 。 根據(jù) 乘法法則 ， 共有 3 2 4 = 24種選法 。 8322 2022/7/13