組合數(shù)學(xué)教案1章排列組合基礎(chǔ)

1、第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)第1章組合數(shù)學(xué)基礎(chǔ)1.1緒論（一） 背景：數(shù)學(xué)幻方問題：給定自然數(shù)1, 2, L, n2 ，將其排列成 n 階方陣，要求每行、每列和每條對(duì)角線上 n 個(gè)數(shù)字之和都相等。這樣的 n 階方陣稱為 n 階幻方。每一行（或列、或?qū)蔷€）之和稱為幻方的和（簡(jiǎn)稱幻和）。例：3 階幻方，幻和(1239)/315。關(guān)心的問題存在性問題：即 n 階幻方是否存在？計(jì)數(shù)問題：如果存在，對(duì)某個(gè)確定的 n，這樣的幻方有多少種？構(gòu)造問題：即枚舉問題，亦即如何構(gòu)造 n 階幻方。奇數(shù)階幻方的生成方法：一坐上行正，依次斜填切莫忘，上邊出格往下填，右邊出格往左填，右上有數(shù)往下填，右上出格往下填。例：將

2、2，4，6，8，10，12，14，16，18 填入下列幻方：1/5143884921. 排列組合的基本計(jì)數(shù)問題2. 多項(xiàng)式系數(shù)的計(jì)算及其組合意義3. 排列組合算法第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)【例 1.1.1】（拉丁方）36 名軍官問題：有 1，2，3，4，5，6 共六個(gè)團(tuán)隊(duì)，從每個(gè)團(tuán)隊(duì)中分別選出具有A、B、C、D、E、F 六種軍銜的軍官各一名，共 36 名軍官。問能否把這些軍官排成 6×6的方陣，使每行及每列的 6 名軍官均來自不同的團(tuán)隊(duì)且具有不同軍銜？本問題的是E5 F6 A1 B2 C3 D4的。F6 A1 B2 C3 D4 E5A1 B2 C3 D4 E5 F6B2 C3 D4

3、E5 F6 A1C3 D4 E5 F6 A1 B2D4 E5 F6 A1 B2 C3A1 B3 C5 D2 E4 F6B2 C4 D6 E3 F5C3 D5 E1 F4 A6D4 E6 F2 A5 B1E5 F1 A3 B6 C2F6 A2 B4 C1 D3【例 1.1.2】（計(jì)數(shù)圖形染色）用 3 種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個(gè)頂點(diǎn)，若某種染色方案在正方形旋轉(zhuǎn)某個(gè)角度后，與另一個(gè)方案重合，則認(rèn)為這兩個(gè)方案是相同的。求本質(zhì)上不同的染色方案。舉例：（a）（b）2/51ybrbrybb第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)形式總數(shù)： 34 81 種。實(shí)際總數(shù)（見第 6 章）：L 1 (3

4、4 + 32 + 2´ 3)244【例 1.1.3】（存在性）不同身高的 26 個(gè)人隨意排成一行，那么，總能從中挑出 6 個(gè)人，讓其出列后，他們的身高必然是由低到由高到低排列的（見第 5 章）。注意：不改變?cè)瓉淼南鄬?duì)順序。（二） 研究?jī)?nèi)容算法分類：l 第一類：數(shù)值算法。主要解決數(shù)值計(jì)算問題，如方程求根、解方程組、求等，其數(shù)學(xué)基礎(chǔ)是高等數(shù)學(xué)與線性代數(shù)（解決建模問題，數(shù)值分析或稱計(jì)算方法解決離散化問題，即在計(jì)算機(jī)上的求解方法問題）。l 第二類：組合算法。解決搜索、排序、組合優(yōu)化等問題， 其數(shù)學(xué)基礎(chǔ)為組合數(shù)學(xué)。按所研究問題的類型，研究?jī)?nèi)容：llll組合計(jì)數(shù)理論組合設(shè)計(jì)組合矩陣論組合優(yōu)化本課

5、程重點(diǎn)：以組合計(jì)數(shù)理論為主，部分涉及其它內(nèi)容。（三） 研究方法分類：第一類：從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)方法（利用原理、二項(xiàng)式定理、Pólya 定理解計(jì)數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。第二類：通常與問題所涉及的組合學(xué)概念無關(guān)，而對(duì)多種問題均可使用。例如：（1） 數(shù)學(xué)歸納法：前提是已知問題的結(jié)果。（2） 迭代法3/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)= 2hn-1 + 1, ，求= 1【例】已知數(shù)列h 滿足關(guān)系ìhníhh 的表nnî1。（解）直接迭代即得：hn = 2hn-1 + 1 2(2h)+ 12+

