本单元介绍了容斥原理.doc

本单元介绍了容斥原理，以及用来求重复组合数、移位排列和定位排列数的公式。本单元关键词：包含 排斥 重复组台 移位排列 定位排列主要公式1. 容斥原理 当n2时 当n3时2. 求重复组合数公式设Snla1，n2a2，nkak，则S的r 重复组合数为3. 求移位排列数公式4。求定位排列数公式 特别，当r0时，N(0)D(n)，定位排列可视为移位排列的推广。复习思考题 1. 容斥原理的计算公式你能用文氏图给予解释吗？ 2. 利用容斥原理做计数计算时，直接计算有困难能否采用间接计算法？ 3. 利用容斥原理做计数计算时，有时令遇到求两个或两个以上的整数的最小公倍数，你会求最小公倍数吗？求1000以内能被6整除的个数时，需求的是整数，取整数时能否四舍五入？ 4. 求重复组合数的一般公式在证明过程中应用了什么基本原理？此公式能否用于非重复组合数的计算？ 5. 移位排列又称错排，它是如何定义的？求错排数D(n)的公式是用什么原理取得的？ 6. 移位排列数的性质有哪些？ 7. 定位排列数N(r)的公式是如何取得的？8. 移位排列与定位排列的关系是什么？学习指导容斥原理是组合数学中一个重要的原理，它在计数研究中占有重要地位。它研究的是若干有限集合的交、并或差的计数。 学习本单元常用的以下方法和技巧是 一、注意采用间接计算。 例如，计算从1到l000中不能被7整除的个数有多少？ 这个计算虽然不太复杂，但是若直接计算还是有一定的难度。如果采用间接计算就较简单。先计算从1到l000中能被7整除的个数142，于是，不能被7整除的个数就是1000142858个。 再如，计算1，2，n 的l不在第1个位置上的排列ili2in(il1)的个数。 此题若直接计算，就要考虑l不在第1个位置上的排列可以根据(2，3，n)中哪个正整k(k2，3，n)是在第1个位置上，而分成n-1个组，分别计算，这当然够麻烦的。但是，如果我们先求l在第1位置上的排列个数，无疑它和(2，3，n)的排列个数(n-1)!一样多。又1，2，n的排列总数是n!。这样就求得了1不在第1个位置上的排列总数为 n! (n-1)! = (n-1)(n-1)! 二、配上文氏图不仅能使计算带来方便，而且便于理解。例如 例1 有170学生，其中120人学英语，80人学法语，60人学西班牙语，50人既学英语也学法语，25人既学英语也学西班牙语，30人同时学法语和西班牙语，有10人同时学以上三种语言，问有多少人这三种语言都没有学。 解 设Ai(il，2，3)分别为学英语、法语和西班牙语人的集合。 利用容斥原理2，可以很方便地求得问题的解， 170-(120+80+60)+(50+25+30)-10 = 5 此类题有多种变换问法。如： 1. 这9个数170，120，80，60，50，25，30，l0，5构成了如上恒等式，若告诉其中任意8个数，就是一个方程，从中可求出未知的一个数。如，给出这三种语言都没有学过的人数为5，问同时学这三种语言的人数是多少？或给出同时学这三种语言人数求学英语的人数等等。 2. 根据已知条件，我们还可以画上文氏图，从文氏图中直接求解。 三、求重复组合数可以代入公式(2。3)，也可以依题意直接求。 例 试确定重集B3a，4b，5c 的10组合个数。解：我们要把容斥原理应用到重集 C = a，b，c 的所有10组合的集合S上。令A1表示C中的10组合多于3个a的集合；A2表示C中的10组合多于4个b的集合；A3表示C中的10组合多于5个c的集合。依题意B的10组合个数等于A1A2A3中的元素个数。利用互斥原理得由重复组合的定义得 A1是由C的a至少出现4次的所有10组合组成。如果从A1这些10组合中任取一个，并且去掉4个a就剩下C的一个6组合。反之，如果取C的一个6组合，并且把4个a加进去，便得到了C的且a至少出现4次的10组合。于是A1的10组合个数等于C的6组合个数。因此同样，用类似的方法可知，A2的10组合个数等于C的5组合个数，A3的10组合个数等于C的4组合个数。于是A1A2是由C的a至少出现4次，同时b至少出现5次的所有10组合组成。如果从这个10组合中任取一个，并且去掉4个a和5个b就剩下C的一个1组合。反之，如果对C的一个1组合，加进4个a和5个b，就得到了一个a至少出现4次，并且b至少出现5次的10组合。于是A1A2的10组合个数等于C的1组合个数。因此用类似的方法可求出，A1A3的10组合个数等于C的0组合个数，A2A3的10组合中不存在10组合个数，这样同样也有66-28-21-15+3+1+0-06 从另一个角度，我们可以这样考虑：重集(nlal，n2a2，nkak的r一组合个数，等于方程 x1+x2+.+x