組合數(shù)學(xué)課件_lcq.ppt

組合數(shù)學(xué) 簡介 相關(guān)課程 使用教材 數(shù)學(xué)分析 高等代數(shù) 離散數(shù)學(xué) 書名 組合數(shù)學(xué) 第三版 作者 孫淑玲出版社 中國科學(xué)技術(shù)大學(xué)出版社 本課程針對計算機(jī)科學(xué)中的一個重要學(xué)科 組合數(shù)學(xué) 組合數(shù)學(xué)是數(shù)學(xué)的一個分支 它研究事物在結(jié)定模式下的配置 研究這種配置的存在性 所有可能配置的計數(shù)和分類以及配置的各種性質(zhì) 組合數(shù)學(xué)在計算機(jī)科學(xué)中有著極其廣泛的應(yīng)用 組合學(xué)問題求解方法層出不窮 干變?nèi)f化 應(yīng)以理解為基礎(chǔ) 善于總結(jié)各種技巧 掌握科學(xué)的組織和推理方法 目錄 1 引言第1章排列與組合1 1加法法則和乘法法則1 2排列1 3組合1 4二項(xiàng)式定理1 5組合恒等式及其含義1 6模型轉(zhuǎn)換本章小結(jié)習(xí)題第2章鴿籠原理2 1鴿籠原理2 2鴿籠原理的推廣2 3Ramsey定理本章小結(jié) 習(xí)題第3章容斥原理3 1容斥原理3 2重集r 組合3 3錯排問題3 4有限制排列3 5 一般有限制排列3 6 廣義容斥原理本章小結(jié)習(xí)題第4章母函數(shù)4 1母函數(shù)的基本概念4 2母函數(shù)的基本運(yùn)算4 3在排列組合中的應(yīng)用4 4在組合恒等式中的應(yīng)用 目錄 基本概念 廣義的組合數(shù)學(xué)就是離散數(shù)學(xué) 離散數(shù)學(xué)是狹義的組合數(shù)學(xué)和圖論 代數(shù)結(jié)構(gòu) 數(shù)理邏輯等的總稱 組合數(shù)學(xué)是一門研究離散對象的科學(xué) 隨著計算機(jī)科學(xué)的日益發(fā)展 組合數(shù)學(xué)的重要性也日漸凸顯 因?yàn)橛嬎銠C(jī)科學(xué)的核心內(nèi)容是使用算法處理離散數(shù)據(jù) 基本概念 狹義的組合數(shù)學(xué)主要研究滿足一定條件的組態(tài) 也稱組合模型 的存在 計數(shù)以及構(gòu)造等方面的問題 組合數(shù)學(xué)的主要內(nèi)容有組合計數(shù) 組合設(shè)計 組合矩陣 組合優(yōu)化等 組合數(shù)學(xué)研究的中心問題是按照一定的規(guī)則來安排有限多個對象 如果人們想把有限多個對象按照它們所應(yīng)滿足的條件來進(jìn)行安排 當(dāng)符合要求的安排并非顯然存在或顯然不存在時 首要的問題就是要證明或者否定它的存在 這就是存在性問題 如果所要求的安排存在 則可能有多種不同的安排 這又經(jīng)常給人們提出這樣的問題 有多少種可能的安排方案 如何對安排的方案進(jìn)行分類 這就是計數(shù)問題 如果一個組合問題有解 則往往需要給出求其某一特定解的算法 這就是所謂的構(gòu)造性問題 如果算法很多 就需要在一定的條件下找出一個或者幾個最優(yōu)或近乎最優(yōu)的安排方案 這就是優(yōu)化問題 組合數(shù)學(xué)中的著名問題 計算一些物品在特定條件下分組的方法數(shù)目 這些是關(guān)于排列 組合和整數(shù)分拆的 地圖著色問題 對世界地圖著色 每一個國家使用一種顏色 如果要求相鄰國家的顏色相異 是否總共只需四種顏色 這是圖論的問題 船夫過河問題 船夫要把一匹狼 一只羊和一棵白菜運(yùn)過河 只要船夫不在場 羊就會吃白菜 狼就會吃羊 船夫的船每次只能運(yùn)送一種東西 怎樣把所有東西都運(yùn)過河 這是線性規(guī)劃的問題 組合數(shù)學(xué)中的著名問題 中國郵差問題 由中國組合數(shù)學(xué)家管梅谷教授提出 郵遞員要穿過城市的每一條路至少一次 怎樣行走走過的路程最短 這不是一個NP完全問題 存在多項(xiàng)式復(fù)雜度算法 先求出度為奇數(shù)的點(diǎn) 用匹配算法算出這些點(diǎn)間的連接方式 然后再用歐拉路徑算法求解 這也是圖論的問題 任務(wù)分配問題 也稱婚配問題 有一些員工要完成一些任務(wù) 各個員工完成不同任務(wù)所花費(fèi)的時間都不同 每個員工只分配一項(xiàng)任務(wù) 每項(xiàng)任務(wù)只被分配給一個員工 怎樣分配員工與任務(wù)以使所花費(fèi)的時間最少 這是線性規(guī)劃的問題 如何構(gòu)作幻方 第1章排列與組合 本章重點(diǎn)介紹以下的基本計數(shù)方法 加法法則和乘法法則排列組合二項(xiàng)式定理的應(yīng)用組合恒等式 相互獨(dú)立的事件A B分別有k和l種方法產(chǎn)生 則產(chǎn)生A或B的方法數(shù)為k l種 1 1加法法則 1 1加法法則和乘法法則 1 1 1加法法則 加法法則 集合論定義 若 A k B l 且A B 則 A B k l 設(shè)S是有限集合 若 且時 則有 1 1加法法則例1 1 1加法法則和乘法法則 1 1 1加法法則 例題 例1 有一所學(xué)校給一名物理競賽優(yōu)勝者發(fā)獎 獎品有三類 第一類是三種不同版本的法漢詞典 第二類是四種不同類型的物理參考書 第三類是二種不同的獎杯 這位優(yōu)勝者只能挑選一樣獎品 那么 這位優(yōu)勝者挑選獎品的方法有多少種 解 設(shè)S是所有這些獎品的集合 Si是第i類獎品的集合 i 1 2 3 顯然 Si Sj i j 根據(jù)加法法則有 1 1加法法則例2 3 1 1加法法則和乘法法則 1 1 1加法法則 例題 例2 大于0小于10的奇偶數(shù)有多少個 例3 小于20可被2或3整除的自然數(shù)有多少個 解 設(shè)S是符合條件數(shù)的集合 S1 S2分別是符合條件的奇數(shù) 偶數(shù)集合 顯然 S1 S2 根據(jù)加法法則有 若 A k B l A B a b a A b B 則 A B k l 1 1乘法法則 1 1加法法則和乘法法則 1 1 2乘法法則 乘法法則 相互獨(dú)立的事件A B分別有k和l種方法產(chǎn)生 則選取A以后再選取B的方法數(shù)為k l種 集合論定義 設(shè)是有限集合 且 則有 1 1乘法法則例4 1 1加法法則和乘法法則 1 1 2乘法法則 例題 例4 從A地到B地有二條不同的道路 從B地到C地有四條不同的道路 而從C地到D地有三條不同的道路 求從A地經(jīng)B C兩地到達(dá)D地的道路數(shù) 解 設(shè)S是所求的道路數(shù)集合 S1 S2 S3分別是從A到B 從B到C 從C到D的道路集合 根據(jù)乘法法則有 1 1乘法法則例5 1 1加法法則和乘法法則 1 1 2乘法法則 例題 例5 由數(shù)字1 2 3 4 5可以構(gòu)成多少個所有數(shù)字互不相同的四位偶數(shù) 解 所求的是四位偶數(shù) 故個位只能選2或4 有兩種選擇方法 又由于要求四位數(shù)字互不相同 故個位選中后 十位只有四種選擇方法 同理 百位 千位分別有三種 兩種選擇方法 根據(jù)乘法法則 四位數(shù)互不相同的偶數(shù)個數(shù)為2 4 3 2 48 1 1乘法法則例6 1 1加法法則和乘法法則 1 1 2乘法法則 例題 例6 求出從8個計算機(jī)系的學(xué)生 9個數(shù)學(xué)系的學(xué)生和10個經(jīng)濟(jì)系的學(xué)生中選出兩個不同專業(yè)的學(xué)生的方法數(shù) 解 由乘法法則有選一個計算機(jī)系和一個數(shù)學(xué)系的方法數(shù)為8 9 72選一個數(shù)學(xué)系和一個經(jīng)濟(jì)系的方法數(shù)為9 10 90選一個經(jīng)濟(jì)系和一個計算機(jī)系的方法數(shù)為10 8 80由加法法則 符合要求的方法數(shù)為72 90 80 242 1 1重集的概念 1 1加法法則和乘法法則 1 1 3計數(shù)問題的分類 有序安排或有序選擇 允許重復(fù) 不允許重復(fù)無序安排或無序選擇 允許重復(fù) 不允許重復(fù) 標(biāo)準(zhǔn)集的特性 確定 無序 相異等 重集 B k1 b1 k2 b2 kn bn 其中 bi為n個互不相同的元素 稱ki為bi的重數(shù) i 1 2 n n 1 2 ki 1 2 重集的概念 1 2線排列 1 2排列 定義1 1 1 2 1線排列 集合論定義 定理1 1 從n個不同元素中 取r個 0 r n 按一定順序排列起來 其排列數(shù)P n r 設(shè)A an 從A中選擇r個 0 r n 元素排列起來 A的r 有序子集 A的r 排列 如n r Z且n r 0 P n r n n r 如n r 稱全排列P n n n 如n r P n r 0 如r 0 P n r 1 證明 構(gòu)造集合A的r 排列時 可以從A的n各元素中任選一個作為排列的第一項(xiàng) 有n種選法 第一項(xiàng)選定后從剩下的n 1個元素中選排列的第二項(xiàng)有n 1種選法 由此類推 第r項(xiàng)有n r 1種選法 根據(jù)乘法法則有 1 2線排列推論1 1 2排列 1 2 1線排列 兩個推論 推論1 1 1 如n r N且n r 2 則P n r n P n 1 r 1 證明 在集合A的n個元素中 任一個元素都可以排在它的r 排列首位 故首位有n種取法 首位取定后 其他位置的元素正好是從A的另n 1個元素中取r 1個的排列 因此有P n 1 r 1 種取法 由乘法法則有P n r n P n 1 r 1 證畢 1 2線排列推論2 1 2排列 1 2 1線排列 兩個推論 推論1 1 1 如n r N且n r 2 則P n r n P n 1 r 1 推論1 1 2 如n r N且n r 2 則P n r r P n 1 r 1 P n 1 r 證明 當(dāng)r 2時 把集合A的r 排列分為兩大類 一類包含A中的某個固定元素 不妨設(shè)為a1 另一類不包含a1 第一類排列相當(dāng)于先從A a1 中取r 1個元素進(jìn)行排列 有P n 1 r 1 種取法 再將a1放入每一個上述排列中 對任一排列 a1都有r種放法 由乘法法則 第一類排列共有r P n 1 r 1 個 第二類排列實(shí)質(zhì)上是A a1 的r 排列 共有P n 1 r 個 再由加法法則有P n r r P n 1 r 1 P n 1 r 證畢 1 2線排列例1 1 2排列 1 2 1線排列 例題 例1 由數(shù)字1 2 3 4 5可以構(gòu)成多少個所有數(shù)字互不相同的四位數(shù) 解 由于所有的四位數(shù)字互不相同 故每一個四位數(shù)就是集合 1 2 3 4 5 的一個4 排列 因而所求的四位數(shù)個數(shù)為 1 2線排列例2 1 2排列 1 2 1線排列 例題 例2 將具有9個字母的單詞FRAGMENTS進(jìn)行排列 要求字母A總是緊跟在字母R的右邊 問有多少種這樣的排法 如果再要求字母M和N必須相鄰呢 解 由于A總是R的右邊 故這樣的排列相當(dāng)于是8個元素的集合 F RA G M E N T S 的一個全排列 個數(shù)為如果再要求M和N必須相鄰 可先把M和N看成一個整體 M N 進(jìn)行7個元素的集合 F RA G E T S 的全排列 在每一個排列中再進(jìn)行 M N 的全排列 由乘法法則 排列個數(shù)為 1 2線排列例3 1 2排列 1 2 1線排列 例題 例3 有多少個5位數(shù) 每位數(shù)字都不相同 不能取0 且數(shù)字7和9不能相鄰 解 由于所有的5位數(shù)字互不相同 且不能取0 故每一個5位數(shù)就是集合 1 2 9 的一個5 排列 其排列數(shù)為P 9 5 其中7和9相鄰的排列數(shù)為 c 7 3 4 2 4 2 P 7 3 滿足題目要求的5位數(shù)個數(shù)為 1 2圓排列 1 2排列 定義1 2 1 2 2圓排列 定理1 2 設(shè)A an 從A中取r個 0 r n 元素按某種順序 如逆時針 排成一個圓圈 稱為圓排列 循環(huán)排列 設(shè)A an A的r圓排列個數(shù)為P n r r 證明 由于把一個圓排列旋轉(zhuǎn)所得到另一個圓排列視為相同的圓排列 因此線排列a1a2 ar a2a3 ara1 ara1a2 ar 1在圓排列中是一個 即一個圓排列可產(chǎn)生r個不同的線排列 同理 r個不同的線排列對應(yīng)一個圓排列 而總共有P n r 個線排列 故圓排列的個數(shù)為P n r r n r n r 證畢 1 2圓排列例4 1 2排列 例題 1 2 2圓排列 例4 有8人圍圓桌就餐 問有多少種就座方式 如果有兩人不愿坐在一起 又有多少種就座方式 解 由上述定理知8人圍圓桌就餐 有8 8 7 5040種就座方式 又有兩人不愿坐在一起 不妨設(shè)此二人為A B 當(dāng)A B坐在一起時 相當(dāng)于7人圍圓桌就餐 有7 7 6 種就座方式 而A B坐在一起時 又有兩種情況 或者A在B的左面 或者A在B的右面 因此A B坐在一起時 共有2 6 種就座方式 因此如果有兩人不愿坐在一起 就座方式為7 2 6 5 6 3600 1 2圓排列例5 1 2排列 例題 1 2 2圓排列 例5 4男4女圍圓桌交替就座有多少種就座方式 解 顯然 這是一個圓排列問題 首先讓4個男的圍圓桌就座 有4 4 3 種就座方式 因?yàn)橐竽信畤鷪A桌交替就座 在男的坐定后 兩兩之間均需留有一個空位 女的就座相當(dāng)于一個4元素集合的全排列 就座方式數(shù)為4 由乘法法則知 就座方式數(shù)為3 4 144 1 2重排列 1 2排列 定義1 3 1 2 3重排列 集合論定義 定理1 3 從n個不同元素中 可重復(fù)選取r個按一定順序排列起來 稱為重排列 從重集B k1 b1 k2 b2 kn bn 中選取r個按一定順序排列起來 重集B b1 b2 bn 的r 排列的個數(shù)為nr 證明 構(gòu)造B的r 排列如下 選擇第一項(xiàng)時可從n個元素中任選一個 有n種選法 選擇第二項(xiàng)時由于可以重復(fù)選取 仍有n種選法 同理 選擇第r項(xiàng)時仍有n種選法 根據(jù)乘法法則 可得出r 排列的個數(shù)為nr 證畢 1 2重排列例6 1 2排列 例題 1 2 3重排列 例6 由數(shù)字1 2 3 4 5 6這六個數(shù)字能組成多少個五位數(shù) 又可組成多少大于34500的五位數(shù) 解 一個五位數(shù)的各位數(shù)字可重復(fù)出現(xiàn) 是一個典型的重排列問題 相當(dāng)于重集B 1 2 6 的5 排列 所求的五位數(shù)個數(shù)為65 7776 大于34500的五位數(shù)可由下面三種情況組成 萬位選4 5 6中的一個 其余4位相當(dāng)于重集B的4 排列 由乘法法則知 共有3 64個五位數(shù) 萬位是3 千位5 6中的一個 其余3位相當(dāng)于重集B的3 排列 由乘法法則知 共有2 63個五位數(shù) 萬位是3 千位4中的一個 百位選5 6中的一個 其余2位相當(dāng)于重集B的2 排列 由乘法法則知 共有2 62個五位數(shù) 由加法法則知 大于34500的五位數(shù)個數(shù)為3 64 2 63 2 62 4392 1 2重排列計數(shù) 1 2排列 1 2 3重排列 定理1 4 重集B n1 b1 n2 b2 nk bk 的全排列個數(shù)為 證明 將B中的ni個bi看作不同的ni個元素 賦予上標(biāo)1 2 ni 即 如此 重集B就變成具有n1 n2 nk n個不同的元素集合顯然 集合A的全排列個數(shù)為n 又由于ni個bi賦予上標(biāo)的方法有ni 種 于是對重集B的任一個全排列 都可以產(chǎn)生集合A的n1 n2 nk 個排列 由乘法法則 故重集B的全排列個數(shù)為證畢 注 利用組合數(shù)的計數(shù)方法同樣可以得出證明 1 2重排列例7 1 2排列 1 2 3重排列 例題 例6 有四面紅旗 三面藍(lán)旗 二面黃旗 五面綠旗可以組成多少種由14面旗子組成的一排彩旗 解 這是一個重排列問題 是求重集 4 紅旗 3 藍(lán)旗 2 黃旗 5 綠旗 的全排列個數(shù) 根據(jù)定理 一排彩旗的種數(shù)為 1 2重排列例8 1 2排列 1 2 3重排列 例題 例8 用字母A B C組成五個字母的符號 要求在每個符號里 A至多出現(xiàn)2次 B至多出現(xiàn)1次 C至多出現(xiàn)3次 求此類符號的個數(shù) 解 這也是一個重排列問題 根據(jù)分析 符合題意的符號個數(shù)相當(dāng)于求重集M 2 A 1 B 3 C 的5 排列個數(shù) 可分為三種情況 需要分別求M A M B 和M C 的全排列個數(shù) 根據(jù)加法法則 此類符號個數(shù)為 1 2項(xiàng)鏈排列 1 2排列 定義1 4 1 2 4項(xiàng)鏈排列 對圓排列 通過轉(zhuǎn)動 平移 翻轉(zhuǎn) 可重合的 即可看作項(xiàng)鏈排列 如n個不同元素的r 項(xiàng)鏈排列個數(shù)為P n r 2 r 具體參照P lya定理 1 3無重組合 1 3組合 定義1 5 1 3 1 無重 組合 集合論定義 定理1 5 設(shè)A an 從A中選擇r個 0 r n 元素組合起來 A的r 無序子集 A的r 組合 如r n 有C n r P n r r n r n r 如n r 0 C n r 1 如n r C n r 0 從n個不同元素中 取r個 0 r n 不考慮順序組合起來 其組合數(shù)C n r 或 證明 從n個不同元素中取r個元素的組合數(shù)為C n r 而r個元素可組成r 個r 排列 即一個r 組合對應(yīng)r 個r 排列 于是C n r 個r 組合對應(yīng)r C n r 個r 排列 這是從n個不同元素中取r個元素的r 排列數(shù)P n r 因此有 1 3無重組合推論1 1 3組合 1 3 1 無重 組合 三個推論 推論1 5 1 C n r C n n r 證明 實(shí)際上 從n個不同元素中選出r個元素的同時 就有n r個元素沒有被選出 因此選出r個元素的方式數(shù)等于選出n r個元素的方式數(shù) 即C n r C n n r 得證 另外 也可通過計算得出證明如下 1 3無重組合推論2 1 3組合 1 3 1 無重 組合 三個推論 推論1 5 1 C n r C n n r 推論1 5 2 Pascal公式 C n r C n 1 r C n 1 r 1 證明 利用組合分析法 在集合A的n個不同元素中固定一個元素 不妨設(shè)為a1 從n個元素中選出r個元素的組合由下面兩種情況組成 r個元素中包含a1 相當(dāng)于從除去a1的n 1個元素中選出r 1個元素的組合 再加上a1而得到 組合數(shù)為C n 1 r 1 r個元素中不包含a1 相當(dāng)于從除去a1的n 1個元素中選出r個元素的組合而得到 組合數(shù)為C n 1 r 由加法法則即得C n r C n 1 r C n 1 r 1 另外 也可通過計算得出證明如下 1 3無重組合推論3 1 3組合 1 3 1 無重 組合 三個推論 推論1 5 1 C n r C n n r 推論1 5 2 Pascal公式 C n r C n 1 r C n 1 r 1 推論1 5 3 C n r C n 1 r 1 C n 2 r 1 C r 1 r 1 證明 反復(fù)利用Pascal公式 即可證明 或利用組合分析法 在集合A an 的n個不同元素選出r個元素的組合可分為以下多種情況 如r個元素中包含a1 相當(dāng)于從除去a1的n 1個元素中選出r 1個元素的組合 再加上a1而得到 組合數(shù)為C n 1 r 1 如r個元素中不包含a1但包含a2 相當(dāng)于從除去a1 a2的n 2個元素中選出r 1個元素的組合 再加上a2而得到 組合數(shù)為C n 2 r 1 同理如r個元素中不包含a1 a2 an r 但包含an r 1 相當(dāng)于從剩下的r 1個元素中選出r 1個元素的組合 再加上an r 1而得到 組合數(shù)為C r 1 r 1 由加法法則得C n r C n 1 r 1 C n 2 r 1 C r 1 r 1 1 3無重組合例1 1 3組合 1 3 1 無重 組合 例題 例1 有5本日文書 7本英文書 10本中文書 從中取兩本不同文字的書 問有多少種方案 若取兩本相同文字的書 問有多少種方案 任取兩本書 有多少種方案 解 從三種文字的書中取兩種共有C 3 2 3種取法 根據(jù)乘法法則有 日英各一本的方法數(shù)為5 7 35 中英各一本的方法數(shù)為10 7 70 中日各一本的方法數(shù)為10 5 50 由加法法則得35 70 50 155取兩本相同文字的 有兩本中文 兩本英文或兩本日文三種方式 由加法法則得C 5 2 C 7 2 C 10 2 76任取兩本書 相當(dāng)于從5 7 10 22本書中取兩本的組合 即C 22 2 231 1 3無重組合例2 1 3組合 1 3 1 無重 組合 例題 例2 從1 300之間任取3個不同的數(shù) 使得這3個數(shù)的和正好被3除盡 問共有幾種方案 解 所有的整數(shù)可分為以下3個分類 模3余0 模3余1和模3余2 故1 300的300個數(shù)可以分為3個集合 A 1 4 298 B 2 5 299 C 3 6 300 任取3個數(shù)其和正好被3整除的情況如下 三個數(shù)同屬于集合A 有C 100 3 種方案 三個數(shù)同屬于集合B 有C 100 3 種方案 三個數(shù)同屬于集合C 有C 100 3 種方案 三個數(shù)分別屬于集合A B C 由乘法法則有1003種方案 由加法法則得 所求的方案數(shù)為3 C 100 3 1003 1485100 1 3無重組合例3 1 3組合 1 3 1 無重 組合 例題 例3 某車站有1到6個入口處 每個入口處每次只能進(jìn)一個人 問一小組9個人進(jìn)站的方案數(shù)有多少 解I 按照從入口1到入口6的順序可得到9個人一個排列 再把兩個入口間設(shè)上一個標(biāo)志 加上這5個標(biāo)志相當(dāng)于每一個排列有14個元素 其中5個標(biāo)志沒有區(qū)別 但其位置將區(qū)分各入口的進(jìn)站人數(shù) 相當(dāng)于14個元素集合的5 組合 故進(jìn)站方案數(shù)為9 C 14 5 726485760解II 同上分析 問題轉(zhuǎn)化為重集 1 p1 1 p2 1 p9 5 標(biāo)志 的全排列 pi代表9個人 i 1 9 故進(jìn)站方案數(shù)為14 5 726485760解III 考慮9個人選擇方案 第1個人有6種選擇 第2個人除了選擇入口 還要考慮在第1個人的前面或后面 故有7種選擇 同理 第9個人有14種選擇 根據(jù)乘法法則 故進(jìn)站方案數(shù)為6 7 14 726485760 1 3無重組合例4 1 3組合 1 3 1 無重 組合 例題 例4 求5位數(shù)中至少出現(xiàn)一個6 而被3整除的數(shù)的個數(shù) 解 10進(jìn)制數(shù)被3整除的充要條件是各位數(shù)的和能被3整除 據(jù)此可進(jìn)行如下討論 從左往右計 如最后一個6出現(xiàn)在個位 則十百千位各有10種選擇 萬位有3種可能 根據(jù)乘法法則 總個數(shù)為3 103 如最后一個6出現(xiàn)在十位 則個位有9種選擇 百千位各有10種選擇 萬位有3種可能 根據(jù)乘法法則 總個數(shù)為3 102 9 如最后一個6出現(xiàn)在百位 則個十位各有9種選擇 千位有10種選擇 萬位有3種可能 根據(jù)乘法法則 總個數(shù)為3 10 92 如最后一個6出現(xiàn)在千位 則個十百位各有9種選擇 萬位有3種可能 根據(jù)乘法法則 總個數(shù)為3 93 如最后一個6出現(xiàn)在萬位 則個十百位各有9種選擇 千位有3種可能 根據(jù)乘法法則 總個數(shù)為3 93 根據(jù)加法法則 符合條件的整數(shù)個數(shù)為3 103 3 102 9 3 10 92 3 93 3 93 12504 1 3無重組合例5 1 3組合 1 3 1 無重 組合 例題 例5 求1000 的末尾有幾個零 解 此問題在于求將1000 分解為素數(shù)的乘積時 2和5的冪是多少 末尾零的個數(shù)應(yīng)該等于2和5的冪中較小的那個數(shù) 1 1000中5的倍數(shù)的數(shù)共200個 其中有40個52的倍數(shù) 這40個數(shù)中有8個53的倍數(shù) 而這8個數(shù)中又有1個54的倍數(shù) 故1000 分解為素數(shù)的乘積時 5的冪應(yīng)該是200 40 8 1 249顯然 2的冪必然大于249 因此1000 的末尾有249個零 1 3無重組合例6 1 3組合 1 3 1 無重 組合 例題 例6 求能除盡1400的正整數(shù)數(shù)目 1除外 其中包含多少個奇數(shù) 解 1400 23527 故除盡1400的正整數(shù)分解為素數(shù)的乘積的形式應(yīng)該為2l5m7n 其中0 l 3 0 m 2 0 n 1 但應(yīng)排除l m n 0的情況 故滿足條件的數(shù)目為 3 1 2 1 1 1 1 23其中包含的奇數(shù)為 1 2 1 1 1 1 5 1 3重復(fù)組合 1 3組合 定義1 6 1 3 2重復(fù)組合 集合論定義 定理1 6 從n個不同元素中 可重復(fù)選取r個不考慮順序組合起來 其組合數(shù)F n r 從重集B k1 b1 k2 b2 kn bn 中取r個元素不考慮順序的組合 重集B b1 b2 bn 的r 組合數(shù)F n r C n r 1 r 證明 設(shè)n個元素b1 b2 bn和自然數(shù)1 2 n一一對應(yīng) 于是任何組合皆可看作是一個r個數(shù)的組合 c1 c2 cr 由于是組合 不妨認(rèn)為各ci是按照大小順序排列的 相同的ci連續(xù)排在一起 不妨設(shè)c1 c2 cr 又令di ci i 1 i 1 2 r 即d1 c1 d2 c2 1 dr cr r 1 因1 ci n 故1 di n r 1 得到一個集合 1 2 n r 1 的r 組合 d1 d2 dr d1 d2 dr 顯然有一種 c1 c2 cr 的取法 就有一種 d1 d2 dr 的取法 反之亦然 這兩種取法是一一對應(yīng)的 從而這兩種取法是等價的 如此 從n個不同元素中可重復(fù)選取r個的組合數(shù) 和從n r 1個不同元素中不重復(fù)選取r個的組合數(shù)是相同的 故F n r C n r 1 r 1 3重復(fù)組合例7 1 3組合 定理1 7 1 3 2重復(fù)組合 例題 r個無區(qū)別的球放入n個有標(biāo)志的盒子里 每盒的球數(shù)可多于1個 則共有F n r 種方案 例7 試問 x y z 4的展開式有多少項(xiàng) 證明 這是一個允許重復(fù)組合的典型問題 實(shí)質(zhì)上定理1 6的另一種說法 由于每盒的球數(shù)不受限制 相當(dāng)于重集 a1 a2 an 的r 組合 解 x y z 4展開式每一項(xiàng)都是4次方的 相當(dāng)于從3個不同元素中可以重復(fù)的選擇4個 或者相當(dāng)于將4個無區(qū)別的球放到3個有標(biāo)志的盒子里 故展開項(xiàng)個數(shù)為F 3 4 C 3 4 1 4 15 1 3重復(fù)組合例8 9 1 3組合 例題 1 3 2重復(fù)組合 例8 某餐廳有7種不同的菜 為了招待朋友 一個顧客需要買14個菜 問有多少種買法 例9 求n個無區(qū)別的球放入r個有標(biāo)志的盒子里 n r 而無一空盒的方案數(shù) 解 這個問題相當(dāng)于重集 1 2 7 的14 組合 根據(jù)定理1 6知買菜的方法數(shù)為F 7 14 C 7 14 1 14 4845 解 由于每個盒子不能為空 故每個盒子里可先放一個球 這樣還剩n r個球 再將這n r個球防到r個盒子里 由于這時每盒的球數(shù)不受限制 相當(dāng)于重集 a1 a2 ar 的n r 組合 根據(jù)定理1 6知 其組合數(shù)為F r n r C r n r 1 n r C n 1 r 1 1 3重復(fù)組合例10 1 3組合 例題 1 3 2重復(fù)組合 例10 在由數(shù)0 1 9組成的r位整數(shù)所組成的集合中 如果將一個整數(shù)重新排列得到另一個整數(shù) 則稱這兩個整數(shù)是等價的 那么 有多少不等價的整數(shù) 如果0和9最多只能出現(xiàn)一次 又有多少不等價的整數(shù) 解 分析題意知 一個r位整數(shù)只和所取的數(shù)字有關(guān) 與其順序無關(guān) 因而是個組合問題 又每一整數(shù)的每一位可從0 1 9中任取 故不等價的r位整數(shù)相當(dāng)于重集 0 1 9 的r 組合 根據(jù)定理1 6知 其組合數(shù)為F 10 r C 10 r 1 r C 9 r r 0和9最多只出現(xiàn)一次 可分為三種情況 均不出現(xiàn)時相當(dāng)于重集B 1 2 8 的r 組合 組合數(shù)為F 8 r C r 7 r 只出現(xiàn)其一 若0出現(xiàn) 相當(dāng)于B的r 1 組合 然后加入0 組合數(shù)為F 8 r 1 C r 6 r 1 同理9出現(xiàn)的組合數(shù)為C r 6 r 1 均出現(xiàn)一次 相當(dāng)于B的r 2 組合 然后加入0 9 組合數(shù)為F 8 r 2 C r 5 r 2 由加法法則知 符合題意的整數(shù)個數(shù)為C r 7 r 2 C r 6 r 1 C r 5 r 2 1 3重復(fù)組合例11 1 3組合 例題 1 3 2重復(fù)組合 例11 求方程x1 x2 xn r的非負(fù)整數(shù)解的個數(shù) 其中n r為正整數(shù) 解 設(shè)重集B b1 b2 bn B的任一個r 組合都具有形式 x1 b1 x2 b2 xn bn 其中xi i 1 2 n 是非負(fù)整數(shù)且滿足方程x1 x2 xn r 反之 每一個滿足方程x1 x2 xn r的非負(fù)整數(shù)解x1 x2 xn都對應(yīng)重集B的一個r 組合 因此 方程x1 x2 xn r的非負(fù)整數(shù)解的個數(shù)就等于重集B的r 組合數(shù)F n r 1 3不相鄰組合 1 3組合 3 1 3組合 定義1 7 1 3 3不相鄰組合 定理1 8 從序列A 1 2 n 個中選取r個 其中不存在i i 1兩個相鄰的數(shù)同時出現(xiàn)于一個組合的組合 從序列A 1 2 n 個中選取r個作不相鄰的組合 其組合數(shù)為C n r 1 r 證明 設(shè) d1 d2 dr 是所求的一個不相鄰組合 不妨設(shè)d1 d2 dr 令ci di i 1 i 1 2 r 即c1 d1 c2 d2 1 cr dr r 1 因1 di n 故1 ci n r 1 得到一個集合 1 2 n r 1 的r 組合 顯然有一種 d1 d2 dr 的取法 就有一種 c1 c2 cr 的取法 反之亦然 集合 1 2 n r 1 的一個r 組合 c1 c2 cr 不妨設(shè)c1 c2 cr 令di ci i 1 i 1 2 r 即d1 c1 d2 c2 1 dr cr r 1 因1 ci n r 1 故1 di n 得到一個集合 1 2 n 的不相鄰組合 d1 d2 dr 顯然有一種 c1 c2 cr 的取法 就有一種 d1 d2 dr 的取法 故這兩種取法是一一對應(yīng)的 從而這兩種取法是等價的 從n個不同元素中可選取r個的不相鄰組合數(shù) 和從n r 1個不同元素中選取r個的組合數(shù)是相同的 即C n r 1 r 1 4二項(xiàng)式定理 1 4二項(xiàng)式定理 定理1 9 證明 因?yàn)?x y n x y x y x y 等式右端有n個因子 項(xiàng)xkyn k是從這n個因子中選取k個因子 k 0 1 n 在這k個 x y 里都取x 而從剩下的n k個因子 x y 中選取y作乘積得到 因此xkyn k的系數(shù)為上述選法的個數(shù)C n r 故有證畢 注 可用數(shù)學(xué)歸納法證明 證明略 C n k 又稱二項(xiàng)式系數(shù) 1 4二項(xiàng)式定理推論1 1 4二項(xiàng)式定理 四個推論 推論1 9 1 推論1 9 2 推論1 9 3 證明 在推論1 9 2中令x 1 即可得證 利用組合分析 等式左端相當(dāng)于從A an 中任意選擇k 0 k n 個元素的所有可能數(shù)目 即對n個元素 每一個都有被選擇和不被選擇的可能 總的可能數(shù)為2n 另外 該等式還表明A的所有子集個數(shù)為2n 1 4二項(xiàng)式定理推論2 1 4二項(xiàng)式定理 四個推論 推論1 9 1 推論1 9 2 推論1 9 3 推論1 9 4 證明 在推論1 9 2中令x 1 即可得證 另外 該等式還表明A an 的偶數(shù)子集個數(shù)和奇數(shù)子集個數(shù)相等 1 4廣義二項(xiàng)式定理 1 4二項(xiàng)式定理 定理1 10 定義1 8 廣義二項(xiàng)式系數(shù)為 牛頓二項(xiàng)式定理 1 4廣義二項(xiàng)式定理推論1 1 4二項(xiàng)式定理 六個推論 推論1 10 1 推論1 10 2 證明 1 4廣義二項(xiàng)式定理推論2 1 4二項(xiàng)式定理 六個推論 推論1 10 1 推論1 10 2 推論1 10 3 推論1 10 4 推論1 10 5 證明 當(dāng) 1 2時 C 0 1 而對于k 0 有將上式代入推論1 10 1即可得證 1 4廣義二項(xiàng)式定理推論3 1 4二項(xiàng)式定理 六個推論 推論1 10 1 推論1 10 2 推論1 10 3 推論1 10 4 推論1 10 5 推論1 10 6 1 5組合恒等式及其含義1 1 5組合恒等式及其含義 恒等式1 如n k N 有C n k n k C n 1 k 1 證明 從n個元素中取k個的組合可先從n個元素中取1個 再從剩下的n 1個元素中選擇k 1個 組合數(shù)為C n 1 k 1 選出的k個元素都有可能被第一次選中 因是組合 故重復(fù)度為k 得證 或通過計算證明 1 5組合恒等式及其含義2 1 5組合恒等式及其含義 恒等式2 證明 考慮盒子1中有n個有區(qū)別的球 從中取一個球放入盒子2中 再取任意多個球放入盒子3中 等式左端表示先從盒子1中取k k 1 2 n 個球 再從中取一個放入盒子2中 剩下的k 1個球放入盒子3中 等式右端表示先從盒子1中取一個放入盒子2中 剩下的n 1個球是否放入盒子3中均有兩種可能 顯然兩種取法結(jié)果是一樣的 得證 或通過計算證明 1 5組合恒等式及其含義3 1 5組合恒等式及其含義 恒等式3 證明 將等式兩邊對x微分得在上式中 令x 1得即得證 注 如令x 1 即可證明恒等式2 1 5組合恒等式及其含義4 5 1 5組合恒等式及其含義 恒等式5 恒等式4 證明 將等式兩邊對x微分得將等式兩邊同乘以x后再對x微分得在上式中 令x 1得得證 注 如令x 1 即可證明恒等式5 1 5組合恒等式及其含義6 1 5組合恒等式及其含義 恒等式6 證明 將等式兩邊對x從0到1積分得即得證 恒等式7 Vandermonde恒等式 如n m N且r min m n 有C m n r C m 0 C n r C m 1 C n r 1 C m r C n 0 1 5組合恒等式及其含義7 1 5組合恒等式及其含義 證明 設(shè)A am B bn 且A B 則A B C有m n個元素 C的r 組合個數(shù)為C m n r 而C的每個r 組合無非是先從A中取k個元素 再從B中取出r k個元素組成 k 0 1 r 由乘法法則共有C m k C n r k 種取法 再由加法法則即可得證 或通過比較系數(shù)法證明 比較等式兩邊xr的系數(shù)即可得證 1 5組合恒等式及其含義8 9 1 5組合恒等式及其含義 恒等式8 恒等式9 恒等式7 Vandermonde恒等式 如n m N且r min m n 有C m n r C m 0 C n r C m 1 C n r 1 C m r C n 0 1 5組合恒等式及其含義10 11 1 5組合恒等式及其含義 恒等式10 如p q n Z且p q n 0 有 恒等式11 如p q n Z且p q n 0 有 1 5組合恒等式及其含義12 1 5組合恒等式及其含義 恒等式12 證明 利用組合分析法 在集合A an 1 的n 1個不同元素選出k 1個元素的組合可分為以下多種情況 如k 1個元素中包含a1 相當(dāng)于從除去a1的n個元素中選出k個元素的組合 組合數(shù)為C n k 如不包含a1但包含a2 相當(dāng)于從除去a1 a2的n 1個元素中選出k個元素的組合 再加上a2而得到 組合數(shù)為C n 1 k 同理如不包含a1 a2 an k 1 但包含an k 2 相當(dāng)于從剩下的k個元素中選出k個元素的組合 再加上an k 2而得到 組合數(shù)為C k k 注意 i k時 C k k 0 由加法法則得或?qū)潭ǖ膋 對n使用歸納法 當(dāng)n 0時 有可見 當(dāng)n 0時 等式成立 如對任意n等式成立 則有可見等式對n 1也成立 由歸納原理 得證 1 5組合恒等式及其含義13 1 5組合恒等式及其含義 恒等式13 證明 注意 這個恒等式與前面的有一個很不一樣的地方 就是C j j C k 1 k 是廣義的二項(xiàng)式系數(shù) 根據(jù)廣義的二項(xiàng)式系數(shù)的定義 Pascal公式C k C 1 k C 1 k 1 對實(shí)數(shù) 和整數(shù)k同樣成立 與恒等式1類似 反復(fù)使用Pascal公式即可得證 1 5組合恒等式及其含義14 1 1 5組合恒等式及其含義 恒等式14 如n r N 有C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 證明I 反復(fù)利用Pascal公式 即可證明 或利用組合分析法 在集合A an r 1 的n r 1個不同元素選出r個元素的組合可分為以下多種情況 如r個元素中不包含a1 相當(dāng)于從除去a1的n r個元素中選出r個元素的組合 組合數(shù)為C n r r 如r個元素中包含a1但不包含a2 相當(dāng)于從除去a1 a2的n r 1個元素中選出r 1個元素的組合 再加上a1而得到 組合數(shù)為C n r 1 r 1 同理如r個元素中包含a1 a2 ar 1 但不包含ar 相當(dāng)于從剩下的n 1個元素中選出1個元素的組合 再加上a1 a2 ar 1而得到 組合數(shù)為C n 1 1 如r個元素中包含a1 a2 ar 相當(dāng)于從剩下的n個元素中選出0個元素的組合 組合數(shù)為C n 0 由加法法則得C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 1 5組合恒等式及其含義14 2 1 5組合恒等式及其含義 恒等式14 如n r N 有C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 證明II 等式的左端可看作是在集合A an 2 的n 2個不同元素允許重復(fù)的選出r個元素的組合 可分為以下多種情況 如r個元素中不包含a1 相當(dāng)于從除去a1的n 1個元素中允許重復(fù)的選出r個元素的組合 組合數(shù)為C n r r 如r個元素中只包含一個a1 相當(dāng)于從除去a1的n 1個元素中允許重復(fù)的選出r 1個元素的組合 再加上a1而得到 組合數(shù)為C n r 1 r 1 如r個元素中包含兩個a1 相當(dāng)于從除去a1的n 1個元素中允許重復(fù)的選出r 2個元素的組合 再加上兩個a1而得到 組合數(shù)為C n r 2 r 2 同理如r個元素中包含r個a1 其組合數(shù)為C n 0 由加法法則得C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 1 5組合恒等式及其含義15 1 5組合恒等式及其含義 恒等式15 如n l r N l r 有C n l C l r C n r C n r l r 證明 等式的左端可看作是先從n個元素中取l個的組合 從所得的l個元素中再選擇r個組合 由此形成了三個組合 所得的全部結(jié)果相當(dāng)于直接從n個元素中取r個的組合 再從剩下的n r個元素中選擇l r個 得證 或通過計算證明 1 5組合恒等式證明方法 1 5組合恒等式及其含義 常用的證明方法 數(shù)學(xué)歸納法二項(xiàng)式系數(shù)公式 特別是Pascal公式比較級數(shù)展開式中的系數(shù) 二項(xiàng)式定理或母函數(shù)法 積分微分法組合分析法 1 6模型轉(zhuǎn)換方法 1 6模型轉(zhuǎn)換 問題的分析注意事項(xiàng) 分析對象屬性合理分類明確分步模型轉(zhuǎn)換 如排列 組合 一一對應(yīng) 計數(shù)的難易程度方式的轉(zhuǎn)換1 11 一組 等價 1 6模型轉(zhuǎn)換例1 1 6模型轉(zhuǎn)換 例題 例1 在100名選手之間進(jìn)行淘汰賽 即一場的比賽結(jié)果 失敗者退出比賽 最后產(chǎn)生一名冠軍 問要舉行幾場比賽 證明 第1輪要進(jìn)行50場比賽 留下50名選手 第2輪要進(jìn)行25場比賽 留下25名選手 第3輪要進(jìn)行25場比賽 1名輪空 留下13名選手 第4輪要進(jìn)行6場比賽 1名輪空 留下7名選手 第5輪要進(jìn)行3場比賽 1名輪空 留下4名選手 第6輪要進(jìn)行2場比賽 留下2名選手 最后一場決賽 產(chǎn)生1名冠軍 根據(jù)加法法則 共需要進(jìn)行50 25 12 6 3 2 1 99場比賽 其實(shí) 最后產(chǎn)生1名冠軍需要淘汰99人 一場比賽淘汰1人 兩者一一對應(yīng) 需要99場比賽進(jìn)行 1 6模型轉(zhuǎn)換例2 1 1 6模型轉(zhuǎn)換 格路問題 例2 簡單格路問題從 0 0 點(diǎn)出發(fā)沿X軸或Y軸的正方向每步走一個單位 最終走到 m n 點(diǎn) 有多少條路徑 解 設(shè)從 0 0 點(diǎn)水平方向向前進(jìn)一步為x 垂直方向向上進(jìn)一步為y 于是從 0 0 點(diǎn)到 m n 點(diǎn) 水平方向走m步 垂直方向走n步 一條從 0 0 點(diǎn)到 m n 點(diǎn)的路徑與重集 m x n y 的一個全排列一一對應(yīng) 故所求路徑數(shù)為 m n m n C m n m 另外 垂直方向需要走n步 相當(dāng)于在X軸0 1 m共m 1個端點(diǎn)處重復(fù)的選擇n個位置向上走 與一條從 0 0 點(diǎn)到 m n 點(diǎn)的路徑一一對應(yīng) 故所求路徑數(shù)為F m 1 n C m n n 1 6模型轉(zhuǎn)換例2 2 1 6模型轉(zhuǎn)換 格路問題 另外 一條從 0 0 點(diǎn)到 m n 點(diǎn)的路徑可分為兩類情況 一種是從 0 0 點(diǎn)到 m n 1 點(diǎn)的路徑 另一種是從 0 0 點(diǎn)到 m 1 n 1 點(diǎn)的路徑 根據(jù)上述結(jié)論 有C m n n C m n 1 m C m n 1 m 1 這是Pascal公式的另一種形式 例2 簡單格路問題從 0 0 點(diǎn)出發(fā)沿X軸或Y軸的正方向每步走一個單位 最終走到 m n 點(diǎn) 有多少條路徑 1 6模型轉(zhuǎn)換例3 1 6模型轉(zhuǎn)換 格路問題 證明 這是上一小節(jié)的組合恒等式 等式左端表示從 0 0 點(diǎn)到 n 1 r 點(diǎn)的路徑數(shù) 右端第1項(xiàng)表示從 0 0 點(diǎn)到 n r 點(diǎn)的路徑數(shù) 右端第2項(xiàng)表示從 0 0 點(diǎn)到 n r 1 點(diǎn)的路徑數(shù) 右端最后1項(xiàng)表示從 0 0 點(diǎn)到 n 0 點(diǎn)的路徑數(shù) 這說明從 0 0 點(diǎn)到 n 1 r 點(diǎn)的路徑根據(jù)是否經(jīng)過 n i 到 n 1 i i 0 1 r 可分為r 1類 根據(jù)加法法則即可得證 例3 如n r N 有C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 1 6模型轉(zhuǎn)換例4 1 6模型轉(zhuǎn)換 格路問題 例4 如n N 有C n 0 C n 1 C n n 2n 組合含義 這是推論1 9 3 等式左端第1項(xiàng)表示從 0 0 點(diǎn)到P 0 n 點(diǎn)的路徑數(shù) 第2項(xiàng)表示從 0 0 點(diǎn)到P1 1 n 1 點(diǎn)的路徑數(shù) 左端最后1項(xiàng)表示從 0 0 點(diǎn)到Q n 0 點(diǎn)的路徑數(shù) 這說明從 0 0 點(diǎn)到PQ上各格子點(diǎn)的路徑總和為2n 也說明2n個人從 0 0 點(diǎn)出發(fā) 每到一個十字路口便分成兩組 直至到達(dá)PQ線為止 能保證每個人所走的路徑不同 1 6模型轉(zhuǎn)換例5 1 6模型轉(zhuǎn)換 格路問題 例5 Vandermonde恒等式如n m N r min m n 有C m n r C m 0 C n r C m 1 C n r 1 C m r C n 0 證明 等式左端表示從 0 0 點(diǎn)到 m n r r 點(diǎn)的路徑數(shù) 從 0 0 點(diǎn)到 m n r r 點(diǎn)的每一條路徑均穿過PQ線上的格子點(diǎn) m l l l 0 1 r 從 0 0 點(diǎn)到 m l l 點(diǎn)的路徑數(shù)為C m l 再從 m l l 點(diǎn)到 m n r r 點(diǎn)的路徑數(shù)為C n r l 由乘法法則 從 0 0 點(diǎn)出發(fā)經(jīng)過 m l l 點(diǎn)到 m n r r 點(diǎn)的路徑數(shù)為C m l C n r l 再由加法法則 即可得證 1 6模型轉(zhuǎn)換例6 1 1 6模型轉(zhuǎn)換 格路問題 例6 從 0 0 點(diǎn)到 m n 點(diǎn) m n 的 要求中間經(jīng)過的每一個格子點(diǎn) a b 恒滿足a b關(guān)系 問有多少條路徑 解 從 0 0 點(diǎn)到 m n 點(diǎn)的路徑數(shù)為C m n m 但需要排除碰到或穿過y x格子點(diǎn)的路徑數(shù) 即去掉a b的情況 第一步必須從 0 0 點(diǎn)到 1 0 點(diǎn) 因此問題等價于求從 1 0 點(diǎn)到 m n 點(diǎn)的路徑數(shù) 因?yàn)閙 n 故從 0 1 點(diǎn)到 m n 點(diǎn)的路徑必然穿過y x上的格子點(diǎn) 下面建立從 0 1 點(diǎn)到 m n 點(diǎn)的每一條路徑 與從 1 0 點(diǎn)到 m n 點(diǎn)但經(jīng)過y x上的格子點(diǎn)的路徑時一一對應(yīng)的 1 6模型轉(zhuǎn)換例6 2 1 6模型轉(zhuǎn)換 格路問題 若從 0 1 點(diǎn)到 m n 點(diǎn)的路徑與y x的交點(diǎn)從左往右數(shù)最后一個是P 作從 1 0 點(diǎn)到P點(diǎn)關(guān)于y x的與上述 0 1 點(diǎn)到P點(diǎn)的路徑對稱的一條路徑 于是從 0 1 點(diǎn)到 m n 點(diǎn)的一條路徑 就有一條從 1 0 點(diǎn)到 m n 點(diǎn)但經(jīng)過y x上的格子點(diǎn)的路徑與之對應(yīng) 反之 一條從 1 0 點(diǎn)到 m n 點(diǎn)但經(jīng)過y x上的格子點(diǎn)的路徑 必存在一條從 0 1 點(diǎn)到 m n 點(diǎn)的一條路徑與之對應(yīng) 故所求的路徑數(shù)為C m n 1 n C m n 1 n 1 m n m n 1 m n 例6 從 0 0 點(diǎn)到 m n 點(diǎn) m n 的 要求中間經(jīng)過的每一個格子點(diǎn) a b 恒滿足a b關(guān)系 問有多少條路徑 第1章小結(jié) 本章小結(jié) 本章討論了基本的組態(tài) 滿足一定條件的優(yōu)先集合的安排 的計數(shù)問題 主要用加法法則和乘法法則解決最基本的幾種組合模型 包括排列 線排列 圓排列 重排列 項(xiàng)鏈排列 組合 無重組合 重復(fù)組合 的計數(shù)問題 并介紹了二項(xiàng)式系數(shù) 廣義二項(xiàng)式系數(shù) 多項(xiàng)式系數(shù) 及證明的組合恒等式的幾種不同證明方法 重點(diǎn)是要掌握如何使用基本的組合模型來證明組合恒等式 要特別注意如何利用合理分類和組合模型的轉(zhuǎn)換進(jìn)行組合計數(shù) 第1章習(xí)題 習(xí)題 P221 6 8 10 11 14 16 20 22 第2章鴿籠原理 回顧前一章 計數(shù) 本章重點(diǎn)介紹鴿籠原理及其在排列組合中的 存在性 應(yīng)用 例子 意義鴿籠原理 排列組合組合恒等式 2 1鴿籠原理定理 2 1鴿籠原理 定理2 1 鴿籠原理 抽屜原理 若把n 1個物體放到n n 1 個盒子中去 則至少有一個盒子放有至少2個物體 證明 用反證法證明 如果n個盒子中每個盒子至多放入一個物體 則放入n個盒子中的物體總數(shù)至多為n個 這與假設(shè)有n 1個物體矛盾 從而定理得證 注 鴿籠原理只指出了至少存在這樣的盒子 并沒有給出 確定哪一個盒子有此性質(zhì)的方法 因此 它只能用來解決存在性問題 4 4 0 0 3 1 0 2 2 0 2 1 1 2 1鴿籠原理例1 2 3 2 1鴿籠原理 例題 例1 一年有365天 今有366個人 則其中至少有兩個人生日相同 證明 此例中把 天 當(dāng)作盒子 相當(dāng)于365個盒子放入366個物體 得證 例2 抽屜里有10雙相同的手套 從中取11只出來 其中至少有兩只是完整配對的 證明 此例中把 每雙手套 當(dāng)作盒子 相當(dāng)于10個盒子放11個物體 得證 例3 一個教師每周上7次