6、 2 + 11 2 hn-2n-2 2 ()+ 2 + 1 2 h+ 22 + 2 + 1+ 1232hn-3n-3M 2n-1 h + 2n-2 + 2n-3+ L+ 22 + 2 + 11 2n - 1（3） 一一對(duì)應(yīng)技術(shù)原理：建立兩類事物之間的一一對(duì)應(yīng)關(guān)系，把一個(gè)較復(fù)雜的組合計(jì)數(shù)問題 A 轉(zhuǎn)化成另一個(gè)容易計(jì)數(shù)的問題 B，從而利用對(duì) B的計(jì)數(shù)運(yùn)算達(dá)到對(duì) A 的各種不同方案的計(jì)數(shù)。思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式。（4） 殊途同歸方法原理：從不同角度討論計(jì)數(shù)問題，以建立組合等式。應(yīng)用：組合恒等式的證明（也稱組合意義法）。（5） 數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論

7、性質(zhì)進(jìn)行分析推理的方法。組合數(shù)學(xué)用的較多的方法：（3）與（4）?！纠?1.1.4】有 100 名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產(chǎn)生冠軍共需要進(jìn)行多少場(chǎng)比賽？（解）常規(guī)思路：502512632199 場(chǎng)10000 名選手：5000250012506253121采用一一對(duì)應(yīng)方法：每場(chǎng)比賽產(chǎn)生一個(gè)失敗者，且每個(gè)失敗者只能失敗一次（場(chǎng)次失敗者）。反之，要淘汰一個(gè)選手，必 須恰好經(jīng)過一場(chǎng)比賽（失敗者場(chǎng)次）。結(jié)論：失敗者« 比賽場(chǎng)次。應(yīng)該比賽 99 場(chǎng)。4/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)一般情況：?jiǎn)窝h(huán)淘汰制，n 個(gè)選手，比賽n - 1場(chǎng)?！纠?1.1.5】設(shè)某地的街道將城市分割

8、成矩形方格，在其住處 A(0, 0)的B(7, 5)處工7 個(gè)街道、向北 5 個(gè)街道的作（見圖 1.1.3），按照最短路徑（即只能或向北走），他每次上班必須經(jīng)過某 12 個(gè)街段，問共有多少種不同的上班路線？（解）（1）將街道抽象為等長(zhǎng)的。B(7, 5)A(0, 0)（2）對(duì)應(yīng)為（元素可重復(fù)的）排列問題：） 排列路徑（排列 路徑（紅色） 結(jié)論：最短路徑« 7 個(gè)x 和 5 個(gè)y 的排列（3）求解：再對(duì)應(yīng)為（元素不重復(fù)的）排列問題12!N = C 5C 5 7927+55!×7!12（4）一般情形：從（0, 0）點(diǎn)到達(dá)（m, n）點(diǎn)的不同的最短路徑數(shù)為N = Cm= Cnm +

9、 nm + n1.2 兩個(gè)1. 2. 1加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個(gè)方案，而第一個(gè)方案有 m 種方法，第二個(gè)方案有 n 種方法可以實(shí)現(xiàn)。只要選則擇任何方案中的某法，就可以完成這件事情，并且這些方法兩兩互不相同。則完成這件事情共有 mn 種方法。5/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)l集合描述：設(shè)有限集合 A 有 m 個(gè)元素，B 有 n 個(gè)元素， 且 A 與 B 不相交，則 A 與 B 的并共有 mn 個(gè)元素。lA 有 m 種產(chǎn)生方式，B 有 n概率角度描述：設(shè)種產(chǎn)生方式，則“A 或 B”有 mn 種產(chǎn)生方式。當(dāng)然 A 與 B 各自所含的基本（二） 應(yīng)用是互相不同的。

10、【例 1.2.1】某班又男生 18 人，女生 12 人，從中選出一名代表參加會(huì)議，問共有多少種選法？（解）（1）兩個(gè)選擇方案：男生（18 種選法）或女生（12種選法）。由加法法則，有 181230 選法。（2）設(shè)集合：A男生，B女生。該班中的學(xué)生要么屬于 A，要么屬于 B，且 ABf ，故A + B 181230。（3） 種可能）。A選男生（18 種可能），B選女生（12“A 或 B”選男生或女生，由加法法則，有181230 種可能?！纠?1.2.2】用一個(gè)小寫英文字母或一個(gè)器編號(hào)，問總共可能編出多少種號(hào)碼？（解）261036 個(gè)。其中英文字母共有 26 個(gè)，數(shù)字 09 共 10 個(gè)。1. 2

