1、離散數學組合數學 2 / 24排列與組合的推廣在許多計數問題里元素可以被重復使用. 前面我們只考慮每個元素至多可以使用一次的排列和組合, 下面介紹怎樣求解元素可以多次使用的計數問題.計數單詞SUCCESS的字母可能被重新排列的方式數, 必須考慮相同字母的放置. 這與前面討論的所有元素都被認為是不同的計數問題大相徑庭.計數把不同的元素放入盒子的方法數, 如把撲克牌發給4個玩牌人的不同的方式數. 3 / 24多重集的排列與組合定義 多重集 S=n1 a1, n2 a2, , nk ak , 0ni+, n=n1+n2+nk 表示 S 中元素的總數.(1) 從S 中有序選取的r個元素稱為多重集 S

2、的一個 r 排列. r = n 的排列稱為 S 的全排列(2) 從 S 中無序選取的 r 個元素稱作多重集 S 的一個r 組合 注意:多重集中元素的重復度, 0 ni +; 當ni+, 表示ai重復選取的次數沒有限制S的子集 X=x1 a1, x2 a2, , xk ak, 其中0 xi ni允許重復選取含義: 紅球, 藍球允許重復的r排列/組合等價于 S= 紅球, 藍球的r排列/組合 4 / 24多重集的全排列定理 設類型1的相同的物體有n1個, 類型2的相同的物體有n2個, , 類型k的相同的物體有nk個, 那么n (=n1+n2+nk )個物體的不同排列(全排列)數是 方法二放球問題:

3、把n個不同的物體分配到k個不同的盒子使得ni個物體放入盒子i (i=1,2,k)的方式數123n方法一 分k步處理: 1.選n1個位置放類型1物體2.在剩下位置選n2個放類型2物體k.在剩下位置選nk個放類型k物體1122223311222233 5 / 24多重集的 r 排列定理 集合S=a1,a2,ak允許重復的r排列數是kr 多重集 S=n1 a1, n2 a2, , nk ak的r排列( ni = +或rni)分r步處理1.安排1號位置【k種方式】2.安排2號位置【k種方式】r. 安排r號位置【k種方式】所求的 r 排列數是 kk = kr 6 / 24多重集的 r 組合定理 集合S=

4、a1,a2,ak允許重復的r組合數為C(r+k1,r)多重集S=n1 a1, n2 a2, , nk ak的r組合( ni = +或rni)證 S的r組合t1 a1, t2 a2, , tk ak (t1+t2+tk = r)不定方程x1+x2+xk = r的非負整數解 xi = tiN, t1+t2+tk = r 0.01001100t1個0t2個0tk個0r個0, k1個1的全排列 7 / 24例例 r個相同的球放到n個不同的盒子里, 每個盒子球數不限, 求放球方法數.解x1+x2+xn = r 的非負整數解 C(n+r1, r) 8 / 24例例 9本不同的書, 其中4本紅皮, 5本白皮

