复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）12/30

推论16:设k元多重集S={∞a1,a2,,aa},r≥k, 若要求S的k个不同元素的每一个至少在组合中出 现一次,则S的这种r组合数是C(r-1,k-l) 证明:任取一个所求的r组合,则S中所有不同元 素a1,a2,a1都在此组合中出现(推论条件规定) 现从这组合中拿走元素a1,a2,a,即得S的一个 rk组合。 而对于S的任一个rk组合,加入元素a1,a2, ·k9 就是一个含有S中所有不同元素的r组合。 ◆因此,S的k个不同元素的每一个至少在组合中出 现一次的r组合数就是S的r组合数, ◆C(k+(r-k)-1,rk)=C(r-1,r-k)=C(r-1,(r-1)-(r k)=C(r-1,k-1)

 推论11.6:设k元多重集S={·a1 ,·a2 ,…, ·ak },rk, 若要求S的k个不同元素的每一个至少在组合中出 现一次，则S的这种r-组合数是C(r-1,k-1)。  证明：任取一个所求的r组合，则S中所有不同元 素a1 ,a2 ,…,ak都在此组合中出现(推论条件规定)，  现从这组合中拿走元素a1 ,a2 ,…,ak，即得S的一个 r-k组合。  而对于S的任一个r-k组合，加入元素a1 ,a2 ,…,ak， 就是一个含有S中所有不同元素的r组合。  因此，S的k个不同元素的每一个至少在组合中出 现一次的r-组合数就是S的r-k组合数，  C(k+(r-k)-1,r-k)=C(r-1,r-k)=C(r-1,(r-1)-(r￾k))=C(r-1,k-1)

◆例:一家商店卖6种面包 客户要买 12只面包,问有多少种不同选择方案每 种面包数量足够多)? 解:买12只面包,没有次序要求,是组 合问题。 ◆商店里每种面包数量远大于12。 ◆即S{x1a1x2a2…,x6“a6}(x÷≥12),由推论 5得 ◆N=C(6+12-1,12)=C(17,12)=C(17,5)=6188

 例：一家商店卖6种面包，，一客户要买 12只面包，问有多少种不同选择方案(每 种面包数量足够多)？  解：买12只面包，没有次序要求，是组 合问题。  商店里每种面包数量远大于12。  即S={x1·a1 ,x2·a2 ,…, x6·a6 }(xi12)，由推论 5得  N=C(6+12-1,12)=C(17,12)= C(17,5)=6188

◆例:一个棋手要在相继的7天内下12盘棋,问 有多少种安排法?如果要求每天至少下一盘棋其, 又有多少种安排法? ◆解:将这相继的7天记为a1,a2,a3,24,as,,a7, ◆则第一种安排相当于多重集S={oa1oa2oa, oa4,oa5,oa,·a7}的12-组合问题。 ◆由定理11即得C(7+12-1,12)=C(18,12) =C(18,6)。 ◆而第二种安排相当于S的每种元素至少取1个 的12组合问题, ◆由推论6得C(12-1,7-1)=C(116)=C(115)

 例：一个棋手要在相继的7天内下12盘棋，问 有多少种安排法? 如果要求每天至少下一盘棋， 又有多少种安排法？  解：将这相继的 7 天记为a1 ,a2 ,a3 ,a4 ,a5 ,a6 ,a7，  则第一种安排相当于多重集S={·a1 ,·a2 ,·a3 , ·a4 ,·a5 ,·a6 , ·a7 }的12-组合问题。  由定理 11.11 即 得 C(7+12-1,12)=C(18,12) =C(18,6)。  而第二种安排相当于S的每种元素至少取1个 的12-组合问题，  由推论11.6得C(12-1,7-1)=C(11,6)= C(11,5)

◆例:确定多重集S={1·a1oa2x,.}的r组合数 ◆解:把S的r组合分成两类: ◆(1)包含a的r组合, 相当于{oa2,.a}的(r-1)-组合(k-个不同元 素) ◆因此包含a1的r组合数是C(k-1)-1+(r-1),r 1)=C(kr3,r-1) ◆(2)不包含a的r组合, 相当于{∞:a2x,.a的r组合(k个不同元素) ◆因此不包含a的r组合数是C(k-1)-1+r,r)=C(k+r 所以多重集S={1·a1,∞o2a2x,.a}的r组合数是: ◆C(k+r-3,r-1)+C(k+r-2,r)o

 例：确定多重集S={1·a1 ,·a2 ,…,·ak }的r-组合数  解：把S的r-组合分成两类：  (1)包含a1的r-组合,  相当于{·a2 ,…,·ak }的(r-1)-组合(k-1个不同元 素),  因此包含 a1 的 r- 组合数是 C((k-1)-1+(r-1),r- 1)=C(k+r-3,r-1)。  (2)不包含a1的r-组合,  相当于{·a2 ,…,·ak }的r-组合(k-1个不同元素),  因此不包含a1的r-组合数是C((k-1)-1+r,r)=C(k+r- 2,r)。  所以多重集S={1·a1 ,·a2 ,…,·ak }的r-组合数是：  C(k+r-3,r-1)+C(k+r-2,r)

◆关于有限多重集的组合问题小结如下 设 S=(n, n2 a2,..., nk agy n=n1+n2++m},则S的r组合数N满足 ◆(1)若r>m,则N=0 ◆(2)若r=m,则N=1 3(3)若r<n,且对一切=,2,,有n≥r,则: N=C(k+r-1, r) ◆(4)若r<m,且存在着某个nr,则对N没有 般的求解方法,可利用容斥原理予以 解决

 关于有限多重集的组合问题小结如下:  设 S={n1·a1 ,n2·a2 ,…,nk·ak } ， n=n1+n2+…+nk }，则S的r-组合数N满足:  (1)若r>n，则N=0。  (2)若r=n，则N=1。  (3)若r<n，且对一切i=1,2,…,k有nir，则： N=C(k+r-1,r)  (4)若r<n，且存在着某个ni<r,则对N没有 一般的求解方法，可利用容斥原理予以 解决

