1、1,第8章 組合計數基礎,2,第8章 組合計數基礎,引言 組合問題的處理技巧 8.1 基本計數規(guī)則 8.2 排列與組合 8.3 二項式定理與組合恒等式 8.4 多項式定理,3,組合問題的處理技巧,一一對應 數學歸納法 上下界逼近,4,一一對應與上下界逼近,例1 在允許移動被切割的物體的情況下，最少用多少次切割可以將 333 的立方體切成 27個單位邊長的立方體？,中間的小立方體的6個面都是切割產生的面，每次切割至多產生一個面，至少需要6次切割。存在一種切割方法恰好用 6 次切割。,例2 100個選手淘汰賽，為產生冠軍至少需要多少輪比賽？ 方法1：50+25+12+6+3+2+1=99 方法2：

2、比賽次數與淘汰人數之間存在一一對應，總計淘汰99人，因此至少需要99場比賽.,5,8.1 基本計數規(guī)則,8.1.1 加法法則 8.1.2 乘法法則 8.1.3 分類處理與分步處理,6,加法法則,加法法則：事件A 有 m 種產生方式，事件 B 有n 種產生方式，則 “事件A或B” 有 m+n 種產生方式. 使用條件：事件 A 與 B 產生方式不重疊 適用問題：分類選取 推廣：事件 A1有 p1種產生方式，事件 A2有 p2 種產生方式，, 事件 Ak 有 pk 種產生的方式，則 “事件A1或 A2或 Ak” 有 p1+p2+pk 種產生的方式.,7,乘法法則,乘法法則：事件A 有 m 種產生方式

3、，事件 B 有n 種產生方式，則 “事件A與B” 有 m n 種產生方式. 使用條件：事件 A 與 B 產生方式彼此獨立 適用問題：分步選取 推廣：事件 A1有 p1種產生方式，事件 A2有 p2 種產生方式，, 事件 Ak 有 pk 種產生的方式，則 “事件A1與 A2與 Ak” 有 p1 p2 pk 種產生的方式.,8,分類處理與分步處理,分類處理：對產生方式的集合進行劃分，分別計數，然 后使用加法法則 分步處理：一種產生方式分解為若干獨立步驟，對每步 分別進行計數，然后使用乘法法則 分類與分步結合使用： 先分類，每類內部分步 先分步，每步又分類,9,應用實例,例3 設A, B, C 是3

4、個城市，從A 到 B 有3條道路，從B 到 C 有2條道路，從A 直接到 C 有4條道路，問從 A 到 C 有多少種不同的方式？ 解： N=32+4 = 10 例4 求1400的不同的正因子個數 1400=23 52 7 解：正因子為：2i 5j 7k，其中 0i3, 0j2, 0k1 N=(3+1)(2+1)(1+1)=24,10,8.2 排列與組合,引言 選取問題 8.2.1 集合的排列與組合 8.2.2 多重集的排列與組合,11,選取問題 -組合計數模型1,設 n 元集合 S，從 S 中選取 r 個元素. 根據是否有序，是否允許重復可以將該問題分為四個子類型,12,集合的排列,定義 從

5、n 元集 S 中有序、不重復選取的 r 個元素稱為 S 的一個 r 排列，S 的所有 r 排列的數目記作 P(n,r) 定理8.1 證明 使用乘法法則 推論 S 的環(huán)排列數 =,13,集合的組合,定義 從 n 元集 S 中無序、不重復選取的 r 個元素稱為 S 的一個 r 組合，S 的所有 r 組合的數目記作 C(n,r) 定理8.2,推論 設n, r為正整數，則 (1) C(n, r)= (2) C(n, r) = C(n, nr) (3) C(n, r)=C(n1,r1)+C(n1,r),14,證明方法,方法1：公式代入并化簡 方法2：組合證明 實例：證明 C(n, r) = C(n, n

6、r) 證 設 S =1, 2, , n是n元集合，對于S 的任意 r-組合 A=a1, a2, , ar，都存在一個S 的 nr 組合SA與之對應. 顯然不同的 r 組合對應了不同的 nr 組合，反之也對，因 此 S 的 r 組合數恰好與 S 的(nr)組合數相等. C(n, r)=C(n1,r1)+C(n1,r) 稱為 Pascal公式，也對應了楊 輝三角形， 兩種證明方法都適用.,15,楊輝三角,16,基本計數公式的應用,解 分類選取 A = 1, 4, ,298 B = 2, 5, ,299 C = 3, 6, , 300 分別取自 A, B, C: 各 C(100,3) A, B, C

