组合数学 第六章 容斥原理及应用.ppt

《组合数学 第六章 容斥原理及应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章容斥原理及应用6.2具有重复的组合前面我们已经完成了对n个不同元素的集合的r-组合，其组合数为：并且完成了k类元素并且都有无穷重复数的多重集合的r-组合，其组合数为：1本节我们将证明与容斥原理相联系的公式，并给出一种方法来求对于其重复数无任何限制的多重集的r-组合数。设T是一个多重集，并设T的某些种类型的元素x具有大于r的重复数。此时，通过用r代替x的重复数，T的r-组合的个数等于从T得到多重集的r-组合的个数，因为每个组合的元素最多。如:{3·a,·b,6·c,·d}={3·a,r·b,6·c,r·d}2因为每个r-组合中的元素最多能达到r个，所以对无穷重复数的多重集，实际上

2、只需要有限重复数r就够了。可以总结为：无穷重复数的多重集{·a1,·a2,…..,·ak}总能化为有限重复数的多重集{n1·a1,n2·a2,…..,nk·ak},对于求r-组合的个数，可以确定两个“极端”的情况：1）n1=n2=…..=nk=1，T是一个普通集合。2）n1=n2=…..=nk=r，T是重复数足够的集合。3我们将用容斥原理来解释如何得到其他的解。下面虽然只是一个例子，但能够很清楚地得到解法，并且推广到一般情况下：例：确定多重集T={3·a,4·b,5·c}的10-组合的数。解：在很久前我们遇到过类似的题，见书P43;当时我们用穷举法排出来满足条件的所有组合。现在我们

3、将容斥原理应用到多重集：4T*={·a,·b,·c}的所有10-组合的集合S上令P1表示T*的10-组合具有多于3个a的性质；P2表示T*的10-组合具有多于4个b的性质；P3表示T*的10-组合具有多于5个c的性质；此时题意要求的多重集T的10-组合的数就是T*中不具备性质P1，P2，P3的10-组合的数。同样5令Ai是由T*中满足性质Pi（i=1,2,3）的那些10-组合够成。的元素数量即是我们需要的，由容斥原理：6其中集合A1是由a多于3个的T*的所有10-组合组成；即构成A1中每个10-组合都至少有4个a，如果任意取A1中的一个10-组合并且去掉其中的4个a，剩下的就是T*

4、的6-组合。反之，如果拿出T*的6-组合再加入4个a就得到T*的10-组合，而且其中至少有4个a，也就是说T*的10-组合个数等于T*的6-组合个数，或者说A1中的4个元素已经确定，余下再作三类元素7选择6个的6-组合，故：同理，集合A2是由b多于4个的T*的所有10-组合组成；A2中T*的10-组合个数等于T*的5-组合个数。8集合A1∩A2是至少有4个a并且至少有5个b的T*的所有10-组合组成，实际上这十个元素已经固定了九个，另外一个可以选择a,b,c中任意一个，共有3种，用前面同样的分析，A1∩A2中的一个10-组合去掉其中的4个a和5个b，剩下的就是T*的1-组合。反之，如果拿

5、出T*的1-组合再加入4个a和5个b就得到T*的10-组合，而且其中至少有4个a和95个b，也就是说T*的10-组合个数等于T*的1-组合个数，用多重集的r-组合数公式求法：A2∩A3中总共才有9个元素，没有10-组合，所以：A1∩A2=0；和A1∩A2∩A3=0;10只有六个10-组合，我们可以全部列出来：{3·a,4·b,3·c}{3·a,3·b,4·c}{3·a,2·b,5·c}{2·a,4·b,4·c}{2·a,3·b,5·c}{1·a,4·b,5·c}由此例题我们可以看出，当重复数之和靠近r-组合的r时，我们可以穷举出所有的r-组合，11但在这两个数差距大时，我们最多求

6、出r-组合的个数。我们曾经指出，r-组合与方程的整数解之间的关系：多重集{n1·a1,n2·a2,…..,nk·ak}的r-组合的个数等于方程：x1+x2+…..+xk=r的整数解的个数(P44定理3.5.1)。这些解满足：0≤xi≤ni(i=1,2,…..k)这些解的个数可以用上面的方法来求得。12例：满足1≤x1≤5,－2≤x2≤4,0≤x3≤5,3≤x4≤9的方程x1＋x2＋x3＋x4＝18的整数解的个数有多少？[分析]这一问题与我们上述一般情况的差别在于解所满足的条件不是0≤xi≤ni的形式。因此，需进行相应的变量变换：令y1＝x1-1,y2＝x2+2,y3=x3,y4=x4-3

7、13使得原方程变为y1+y2+y3+y4=16而原条件变为0≤y1≤4,0≤y2≤6,0≤y3≤5,0≤y4≤6对于方程y1+y2+y3+y4=16若其非负整数解集是S，则以下的问题就是根据容斥原理的具体计算了。14令P1为性质y1≥5，P2为性质y2≥7，P3为性质y3≥6，P4为性质y4≥7。令Ai为满足性质Pi的解的集合，题意是求集合：的大小。其中集合A1为满足性质y1≥5的解组成，再作一次变量代换：z1=y1–5,z2=y2