复旦大学：《离散数学——集合与图论》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没有 一般的求解方法，可利用容斥原理予以 解决