7、 各取 1 個（分步處理）： C(100,1)3 N= 3C(100,3) + 1003 = 1485100,例8.5 從1300中任取3個數使得其和能被3整除有多少種方法？,17,基本計數公式的應用(續(xù)),解: 1000!=1000 999 998 21 將上面的每個因子分解，若分解式中共有i 個5, j 個2， 那么min(i, j)就是0的個數. 1, ,1000中有 500個是 2 的倍數，j 500; 200個是 5 的倍數， 40個是 25 的倍數（多加 40 個 5）， 8個是 125 的倍數（再多加 8 個 5）， 1個是 625 的倍數（再多加 1 個 5） i = 200+

8、40+8+1 = 249. min(i, j)=249.,例2 求1000！的末尾有多少個0？,18,基本計數公式的應用(續(xù)),例3 設A為 n 元集，問 (1) A上的自反關系有多少個？ (2) A上的反自反關系有多少個？ (3) A上的對稱關系有多少個？ (4) A上的反對稱關系有多少個？ (5) A上既不對稱也不是反對稱 的關系有多少個？,19,多重集的排列,定理8.3 多重集S=n1a1, n2a2, , nkak，0 ni + (1) 全排列 r = n, n1 + n2 + + nk = n 證明：分步選取. 先放a1, 有C(n,n1) 種方法；再放a2, 有 C(n n1,n2

9、)種方法, . , 放ak,有C(nn1n2 nk1,nk) 種方法 (2) 若r ni 時，每個位置都有 k 種選法，得 kr.,20,多重集的組合,定理8.4 多重集 S=n1a1, n2a2, , nkak，0ni + 當 r ni , S的r 組合數為 N = C(k+r1,r), 證明 一個 r 組合為 x1a1, x2a2, , xkak， 其中 x1 + x2 + + xk = r , xi 為非負整數. 這個不定方程的非負整數解對應于下述排列 11 0 11 0 11 0 0 11 x1個 x2個 x3個 xk個 r 個1，k1個 0 的全排列數為,21,實例,例5 排列26個

10、字母，使得 a 與 b 之間恰有7個字母，求方法數.,解： 設盒子的球數依次記為 x1, x2, , xn, 則滿足 x1 + x2 + + xn = r， x1, x2, , xn 為非負整數 N = C(n+r1, r),例4 r 個相同的球放到 n 個不同的盒子里，每個盒子球數不限，求放球方法數.,解： 固定a 和 b, 中間選7個字母，有2 P(24,7)種方法， 將它看作大字母與其余17個字母全排列有18！種，共 N = 2 P(24,7) 18!,22,實例(續(xù)),例6 (1) 10個男孩，5個女孩站成一排，若沒有女孩相鄰， 有多少種方法？ (2) 如果站成一個圓圈，有多少種方法？

11、,解: (1) P(10,10) P(11,5) (2) P(10,10) P(10,5)/10,解：相當于2n 不同的球放到 n 個相同的盒子，每個盒子2個，放法為,例7 把 2n 個人分成 n 組，每組2人，有多少分法？,23,實例(續(xù)),解 使用一一對應的思想求解這個問題. a1, a2, , ak ：k個不相鄰的數, 屬于集合1, 2, , n b1, b2, , bk：k個允許相鄰的數, 屬于集合1, , n(k1) 對應規(guī)則是 bi = ai(i1). i =1, 2, , k 因此 N = C(nk+1,k),例8 從S=1, 2, , n中選擇 k 個不相鄰的數，有多少種方法？

12、,24,8.3二項式定理與組合恒等式,8.3.1 二項式定理 8.3.2 組合恒等式 8.3.3 非降路徑問題,25,二項式定理,定理8.5 設 n 是正整數，對一切 x 和 y 證明方法: 數學歸納法、組合分析法. 證 當乘積被展開時其中的項都是下述形式：xi yni, i = 0, 1, 2, , n. 而構成形如 xiyni 的項，必須從n 個 和 (x+y) 中選 i 個提供 x，其它的 ni 個提供 y. 因此， xiyni 的系數是 ，定理得證.,26,二項式定理的應用,例1 求在(2x3y)25的展開式中x12y13的系數. 解 由二項式定理 令i =13 得到展開式中x12y1