11、. 2乘法法則（一） 乘法法則l 常規(guī)描述：如果完成一件事情需要兩個(gè)步驟，而第一數(shù)字給一批機(jī)m 種方法、第二有m × n 種方法。n 種方法去實(shí)現(xiàn)。則完成該件事情共l 集合描述：設(shè)有限集合 A 有 m 個(gè)元素，B 有 n 個(gè)元素， 且 A 與 B 不相交， a Î A, b Î B ，記(a, b)為一有序?qū)?。所有有序?qū)Φ募戏Q為 A 和 B 的積集（或笛卡兒乘積），記作 A´ B 。那么， A ´ B 共有m × n 個(gè)元素。A ´ B = (a, b) a Î A, b Î B6/51第一章組合數(shù)學(xué)基

12、礎(chǔ)組合數(shù)學(xué)l 概率角度描述：設(shè)離散型隨量 X 有 m 個(gè)取值，Y 有 n個(gè)取值，則離散型隨機(jī)向量(X , Y )有m × n 種可能的取值。（二） 應(yīng)用【例 1.2.3】仍設(shè)某班有男生 18 人，女生 12 人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽，問共有多少種選法？（解）（1）分兩步挑選，先選女生（12 種選法），再選男生（18種選法）。由乘法法則，有 12×18216 種選法。（2） 設(shè)集合：A男生，B女生。由乘法法則， A ´ B18×12216。（3） 變量 X男生（18 種取值），變量 Y女生（12 種取值）。由乘法法則，隨機(jī)向量（X

13、，Y）有 18×12216 種可能的值?！纠?1.2.4】給程序模塊命名，需要用 3 個(gè)字符，其中首字符要求用字母 AG 或 UZ，后兩個(gè)要求用數(shù)字 19，問最多可以給多少種程序命名？（解）首字符選法：7613 種（加法法則）。總數(shù)： 13×9×91053 種（數(shù)字可重復(fù)使用）（乘法法則）?！纠?1.2.5】從 A 地到 B 地有n1 條不同的道路，從 A 地到 C 地有n2 條不同的道路，從 B 地到 D 地有m1 條不同的道路，從 C地到 D 地有m2 條不同的道路，那么，從 A 地經(jīng) B 或 C 到達(dá)目的地 D 共有多少種不同的走法?（解）路線 A 

14、4; B ® D： n1 × m1 種走法（）路線 A ® C ® D： n2 × m2 種走法（）總數(shù)： n1 m1 n2 m2 種走法（加法法則）7/51乘法法則乘法法則第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)2×33×418排列與組合1.31. 3. 1相異元素不（一） 計(jì)算公式重復(fù)的排列數(shù)和組合數(shù)從 n 個(gè)相異元素中不重復(fù)地取 r 個(gè)元素的排列數(shù)和組合數(shù)：n!= P(n, r ) = n(n - 1)L(n - r + 1) = (Pr（1）排列：n - r )!n推導(dǎo)：反復(fù)利用加法法則與乘法法則æ nöPrn

15、!= C(n, r ) = ç÷ =C r n r!（2）組合：()nn - rè r ø!r!推導(dǎo)：利用組合與排列的異同（3）例：n5，r3，即元素為 1，2，3，4，5排列：134，143，314，341，413，431；254，425， 組合：134，245，（4）特點(diǎn)：排列考慮順序，組合不然。（二） 數(shù)學(xué)模型（1）排列問題：將 r 個(gè)有區(qū)別的球放入 n 個(gè)不同的盒子，每盒不超過一個(gè)，則總的放法數(shù)為P r 。n（2）組合問題：將 r 個(gè)無區(qū)別的球放入 n 個(gè)不同的盒子，每盒不超過一個(gè)，則總的放法數(shù)為C r 。n8/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)1.

16、 3. 2相異元素（一） 問題從 n 個(gè)不同元素中重復(fù)的排列重復(fù)地選 r 個(gè)元素的排列，簡(jiǎn)稱 r 元重復(fù)排列，排列數(shù)記為 RP(, r)。（二） 模型將 r 個(gè)不相同的球放入 n 個(gè)有區(qū)別的盒子，每個(gè)盒子中的球數(shù)不加限制而且同盒的球不分次序。（三） 計(jì)算公式RP(, r) nr（四） 集合描述方式設(shè)無窮集合S = ¥ × e , ¥ × e ,L, ¥ × e，從 S 中取 r 個(gè)元素12n的排列數(shù)即為 RP(, r)。不重復(fù)排列：S1× e , 1× e , L, 1× e e , e , L, e 。

17、12n12n9/51對(duì)應(yīng)關(guān)系元素« 盒子位置« 球元素和位置編號(hào)12345A B C排列 1ABC1 1 4排列 2C BA4 3 3排列 3A CB3 4 3排列 4A B C2 2 2排列 5BAC4 2 5對(duì)應(yīng)關(guān)系元素« 盒子位置« 球元素和位置編號(hào)12345A B C排列 1ABC1 3 4排列 2CBA4 3 1排列 3ACB1 4 3排列 4ACB2 5 4排列 5BAC4 2 5組合 11 3 4組合 22 4 5第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)1. 3. 3不盡相異元素的列（一） 問題有限重復(fù)排列（部分排列）：設(shè)S = n1 × e1

