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

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

2、2，4，6，8，10，12，14，16，18 填入下列幻方：1/5143884921. 排列組合的基本計數(shù)問題2. 多項式系數(shù)的計算及其組合意義3. 排列組合算法第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)【例 1.1.1】（拉丁方）36 名軍官問題：有 1，2，3，4，5，6 共六個團(tuán)隊，從每個團(tuán)隊中分別選出具有A、B、C、D、E、F 六種軍銜的軍官各一名，共 36 名軍官。問能否把這些軍官排成 6×6的方陣，使每行及每列的 6 名軍官均來自不同的團(tuán)隊且具有不同軍銜？本問題的是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】（計數(shù)圖形染色）用 3 種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個頂點，若某種染色方案在正方形旋轉(zhuǎn)某個角度后，與另一個方案重合，則認(rèn)為這兩個方案是相同的。求本質(zhì)上不同的染色方案。舉例：（a）（b）2/51ybrbrybb第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)形式總數(shù)： 34 81 種。實際總數(shù)（見第 6 章）：L 1 (3

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

5、程重點：以組合計數(shù)理論為主，部分涉及其它內(nèi)容。（三） 研究方法分類：第一類：從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)方法（利用原理、二項式定理、Pólya 定理解計數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。第二類：通常與問題所涉及的組合學(xué)概念無關(guān)，而對多種問題均可使用。例如：（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） 一一對應(yīng)技術(shù)原理：建立兩類事物之間的一一對應(yīng)關(guān)系，把一個較復(fù)雜的組合計數(shù)問題 A 轉(zhuǎn)化成另一個容易計數(shù)的問題 B，從而利用對 B的計數(shù)運(yùn)算達(dá)到對 A 的各種不同方案的計數(shù)。思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式。（4） 殊途同歸方法原理：從不同角度討論計數(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)行多少場比賽？（解）常規(guī)思路：502512632199 場10000 名選手：5000250012506253121采用一一對應(yīng)方法：每場比賽產(chǎn)生一個失敗者，且每個失敗者只能失敗一次（場次失敗者）。反之，要淘汰一個選手，必 須恰好經(jīng)過一場比賽（失敗者場次）。結(jié)論：失敗者« 比賽場次。應(yīng)該比賽 99 場。4/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)一般情況：單循環(huán)淘汰制，n 個選手，比賽n - 1場?！纠?1.1.5】設(shè)某地的街道將城市分割

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

9、 nm + n1.2 兩個1. 2. 1加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個方案，而第一個方案有 m 種方法，第二個方案有 n 種方法可以實現(xiàn)。只要選則擇任何方案中的某法，就可以完成這件事情，并且這些方法兩兩互不相同。則完成這件事情共有 mn 種方法。5/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)l集合描述：設(shè)有限集合 A 有 m 個元素，B 有 n 個元素， 且 A 與 B 不相交，則 A 與 B 的并共有 mn 個元素。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 人，從中選出一名代表參加會議，問共有多少種選法？（解）（1）兩個選擇方案：男生（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】用一個小寫英文字母或一個器編號，問總共可能編出多少種號碼？（解）261036 個。其中英文字母共有 26 個，數(shù)字 09 共 10 個。1. 2

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