13、3的系數，即,27,組合恒等式遞推式,證明方法：公式代入、組合分析 應用： 1式用于化簡 2式用于求和時消去變系數 3式用于求和時拆項（兩項之和或者差），然后合并,28,組合恒等式變下項求和,證明公式4. 方法：二項式定理或者組合分析. 設S=1,2,n，下面計數S 的所有子集. 一種方法就是分類處理，n元集合的 k子集個數是,根據加法法則，子集總數是,另一種方法是分步處理，為構成 S 的子集A，每個元素有 2 種選擇，根據乘法法則，子集總數是2n.,29,恒等式求和變系數和,證明方法： 二項式定理、級數求導 其他組合恒等式代入,30,證明公式6 (二項式定理+求導),31,證明公式7 (已知

14、恒等式代入),32,恒等式變上項求和,證明 組合分析. 令S=a1, a2, , an+1為n+1元集合. 等式右邊是 S 的 k+1子集數. 考慮另一種分類計數的方 法. 將所有的k+1元子集分成如下n+1類： 第1類：含a1, 剩下 k個元素取自a2,an+1,第2類：不含a1,含a2, 剩下k個元素取自 a3, , an+1, 不含a1, a2, , an, 含an+1,剩下k個元素取自空集,由加法法則公式得證,33,恒等式乘積轉換式,證明方法：組合分析. n 元集中選取 r 個元素，然后在這 r 個元素中再選 k個 元素. 不同的 r 元子集可能選出相同的 k子集，例如 a, b, c

15、, d, e a, b, c, d b, c, d b, c, d, e b, c, d 重復度為： 應用：將變下限 r 變成常數 k，求和時提到和號外面.,34,恒等式積之和,關系,證明思路：考慮集合A=a1,a2,am，B=b1,b2,bn. 等 式右邊計數了從這兩個集合中選出r個元素的方法. 將這 些選法按照含有A中元素的個數 k 進行分類，k=0,1,r. 然后使用加法法則.,35,組合恒等式解題方法小結,證明方法： 已知恒等式帶入 二項式定理 冪級數的求導、積分 歸納法 組合分析 求和方法： Pascal公式 級數求和 觀察和的結果，然后使用歸納法證明 利用已知的公式,36,非降路徑

16、問題,基本計數模型 限制條件下的非降路徑數 非降路徑模型的應用 證明恒等式 單調函數計數 棧的輸出,37,基本計數模型,(0,0) 到 (m,n) 的非降路徑數：C(m+n, m) (a,b) 到 (m,n)的非降路徑數： 等于 (0,0) 到 (ma,nb) 的非降路徑數 (a,b) 經過 (c,d) 到 (m,n) 的非降路徑數：乘法法則,38,限制條件的非降路徑數,從(0,0)到(n,n)不接觸對角線的非降路徑數 N N1：從(0,0) 到 (n,n) 下不接觸對角 線非降路徑數 N2：從(1,0)到(n,n1) 下不接觸對角 線非降路徑數 N0: 從(1,0)到(n,n1) 的非降路徑

17、數 N3: 從(1,0)到(n,n1) 接觸對角線的 非降路徑數 關系: N=2N1=2N2=2N0 N3,39,一一對應,N3: 從(1,0)到(n,n1) 接觸對角線的 非降路徑數 N4: 從(0,1)到(n,n1) 無限制條件的 非降路徑數 關系: N3=N4,40,應用證明恒等式,例2 證明 證： 計數(0,0)到(m+nr,r) 的非降路徑數 按照 k分類，再分步. (0,0)到(mk,k)路徑數， (mk,k)到(m+nr,r)的路徑數,41,應用單調函數計數,例3 A=1,2,m, B=1,2,n， N1:B上單調遞增函數個 數是(1,1)到 (n+1,n) 的非降路徑數 N:

18、B上單調函數個數 N=2N1 N2: A到B單調遞增函數個 數是從(1,1)到 (m+1,n) 的非降路徑數 N: A到B的單調函數個數，N =2N2 嚴格單調遞增函數、遞減函數個數都是C(n,m),42,函數計數小結,A = 1, 2, , m, B = 1, 2, , n f: AB,43,應用棧輸出的計數,例4 將1,2,n按照順序輸入棧,有多少個不同的輸出序列？ 解：將進棧、出棧分別記作 x,y, 出棧序列是n個x，n個y的排列，排列中任何前綴的 x 個數不少于y 的個數. 等于從 (0,0) 到 (n,n) 的不穿過對角線的非降路徑數. 實例：n=5 x, x, x ,y, y, x, y, y, x, y 進,進,進,出,出,進,出,出,進,出 3, 2, 4, 1, 5,44,應用棧輸出的計數(續(xù)),N: 堆棧輸出個數 N:(0,0)到(n,n)不 穿過對角線的 非降路徑數 N0:(0,0)到(n,n)的 非降路徑總數 N1:(0,0)到(n,n)的 穿過對角線的 非降路徑數 N2:(1,1)到(n,n) 的非降路徑數. 關系：N=N =N0N1, N1=