18、 , n2 × e2 , L, nt × et （ n1 + n2 + L+ nt = n ），從 S 中RP(n, r )。（二） 模型r 個(gè)元素，求其排列數(shù)將 r 個(gè)有區(qū)別的球放入 t 個(gè)不同的盒子，每個(gè)盒子的容量有限，其中第 i 個(gè)盒子最多只能放入ni 個(gè)球，求分配方案數(shù)。例： S2·1，4·2，1·3，3·4，2·51, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 5說明：（1）情形：相異元素不重復(fù)的排列強(qiáng)調(diào)的是不重復(fù)，即盒子的容量為 1；（2情形：相異元素重復(fù)的排列強(qiáng)調(diào)的是無限重復(fù)，即盒子的容量無限

19、；（3）一般情形：不盡相異元素的排列強(qiáng)調(diào)的是有限重復(fù)，即盒子的容量有限，介于兩者之間。（三） 特例（1） r 1：RP(n, 1)t（2） r n（列）10/51對(duì)應(yīng)關(guān)系元素« 盒子位置« 球元素和位置編號(hào)12345A B C排列 1ABC1 1 4排列 2B CA4 3 3排列 3A CB3 4 3排列 4A B C2 2 2排列 5BAC4 2 5第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)n!RP (n, n) =n1!n2!Lnt !例a1a2 a3 b1b2 c1c2 與a1a2a3a1b2b1c1c2a1b1a2 b2 c1a3 c2 與a2 b1a1b2 c1a3 c2

20、0; n ön!（3）t2， RP (n, n) = ç÷n1!n2 !è n1 ø（4） ni 1，即不重復(fù)的排列（5） ni = ¥ ，即重復(fù)排列1. 3. 4相異元素不（一） 圓排列重復(fù)的圓排列【例 1.3.1】把 n 個(gè)有標(biāo)號(hào)的珠子排成一個(gè)圓圈，共有多少種不同的排法？（解）稱為圓排列（相對(duì)于線排列）。條件：元素同時(shí)按同一方向旋轉(zhuǎn)，絕對(duì)位置變化，相對(duì)位置未變，即元素間的相鄰關(guān)系未變，視為同一圓排列。結(jié)論：1 個(gè)圓排列對(duì)應(yīng) n 個(gè)線排列。CP(n, n) = P(n, n) (n1)!n3254125413541324132513

21、254【例 1.3.2】從 n 個(gè)相異元素中不重復(fù)地取 r 個(gè)圍成圓排列，求不同的排列總數(shù) CP(n, r)。n!P rCP(n, r)（解）nrr n - r )!(11/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)（二） 項(xiàng)鏈排列【例 1.3.3】將 5 個(gè)標(biāo)有不同序號(hào)的珠子穿成一環(huán)，共有多少種不同的穿法？（解）稱為項(xiàng)鏈排列。條件：可以翻轉(zhuǎn)的圓排列。即同一項(xiàng)鏈不用剪斷重穿，翻過來仍是原項(xiàng)鏈。結(jié)論：兩個(gè)圓排列對(duì)應(yīng)一個(gè)項(xiàng)鏈排列，故有 24/212 種。（a）（b）圖 1.3.1項(xiàng)鏈排列一般情形：從 n 個(gè)相異珠子中取 r 個(gè)的項(xiàng)鏈排列數(shù)：P rn! n 2r2r(n - r )!重復(fù)的圓排列：情況復(fù)雜，參見

22、反演公式（第四章）。1. 3. 5相異元素（一） 問題重復(fù)的組合設(shè)S = ¥ × e, L, ¥ × e ，從 S 中, ¥ × e重復(fù)地取 r 個(gè)12n元素組合，稱為 r 可重組合，其組合數(shù)記為 RC(, r)。（二） 抽象記S 為S = ¥ × 1, ¥ × 2, L, ¥ × n 。例：n5，r4：（三） 計(jì)算公式1111，1122，1345，555512/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)設(shè)所選 r 個(gè)元素為：1a1a2arnbi = ai + (i - 1)， i1，2

