離散組合數(shù)學(xué)1多重集的排列與

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

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

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

4、a1,a2,ak允許重復(fù)的r組合數(shù)為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的非負(fù)整數(shù)解 xi = tiN, t1+t2+tk = r 0.01001100t1個0t2個0tk個0r個0, k1個1的全排列 7 / 24例例 r個相同的球放到n個不同的盒子里, 每個盒子球數(shù)不限, 求放球方法數(shù).解x1+x2+xn = r 的非負(fù)整數(shù)解 C(n+r1, r) 8 / 24例例 9本不同的書, 其中4本紅皮, 5本白皮

5、(1)9本數(shù)的排列方式數(shù)有多少?(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個不相鄰的數(shù), 有多少種方法?解 (應(yīng)用一一對應(yīng)的思想求解)a1,a2,ak: k個不相鄰的數(shù), 屬于集合1,2,n對應(yīng)規(guī)則: bi = ai(i1), i=1,2,kb1,b2,bk: k個允許相鄰的數(shù), 屬于集合1,2,n(k

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

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

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

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

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