13容斥原理与母函数

1、13容斥原理与母函数容斥原理与母函数是组合数学的重要内容，他们是在解决组合问题的重要工具.对于数列，我们将形式幂级数称为的普母函数，简称母函数；将形式幂级数称为的指母函数.当形式幂级数在某个区间收敛时，我们把它看成是一般的幂级数，下面介绍容斥原理与母函数解决组合问题的方法.1 基本原理 定理1（容斥原理）设为有限集，则 证 ，我们证明在（1）式两边被计算的次数相同. 事实上，在（1）式左边被计算了1次。在（1）式右边的各个和式中被计算的次数分别为，从而知在（1）式在右边计算的次数为，即在（1）式在右边被计算了一次，由于，在（1）式两边被计算的次数相同，故（1）式成立.推论 设为有限集，则.证

2、， .定理2 设，对于不定方程 （1）满足条件的整数解的个数记为，则的母函数为 （2）证 将式右边展开后比较左右两边的系数，设，且，则，即是不定方程满足条件的一个解；反之，设是不定方程满足条件的一个解，则，因此，式右边展开后的项数是不定方程满足条件的解的个数，所以合并后的系数.推论 设均为，集合的满足条件出现的次数属于的可重根组合的个数为，则的母函数为.证 易知为不定方程满足条件的非负整数解个数，由定理2的知结论成立.定理3 设均为，集合的满足条件出现的次数属于的可充排列个数为，则的指母函数为.定理3的证明较繁琐，有兴趣的读者可查阅组合数学教材.3方法解读运用容斥原理与母函数解题，应对定理1至

3、定理3的本质有足够的认识，特别是定理2与定理3中的，它们是对元素出现的次数的限制条件，解题时应能根据题意准确地写出这些集合.对于容斥原理，当我们将等式左边从某一个和号开始删去它及后面的各个和号后，能得到一些不等式，有时我们要利用这些不等式进行估值，这一点应特别注意.例1 已知三位数的个位不为1，十位数不为2，百位数不为3，且三个数字互不相同，求这样的三位数的个数.分析 易求个位为1的三位数的个数，十位数为2的三位数的个数，百位数为3的三位数的个数，因此可考虑用容斥原理实现转化.解 令，则所求的三位数的个数为，由容斥原理知，,， ，.例2 已知，求满足条件且的整数的个数.分析 ，即，由此不难看出

4、要利用容斥原理实现转化.解 令：，则，.由容斥原理有例3（1994年全国高中联赛试题）将与105互素的正整数从小到大排列成数列，求出这个数列的第1000项.分析 设这个数列的1000项是，由于，所以集合中不能被中任何一个整除的数恰有1000个，这样可用容斥原理建立个满足的方程.解 设这个数列的第1000项为，令，由容斥原理知：= （1）从而.又因为与105互素，所以只能为，检验知.例4（第31届IMO预选题）一次会议有1990位数学家参加，每人至少有1327位合作者，证明可以找到四位数学家，他们中每两人都合作过.分析 要找到满足题设条件的四位数学家，可找出3位合作过的数学家，再证明有一位数学家

5、，它与都合作过，若令与合作过的的数学家的集合为，则,因此只需证明，即证，这可用容斥原理来证.证 设数学家合作过，并设与合作过的的数学家的集合为. ,.设，则中任两人都合作过，设.，.设，则中每两位都合作过.例5 在1978个集合中，每个集合有40个元素，每两个集合都恰好有一个公共元素，求这1978个集合的并集所含元素的个数.分析 题中要求并集的元素的个数，因此可考虑用容斥原理.解 设这1978个集合分别为 ，由容斥原理知： .在集合中，将中的每个元素看成盒子，集合看作球，对于. >49，所以由抽屉原则知至少有50个球进入同一个盒子，即中有一个元素至少属于中的50个集合.不妨设 ,且，下证

6、：对于，必有.事实上，若存在 ，使得 ， 则与的公共元素两两互不相同，从而有，这与已知条件相矛盾.设 则， ， ， ，=77143.例6 用排成一个位数，要求出现偶数次，试求这样的位数的个数.分析 满足条件的位数是的一个有限制条件的可重排列，因而可用指母函数求解.解 设满足条件的位数的个数为，令,，由定理3知的指母函数为=比较.例7 袋中有红，白，黑三种颜色的球各十个，从中抽出十六个，要求三种颜色的球都有，问有多少种不同的取法？分析 用分别表示取出的红，白，黑三种颜色的球数，则，故可用定理2求解.解 设取出的个球的取法个数为，由定理2知的母函数为，比较的系数得.例8（2004年第3届女子奥林匹

7、克试题）一副三色牌共32张，其中红黄蓝每种颜色的牌各十张，编号分别是，另有大小王各一张，编号为0，从这副牌中抽出若干张牌，然后按如下规则计算分值，每张编号为分，若它的分值之和等于，就称这些牌为一个“好”牌组，试求好牌组的个数.分析 用分别表示三张1为好牌组提供的分数，用表示三张2为好牌组提供的分数，用分别表示三张10为好牌组提供的分数，用分别表示大小王为好牌组提供的分数，则有 （1）且 （2）从而知.反之，对于，可依据的值去确定各张牌的取法，从而确定一个好牌组.所以好牌组的个数为的个数，将换成一般的，就可用定理求解。解 用表示分值之和等于的牌组数目，由以上分析及定理2知，数列的母函数为，即.比较式两边的系数，因为，所以式右边的系数等于的展开式中的系数.又因为，所以，所以“好”牌组数为.