23、，r1b1b 2brn(r1)令則ai = bi - (i - 1)反之結(jié)論：與從 nr1 個(gè)相異元素中不重復(fù)地取 r 個(gè)元素的組合方案一一對(duì)應(yīng)。 RC (¥, r ) = C (n + r - 1, r ) = (n + r - 1)!r!(n - 1)!例： n5，r4（四） 模型將 r 個(gè)無區(qū)別的球放入 n 個(gè)不同的盒子，每個(gè)盒子的球數(shù)不受限制。（五） 應(yīng)用【例 1.3.4】不同的 5 個(gè)字母通過通信線路被傳送，每?jī)蓚€(gè)相鄰字母之間至少3 個(gè)空格，但要求空格的總數(shù)必須等于 15，問共有多少種不同的傳送方式？（解）三步求解：（1）先排列 5 個(gè)字母，排列數(shù) P(5, 5)5!。（2

24、）兩個(gè)字母間各4 個(gè)間隔內(nèi)，有 1 種方案。3 個(gè)空格，將 12 個(gè)空格均勻地放入c b d e a（3）將余下的 3 個(gè)空格4 個(gè)間隔：分析：將 3 個(gè)相同的球放入 4 個(gè)不同的盒子，盒子的容量不限。方案 1： c b d e a方案 2： c b d e a13/51分類重復(fù)組合不重復(fù)組合元素1, 2, 3, 4, 51, 2, 3, 4, 5, 6, 7, 8部分組合11111234112212452245236855555678第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)歸納：從 4RC(個(gè)相異元素中可重復(fù)地取 3 個(gè)元素的組合數(shù)¥, 3) = C= 20 。34+ 3-1（4）總方案數(shù)： L

25、5！·1. 3. 6不盡相異元素1·202400r 個(gè)的組合問題（一） 問題設(shè)集合S = n1 × e1 , n2 × e2 , L,nt × et （ n1 + n2 + L + nt= n ），從 S 中r 個(gè)，求其組合數(shù) RC(n, r)。（二） 組合數(shù)中間工具：組合問題的母函數(shù)：ni()nttÕååÕxrj1 +nar =0x iri =1 j = 0i =1：RC(n, r) ar（三） 應(yīng)用【例 1.3.5】整數(shù) 360 有幾個(gè)正約數(shù)？（解）（1）標(biāo)準(zhǔn)素因數(shù)分解：36023×32&#

26、215;5（2） 正約數(shù)及其條件120×30×50，22×30×50，320×3×50，520×30×5，2222×30×50，62×3×503×2，902×32×5，18022×32×5，36023×32×5結(jié)論：正整數(shù) d 是 360 的正約數(shù)Û d 2a3b5c 且 0a 3，0b2，0c1。故 142×7 不是約數(shù)，16 24 也不是約數(shù)。（3） 問題轉(zhuǎn)化：求S = 3×

27、; 2, 2× 3, 1× 5的所有組合數(shù)之和。（4） 求解：構(gòu)造多項(xiàng)式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6系數(shù)求和： t = å RC (6, i )135653124i=0方法化簡(jiǎn)：求 P6(1)å RC (6, i )4×3×224i =014/5166第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)aaa（5）一般規(guī)律：設(shè)正整數(shù) n 分解為n = ppL p，則12k12kt = (a1+1)L(a 2+1)(a k+1)習(xí)題：18，21小結(jié)：課程任務(wù)；技巧性。1.4組合等式及其組合意義組合等式的證明方

28、法：（1） 歸納法（2） 組合意義法：借助于闡明等號(hào)兩端的不同表實(shí)質(zhì)上是同一個(gè)組合問題的方案數(shù)（殊途同歸法），或者雖是兩個(gè)不同組合問題的方案數(shù)，但二者的組合方案之間存在著一一對(duì)應(yīng)關(guān)系，因此等式兩端必須相等，從而達(dá)到證明等式成立的目的。對(duì)于恒等式的實(shí)質(zhì)刻。得更為深（3） 母函數(shù)法：利用無窮級(jí)數(shù)（包括有限時(shí)的多項(xiàng)式）證明有關(guān)組合等式。是產(chǎn)生和證明組合恒等式的普遍方法。（4） 其它方法：二項(xiàng)式展開、反演公式等【等式 1】對(duì)稱關(guān)系式Cr = Cn-rnn組合意義：a1 ,a2 ,L,an 的 r 組合 « nr 組合【等式 2】加法公式+ Cr -1Cr= Crn-1n-1n（一）組合意義：

29、a1 ,a2 ,L,an 的 r 組合，分為兩類：（1） 取出的元素中含有a ：組合數(shù)為Cr-1 。n-11（2） 不含元素a ，組合數(shù)為Cr。n-11+ Cr -1總數(shù)：Crn-1n-1注意：無第三種情形；兩類情況互不重復(fù)；用加法法則。（二）例：從1，2，3，4，5中取 3 個(gè)的組合情況：15/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)第一類（包含元素“1”）：第二類（不包含“1”）：123，124，125，134，135，145234，235，245，345（三）路徑問題：等價(jià)形式+ Cm -1Cm= Cmm + nm + n-1m + n-1組合意義：從（0，0）點(diǎn)到（m，n）點(diǎn)的路徑數(shù)等于從（0，