5、(1)9本數的排列方式數有多少?(2)若白皮書必須放在一起, 有多少方法?(3)若白皮書必須放在一起, 紅皮書也必須放在一起, 有多少方法?(4)若白皮書和紅皮書必須相間, 有多少方法? 解(1) P(9,9)(2) P(5,5) P(5,5)(3) P(5,5) P(4,4) P(2,2)(4) P(5,5) P(4,4) 9 / 24例例 從S=1,2,n中選擇k個不相鄰的數, 有多少種方法?解 (應用一一對應的思想求解)a1,a2,ak: k個不相鄰的數, 屬于集合1,2,n對應規則: bi = ai(i1), i=1,2,kb1,b2,bk: k個允許相鄰的數, 屬于集合1,2,n(k

6、1)因此 N = C(nk+1,k) 10 / 24例例 在下面的偽碼被執行后k的值是多少?k:=0for i1:=1 to nfor i2:=1 to i1for im:=1 to im1k:=k+1關鍵在于求解 k增1的次數滿足1imim1i1n的整數序列i1,i2,im的個數從1,2,n中允許重復地選擇m個整數的方式數i1,i2,im代碼執行后k = C(n+m1, m)m組合降序排列 11 / 24多項式定理定理 多項式定理 設n為正整數, xi為實數 求和是對滿足方程n1+n2+nt=n的一切非負整數解求和求和是對滿足方程n1+n2+nt=n的一切非負整數解求和 1.在n個(x1+x

7、2+xt)選n1個提供x12.在剩余的nn1個(x1+x2+xt)選n2個提供x2t. 在剩余的nn1nt1個(x1+x2+xt)選nt個提供xt 12 / 24多項式定理多項式系數組合含義1.多重集S=n1a1,n2a2,ntat的全排列數2. n個不同的球放到t個不同的盒子使得第一個盒子含n1個球, 第二個盒子含n2個球, 第t個盒子含nt個球的方案數 13 / 24推論推論 多項式展開式中不同的項數為方程n1+n2+nt=n的非負整數解的個數C(n+t1,n)推論多項式系數恒等式 按某個指定的球放入盒子情況分t類處理 123nn1n2nt 14 / 24例證明Fermat小定理: p為素

8、數, 則p | (np-n)證 15 / 24組合恒等式解題方法小結證明方法已知恒等式代入二項式定理冪級數的求導, 積分歸納法組合分析求和方法帕斯卡公式級數求和觀察和的結果, 然后使用歸納法證明利用已知的公式 16 / 24練習把10個不同的球放到6個不同的盒子里, 允許空盒, 且前2個盒子球的總數至多是4, 有多少種方法?解 按前2個盒子放球的總數k (0k4)分5類處理對第k類分步處理: (0k4)第一步從10個不同球里選擇k個放入前2個盒子, 方法數為C(10,k)2k第二步將剩下的10k個球放到后4個盒子, 方法數為410k總方法數 17 / 24練習續由m個A和n個B構成序列, 其中

9、m,n為正整數, mn. 如果要求每個A后面至少緊跟著1個B, 有多少個不同的序列?解 方法一 分步處理1.先放n個B (1種方法)2.再在B的間隙(n個位置) 選擇m個放A 方法數為C(n,m) 所求序列數為C(n,m)BBBBBBAAAn個Bn個間隙m個A 18 / 24練習續由m個A和n個B構成序列, 其中m,n為正整數, mn. 如果要求每個A后面至少緊跟著1個B, 有多少個不同的序列?解 方法二 分步處理1 先將AB兩兩組合放好 (m組) 1種方法2 再將剩下的nm個B 插入 m+1 個間隙第2步等價于將nm個相同的球放入m+1個不同的盒子的方法數C(nm+m+11,nm) =C(n

10、,m)ABBBBm個ABm+1個間隙ABABABnm個B 19 / 24練習續設S是n元集, N表示滿足ABS的有序對的個數, 證明N=3n.證 方法一 分n步處理: S中每個元素x有 3 種選擇: xAxB; xAxB; xAxB 因此總方法數為3n.方法二 按A的元素個數k (0kn) 分 n+1類處理. 第k類: |A|=k 分步處理: 第一步從S中選擇k個構成A, C(n,k)種方法; 第二步從剩下的nk個元素中選擇任意可能的元素加入A中構成B, 方法數為2nk.總方法數為 20 / 24練習續證明方法一 21 / 24練習續證明方法二 22 / 24練習續求和解 方法一帕斯卡恒等式 23 / 24練習續求和解 方法二變上項和 24 / 24練習續證明上式等價于S=1, 2, 3, ., n, n+1, , n+r, n+r+1:右邊是對S的 nm+r+1 元子集計數;左邊對S的nm+r+1 元子集A的選取按如下方式分類處理: 按A中第 r+1 大的元素 a 分類: 比 a 小的有 nm 個,