12、礎(chǔ)組合數(shù)學(xué)l 概率角度描述：設(shè)離散型隨量 X 有 m 個取值，Y 有 n個取值，則離散型隨機(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 個字符，其中首字符要求用字母 AG 或 UZ，后兩個要求用數(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相異元素不（一） 計算公式重復(fù)的排列數(shù)和組合數(shù)從 n 個相異元素中不重復(fù)地取 r 個元素的排列數(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）特點：排列考慮順序，組合不然。（二） 數(shù)學(xué)模型（1）排列問題：將 r 個有區(qū)別的球放入 n 個不同的盒子，每盒不超過一個，則總的放法數(shù)為P r 。n（2）組合問題：將 r 個無區(qū)別的球放入 n 個不同的盒子，每盒不超過一個，則總的放法數(shù)為C r 。n8/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)1.

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

17、12n12n9/51對應(yīng)關(guān)系元素« 盒子位置« 球元素和位置編號12345A B C排列 1ABC1 1 4排列 2C BA4 3 3排列 3A CB3 4 3排列 4A B C2 2 2排列 5BAC4 2 5對應(yīng)關(guān)系元素« 盒子位置« 球元素和位置編號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 個元素，求其排列數(shù)將 r 個有區(qū)別的球放入 t 個不同的盒子，每個盒子的容量有限，其中第 i 個盒子最多只能放入ni 個球，求分配方案數(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對應(yīng)關(guān)系元素« 盒子位置« 球元素和位置編號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 個有標(biāo)號的珠子排成一個圓圈，共有多少種不同的排法？（解）稱為圓排列（相對于線排列）。條件：元素同時按同一方向旋轉(zhuǎn)，絕對位置變化，相對位置未變，即元素間的相鄰關(guān)系未變，視為同一圓排列。結(jié)論：1 個圓排列對應(yīng) n 個線排列。CP(n, n) = P(n, n) (n1)!n3254125413541324132513

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

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

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

24、）兩個字母間各4 個間隔內(nèi)，有 1 種方案。3 個空格，將 12 個空格均勻地放入c b d e a（3）將余下的 3 個空格4 個間隔：分析：將 3 個相同的球放入 4 個不同的盒子，盒子的容量不限。方案 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(個相異元素中可重復(fù)地取 3 個元素的組合數(shù)¥, 3) = C= 20 。34+ 3-1（4）總方案數(shù)： L

25、5！·1. 3. 6不盡相異元素1·202400r 個的組合問題（一） 問題設(shè)集合S = n1 × e1 , n2 × e2 , L,nt × et （ n1 + n2 + L + nt= n ），從 S 中r 個，求其組合數(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 有幾個正約數(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)造多項式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6系數(shù)求和： t = å RC (6, i )135653124i=0方法化簡：求 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） 組合意義法：借助于闡明等號兩端的不同表實質(zhì)上是同一個組合問題的方案數(shù)（殊途同歸法），或者雖是兩個不同組合問題的方案數(shù)，但二者的組合方案之間存在著一一對應(yīng)關(guān)系，因此等式兩端必須相等，從而達(dá)到證明等式成立的目的。對于恒等式的實質(zhì)刻。得更為深（3） 母函數(shù)法：利用無窮級數(shù)（包括有限時的多項式）證明有關(guān)組合等式。是產(chǎn)生和證明組合恒等式的普遍方法。（4） 其它方法：二項式展開、反演公式等【等式 1】對稱關(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 個的組合情況：15/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)第一類（包含元素“1”）：第二類（不包含“1”）：123，124，125，134，135，145234，235，245，345（三）路徑問題：等價形式+ Cm -1Cm= Cmm + nm + n-1m + n-1組合意義：從（0，0）點到（m，n）點的路徑數(shù)等于從（0，

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

31、20 13 5推廣：n 個元素分為 t 堆，且可以若干堆個數(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 個相異的紅球，m 個相異的藍(lán)球，選 r 個的組合。分類統(tǒng)計：i 個紅球，ri 個藍(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 個相異元素選 i 個的組合« 兩類元素的 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ā)：存在一一對應(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 個大小相同的球，其中r 個，其余為黑球。每次摸出一個球，不放回，直至摸到白球為止。是必然（遲早會摸到），概率為 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 時，n-må nm+km= 2n-m× CmCCm+knk=0組合意義：從 n 人中選出 m 名正式代表及若干名列席代表的選法（列席代表人數(shù)不限）。統(tǒng)計方法一：先選正式代表，再從n - m 人中選列席代表，2n-m ?？偟倪x法為C mn統(tǒng)計方法二：先選 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 多項式系數(shù)（一） Newton 二項式(1) 二項展開式Newton 二項式定理（n 是正整數(shù)）n(a + b)n =C a bår r n-rnr =0右端稱為二項式(ab)n 的展開式，C r 叫做二項式系數(shù)。n(2) 組合意義分配問題：將 n 個相異的球放入兩個盒子，a 盒放入n1 = r 個，b 盒放入n2 = n - r 個，同盒的球不分次序，方案數(shù)為n!n! r!×(n - r )!n1 !×n2 !rn-r即a b項的系數(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ù)的根源：同一單項式中有順序，即排列問題（球不同的分配問題）。排列問題：從兩種元素中選 n 個的排列（a 選r 個，b 選n - r個）（二） 一般分配問題問題：將 n 個相異的球放入 t 個盒子，要求第 1 個盒子放入n1個，第 2 個盒子放入n2 個，第 t 個盒子放入nt 個，且盒中的球無次序，求不同的分配方案數(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ö仿照二項式系數(shù)ç÷ ，記為ç÷ 。è r øè n1n2 Lnt ø20/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)（三） 多項式系數(shù)æönç÷一般多項式系數(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個因子連乘（1）所有n，且å n= nn2n1L21ii =1nt 項，（2）一般項的系數(shù)： n 個因式中選取 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ö稱ç÷為多項式系數(shù)。è n1n2 Lnt ø（四） 多項式展開的項數(shù)【定理 1.5.2】(+ L+展開式的項數(shù)等于C n，21t + n-1而這些項的系數(shù)之和為t n .（證）展開式的項中取 n 個的 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（項）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的展開式中，項a a a a 的123451 3 4 522/51第一章組合數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)系數(shù)。æ71öçè 2【例 1.5.3】在(÷ =4202!×0!031ø+-531的展開式中，項系數(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（證）（證明組合等式）在二項式中取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 è等價問題：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請給出多項式ç

53、 a - 2b + 3d ÷ 的展開式中a 2b2c 2d 2 和è2øbc5d 2 兩項的系數(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）特點：固定進(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)