30、0）點(diǎn)分別到（m，n1）點(diǎn)和（m1，n）點(diǎn)的路徑數(shù)之和。(m, n)(0, 0)【等式 3】乘法公式CkCr = CrCk - rnn- rnkCn- kCk - rCr = CrCn- kCk - r等式變形：組合意義nn- rk - rnkr（1） 左端：“將 n 個(gè)元素分為 3 堆：第一堆n - k 個(gè)，第二堆k - r 個(gè)，則第三堆為 r 個(gè)”，求組合方案數(shù)。（2） 右端：“將 n 個(gè)元素分為 3 堆：第三堆 r 個(gè)，第二堆n - k個(gè)，第一堆k - r 個(gè)”，求組合方案數(shù)。（3） 兩個(gè)組合問題等價(jià)。舉例：n20578785，C 5 C 7 C 8 C 7 C 8 C 520 15 8

31、20 13 5推廣：n 個(gè)元素分為 t 堆，且可以若干堆個(gè)數(shù)相等n2042592945，C 4 C 2 C 5 C 2 C 9 C 420 18 1620 18 9rn + r + 1å+ Cr -1+ Cr - 2Cr+ L + C0【等式 4】Cr=Cin + in+ rn+ r -1n+ r - 2ni = 0rn + r + 1å=CCn+ Cn+ Cn+ L + CnCrn或n + in+ rn+ r -1n+ r - 2ni = 0（一）組合意義：16/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)（二）說明：等式 2 的推廣。+ Cr-1 CrCrn+rn+rr -n+r +

32、1+ ()+ Cr -2 Cr1Cn+rn+r -1n+r -1+ ()+ Cr -1r -2+ Cr -3 CrCn+rn+r -1n+r -2n+r -2(+ C 0)+ Cr -1+ Cr -2 Cr+ L + C1n+rn+r -1n+r -2n+1n+1+ Cr -1+ Cr -2 Cr+ L + C 1+ C 0n+rn+r -1n+r -2n+1n（三）相應(yīng)的路徑問題：(r, n + 1)(0, 0)【等式 5】Vandermonde（蒙）恒等式æ m + nöræ nöæömåçè

33、7; ç÷ç÷øir - irøi =0 èmøèæ nöæ m öæ nöæöæ nöæ m öç÷ç÷ + ç÷ç÷ + L + ç÷ç÷ ,rmin(m，n)è 1 øè r - 1ø0rè r ø

34、32; 0 øèøèø組合意義 n 個(gè)相異的紅球，m 個(gè)相異的藍(lán)球，選 r 個(gè)的組合。分類統(tǒng)計(jì)：i 個(gè)紅球，ri 個(gè)藍(lán)球的選法為Ci Cr-i 。nm特例：mræ n + r öæ nöæ r öæ nöæöæ nöæ r örçè÷ ç÷ç÷ + ç÷ç÷ + L + ç÷&#

35、231;÷ ，rnè 1 øè r - 1ørøè 0 øè r øè r øè 0ø17/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)æ nöæ r öæ nöæ r öæ nöæ r öç÷ç÷ + ç÷ç÷ + L + ç÷ç÷

36、è 0 øè 0øè 1 øè 1øè r øè r øræ nöæ r öåç÷ç÷iii =0 èøèøn【等式 6】和式公式： åC(n, i ) = 2n組合意義：n 個(gè)相異元素選 i 個(gè)的組合« 兩類元素的 n 可重排列i =0æ n öæ n öæ n ön

37、 æ n ö÷ - ç÷ + ç÷ - L + (- 1) ç÷ = 0【等式 7】çè 0 øè 1 øè 2 øè n ø組合意義：等式變形+ C 2 + L = C1 + C 3 + LC 0nnnn奇組合數(shù)偶組合數(shù)。啟發(fā)：存在一一對(duì)應(yīng)關(guān)系。例：n4()()()222n= nCn-11n+ 22n+ L +、nCCnC【等式 8】2n-1n組合意義：從 n中選出 n 人，其中一人擔(dān)，且必須為太太，求選法數(shù)。選法

38、 1：選一；再選 n1 人。選法總數(shù)為C1Cn-1 = nC n-1。n2n-12n-1選法 2：從 n中選 k 人；從此 k 人中選一人18/51奇組合aabcabdacdbcdbcd偶組合bcbdcdabacadabcd組合e1e2e3e4e5e6排列不不不不不不000000e1 e2 e3 e4 e5 e6取取取取取取111111e1 e3 e6取不取不不取101001e3 e5 e6第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)席；再從 n中選 nk 人（1kn）。()CkC1 Cn-k= kk 2Cnknn()nåk 2選法總數(shù)k Cnk =1【等式 9】設(shè) r，M 都是自然數(shù)，Mr 則有r