四、有序划分和无序划分 设S是n个元素的集合。AS, A≠,=1,2…t且A1UA2U.UA=S, A∩A(ij=1,2…,i≠j),则称 I={41,A2,A是S的一个划分。 这里{4142,,是一个集合,即是 无序划分。 如果块与块之间有先后次序之分,则 记为(A1,A2,,A),为S的一个块 有序划分

四、有序划分和无序划分 设S是n个元素的集合。AiS, Ai,i=1,2,…t,且A1∪A2∪…∪At=S, Ai∩Aj =(i,j=1,2,…,t,ij),则称 ={A1 ,A2 ,…,At }是S的一个划分。 这里{A1 ,A2 ,…,At }是一个集合，即是 无序划分。 如果块与块之间有先后次序之分，则 记为（A1 ,A2 ,…,At），为S的一个t块 有序划分

Q∴1有序划分 ◆定义一:设S是n个元素的集合 {A1,A2…,A}是S的一个t块划分。则 (1,A2,A为S的个块的一个有序划分 ◆要说明的是给出一个划分{A1,A2…,A} 可以构造个块的多个有序划分。 例:S={a,b,c,d},A1={a,b},A2={c},A3={d},则 A1,A42,A3}为s的3个块的一个划分,从此划分 中,可得到6个不同的S的3个块的有序划分: ◆(A1,A2A3)2(A1,A3,42)(A2,A1,A3)(A2,A3,A1)(A3, A1A2),(A3,A2,A1)

 1.有序划分  定义一：设 S 是 n 个元素的集合 ， {A1 ,A2 ,…,At } 是 S 的一个 t块划分 。 则 (A1 ,A2 ,…,At )为S的t个块的一个有序划分  要说明的是给出一个划分{A1 ,A2 ,…,At }， 可以构造t个块的多个有序划分。  例 ： S={a,b,c,d}, A1={a,b},A2={c},A3={d}, 则 {A1 ,A2 ,A3 }为S的3个块的一个划分，从此划分 中，可得到6个不同的S的3个块的有序划分：  (A1 ,A2 ,A3 ),(A1 ,A3 ,A2 ),(A2 ,A1 ,A3 ),(A2 ,A3 ,A1 ),(A3 , A1 ,A2 ), (A3 ,A2 ,A1 )

◆定义二:设S是n个元素的集合,且 q1+q2+…+q=n(q为正整数根据q的值 就可构造S的t个块的划分{A1,A2…,A1},使 得A=q1,-称(q1,q2…,q给出了的一种类 型的个块的有序划分记这种类型的不同 有序划分数为P(m;q1,q2…,q ◆那么此值是多少? ◆从n个元素中选取q1个元素组成A的方式数为C(nq1), ◆从剩余的nq1个元素中选取q2个元素组成A2的方式数 为C(n,q2),, ◆由乘法原理得: P(m;q1,q2,…,q1=n!(q1!q2!.q!)

 定 义二 ：设 S是 n个 元素 的集合 ， 且 q1+q2+…+qt=n(qt为正整数),根据qI的值 就可构造S的t个块的划分{A1 ,A2 ,…,At },使 得|Ai |=qi ,称(q1 ,q2 ,…,qt )给出了S的一种类 型的t个块的有序划分,记这种类型的不同 有序划分数为P(n; q1 ,q2 ,…,qt ).  那么此值是多少?  从n个元素中选取q1个元素组成A1的方式数为C(n,q1 ),  从剩余的n-q1个元素中选取q2个元素组成A2的方式数 为C(n,q2 ),…,  由乘法原理得:  P(n; q1 ,q2 ,…,qt )= n!/(q1 !q2 !…qt !)

◆例1:6本不同的书分给甲,乙,丙三人 ◆1)要求甲得1本,乙得2本,丙得3本 ◆2)要求每人各得2本 ◆3)要求1个人得1本,另一人得2本,还有 人得3本 ◆要注意有序划分的类型数目 ◆例2:8本不同的书分给5人,其中2人各得1 本,另3人各得2本,问有多少种分法?

 例1:6本不同的书分给甲,乙,丙三人,  1)要求甲得1本,乙得2本,丙得3本  2)要求每人各得2本  3)要求1个人得1本,另一人得2本,还有一 人得3本  要注意有序划分的类型数目.  例2:8本不同的书分给5人,其中2人各得1 本,另3人各得2本,问有多少种分法?

无序划分 ◆无序划分最典型的是分堆。 般地,无序划分没有通用的公式。但 部分问题可根据实际情况来解决。 ◆例3:集合S中的n个元素平均分成价个块 每块有q个元素,即n=tq求分成个块的 不同分法数。 ◆首先考虑作为有序划分其数目为n!/q 个无序划分对应t个不同的有序划分 ◆分成个块的不同分法数为(1t!)×n!(q!y

 二、无序划分  无序划分最典型的是分堆。  一般地，无序划分没有通用的公式。但 部分问题可根据实际情况来解决。  例3：集合S中的n个元素平均分成t个块， 每块有q个元素，即n=t·q,求分成t个块的 不同分法数。  首先考虑作为有序划分其数目为n!/(q!)t  一个无序划分对应t!个不同的有序划分  分成t个块的不同分法数为(1/t!)×n!/(q!)t