39、+ M - r ×r+ M - r × M - r - 1 ×rMMM - 1MM - 1M - 2+ L + M - r × M - r - 1L 1× r= 1M - 1r + 1 rM組合意義（概率問題）：設(shè)袋中有 M 個(gè)大小相同的球，其中r 個(gè)，其余為黑球。每次摸出一個(gè)球，不放回，直至摸到白球?yàn)橹?。是必然（遲早會(huì)摸到），概率為 1。r另法： 第一次摸到 概率。 第二次摸到MM - r ×r,LL，第 k 次才摸到k2, 3, , Mr1）MM - 1M - r × M - r - 1 ×L× M

40、- r - (k - 2) ×rM - (k - 2)M - (k - 1)M - 1M【等式 10】當(dāng) nm 時(shí)，n-må nm+km= 2n-m× CmCCm+knk=0組合意義：從 n 人中選出 m 名正式代表及若干名列席代表的選法（列席代表人數(shù)不限）。統(tǒng)計(jì)方法一：先選正式代表，再從n - m 人中選列席代表，2n-m ?？偟倪x法為C mn統(tǒng)計(jì)方法二：先選 mk 人（k0, 1, , nm） ，再從中選出 m 名正式代表，其余的 k 人為列席代表，有Cm+kCm種選m+kn法。n-måk =0m+ kmm+ kCC總數(shù)n19/51第一章組合數(shù)學(xué)基礎(chǔ)

41、組合數(shù)學(xué)1.5 多項(xiàng)式系數(shù)（一） Newton 二項(xiàng)式(1) 二項(xiàng)展開式Newton 二項(xiàng)式定理（n 是正整數(shù)）n(a + b)n =C a bår r n-rnr =0右端稱為二項(xiàng)式(ab)n 的展開式，C r 叫做二項(xiàng)式系數(shù)。n(2) 組合意義分配問題：將 n 個(gè)相異的球放入兩個(gè)盒子，a 盒放入n1 = r 個(gè)，b 盒放入n2 = n - r 個(gè)，同盒的球不分次序，方案數(shù)為n!n! r!×(n - r )!n1 !×n2 !rn-r即a b項(xiàng)的系數(shù)為組合數(shù)C 。rn(a + b)2 (ab)(ab)aaabbabb a 2 + 2ab + b2例(a + b)

42、3 (ab)(ab)(ab)(aaabbabb)(ab)aaaaababaabbbaababbbabbb a3 + 3a2b + 3ab2 + b3產(chǎn)生系數(shù)的根源：同一單項(xiàng)式中有順序，即排列問題（球不同的分配問題）。排列問題：從兩種元素中選 n 個(gè)的排列（a 選r 個(gè)，b 選n - r個(gè)）（二） 一般分配問題問題：將 n 個(gè)相異的球放入 t 個(gè)盒子，要求第 1 個(gè)盒子放入n1個(gè)，第 2 個(gè)盒子放入n2 個(gè)，第 t 個(gè)盒子放入nt 個(gè)，且盒中的球無次序，求不同的分配方案數(shù)。轉(zhuǎn)化：求S = n × e , n × e ,L, n × e （ n + n + L + n

43、 = n ）1122列數(shù) RP(n，n)：RP(n, n) =tt12t的n!n1!n2 !Lnt !æ n öænö仿照二項(xiàng)式系數(shù)ç÷ ，記為ç÷ 。è r øè n1n2 Lnt ø20/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)（三） 多項(xiàng)式系數(shù)æönç÷一般多項(xiàng)式系數(shù)與的關(guān)系：n n Lnè 1 2t ø(x + y + z)3 x3y3z33x2y3xy23x2z6xyz3!3!3!3!x3y3z33!x2y3!

44、15;0!×0!0!×3!×0!0!×0!×3!2!×1!×0!3!3!xy2x2zxyz1!×2!×0!32!×0!×1!1!×1!×1!3æöæöæ33öç÷ x ç÷ y ç÷ z333è 300ø3è 00ø32è 003ø30æöæö

45、30;öç÷ x yç÷ xy ç÷ x z222è 210øè10øè 21øæö3ç÷ xyzè 111ø【定理 1.5.1】設(shè)n 與t 均為正整數(shù)，則有ænö(å+ L +ç÷nn L212121Lnnnè21t øtåi = nni=1(ni ³0)t其中求和是在使ånii =1進(jìn)行。=n 的所有非負(fù)

46、整數(shù)數(shù)列（n1,n2,nt）上（證） ()nt(t4)(具形式t )L(t )443共n個(gè)因子連乘（1）所有n，且å n= nn2n1L21ii =1nt 項(xiàng)，（2）一般項(xiàng)的系數(shù)： n 個(gè)因式中選取 x ，得tii其系數(shù)為)×, n )L)112t21/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)(n - n1 )!n!nt !×L(n - n )! n2 !×(n - n1 - n2 )!nt !×0!×n !11ænön!ç÷n n Lnn !n !Ln !è 1 2t ø12t

47、30;nö稱ç÷為多項(xiàng)式系數(shù)。è n1n2 Lnt ø（四） 多項(xiàng)式展開的項(xiàng)數(shù)【定理 1.5.2】(+ L+展開式的項(xiàng)數(shù)等于C n，21t + n-1而這些項(xiàng)的系數(shù)之和為t n .（證）展開式的項(xiàng)中取 n 個(gè)的 n 可重組合。«從t 種元素n2n1LL,121=21= L =在定理 1.5.1 中令1 得æönåç÷ (1 + 1 + L+ 1)n = t nè n1n2 Lnt øtå ni =n(ni ³0)（五） 例i =1【例 1.5.1

48、】求(a + b + c + d )3 的展開式。（解）n3，t4，有 RC(, 3)C 320（項(xiàng)）4+ 3-1(a + b + c + d )3æöæö33çè÷a 0çè÷b 033300030øø3æöæö3çè 2÷a b ç÷cd22100øè 0012øæöæö33çè1÷a

49、bc ç÷bcd110øè 0111ø a 3 b3 c 3 d 3 3 a 2b 3 a2c 3 a 2d 3 cd 2 6abc6abd6acd6bcd【例 1.5.2】(a + a + a + a + a)723的展開式中，項(xiàng)a a a a 的123451 3 4 522/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)系數(shù)。æ71öçè 2【例 1.5.3】在(÷ =4202!×0!031ø+-531的展開式中，項(xiàng)系數(shù)是什么？（解）令a1 = 2 x1 ， a2 = -3 x2 ， a

50、3 = 5 x3 。l 展開(a + a + a )6 ：123æ61ö32ç÷2a aa 的系數(shù)ç12 33èø)3()-(5)中(+-5系數(shù)：的系數(shù)131læ6ö6!÷2 (- 3)5× 8 × (- 3)× 25çè 3323!×1!×2!12ø36000【例 1.5.4】求證nå(- 1)k C(n, k )xk，n1k =0（證）（證明組合等式）在二項(xiàng)式中取a = - x ， b = 1 + x1

51、1n (- x)+ (1 + x)n åC(n, k )(- x)k (1 +k = 0n日，再過10100 天是【例 1.5.5】今天是幾？（解）（求余數(shù)，同余運(yùn)算）10100 10050 (14´ 7 + 2)50050ö÷(14´ 7)ø 2+50rr =1 è等價(jià)問題：23/5110100 除以 7 的余數(shù) 250 除以 7 的余數(shù)第一章組合數(shù)學(xué)基礎(chǔ)250 22+3´16 4 × 816 4(7 + 1)16組合數(shù)學(xué)éæ16ör ù16 4ê1 +

52、 åç÷7 ú 4（mod 7）rr =1 èøëûæ100rö100另法：10100 (7 + 3)100 å3+ç÷7 ×100rr =1 èø3100 3 × 2733 3(28 + (- 1)33é(æ 33333ê - 1+ åç33rër =1 è3(- 1)33 34（mod 7）（六） 問題ö8æc請(qǐng)給出多項(xiàng)式ç

53、 a - 2b + 3d ÷ 的展開式中a 2b2c 2d 2 和è2øbc5d 2 兩項(xiàng)的系數(shù)（答：22680, 189/2）。1.61. 6. 1序數(shù)法（一） 數(shù)的位權(quán)表示（1）十進(jìn)制數(shù)：小于10r 的正整數(shù) n 的位權(quán)形式：r -1排列的生成算法n = åa 10k ， 0 a 910kkk = 0例 315 3 ´ 102 + 1´ 101 + 5 ´ 100 （r3）（2）推廣（p 進(jìn)制數(shù)）r -1n = å a pk ， 0 a pkkk = 0（3）特點(diǎn)：固定進(jìn)制；逢 p 進(jìn)一；十進(jìn)制r 位數(shù)最小為0，最大為 999910r 110r ；將十進(jìn)制換算為p 進(jìn)制數(shù)方法：除 p ?。ǘ?變進(jìn)制表示。（1）依據(jù)：n!(n1)(n1)!(n1)!遞歸：n!(n1)(n1)!(n2)(n2)!(n2)!24/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)(n1)(n1)!(n2)