本单元介绍了容斥原理

《本单元介绍了容斥原理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、本单元介绍了容斥原理，以及用来求重复组合数、移位排列和定位排列数的公式。本单元关键词：包含排斥重复组台移位排列定位排列主要公式1.容斥原理当n＝2时当n＝3时2.求重复组合数公式设S＝{nl·a1，n2·a2，…，nk·ak}，则S的r—重复组合数为3.求移位排列数公式4。求定位排列数公式特别，当r＝0时，N(0)＝D(n)，定位排列可视为移位排列的推广。复习思考题1.容斥原理的计算公式你能用文氏图给予解释吗？2.利用容斥原理做计数计算时，直接计算有困难能否采用间接计算法？3.利用容斥原理做计数计算时，有时令遇

2、到求两个或两个以上的整数的最小公倍数，你会求最小公倍数吗？求1000以内能被6整除的个数时，需求的是整数，取整数时能否四舍五入？4.求重复组合数的一般公式在证明过程中应用了什么基本原理？此公式能否用于非重复组合数的计算？5.移位排列又称错排，它是如何定义的？求错排数D(n)的公式是用什么原理取得的？6.移位排列数的性质有哪些？7.定位排列数N(r)的公式是如何取得的？8.移位排列与定位排列的关系是什么？学习指导容斥原理是组合数学中一个重要的原理，它在计数研究中占有重要地位。它研究的是若干有限集合的交、并或差的计

3、数。学习本单元常用的以下方法和技巧是一、注意采用间接计算。例如，计算从1到l000中不能被7整除的个数有多少？这个计算虽然不太复杂，但是若直接计算还是有一定的难度。如果采用间接计算就较简单。先计算从1到l000中能被7整除的个数＝＝142，于是，不能被7整除的个数就是1000—142＝858个。再如，计算{1，2，…，n}的l不在第1个位置上的排列ili2…in(il¹1)的个数。此题若直接计算，就要考虑l不在第1个位置上的排列可以根据(2，3，…，n)中哪个正整k(k＝2，3，…，n)是在第1个位置上，而分成

4、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人同时学以上三种语言，问有多少人这三种语言都没

5、有学。解设Ai(i＝l，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.根据已知条件，我们还可以画上文氏图，从文氏图中直

6、接求解。三、求重复组合数可以代入公式(2。3)，也可以依题意直接求。例试确定重集B＝{3·a，4·b，5·c}的10—组合个数。解：我们要把容斥原理应用到重集C={¥·a，¥·b，¥·c}的所有10—组合的集合S上。令A1表示C中的10—组合多于3个a的集合；A2表示C中的10—组合多于4个b的集合；A3表示C中的10—组合多于5个c的集合。依题意B的10—组合个数等于`A1Ç`A2Ç`A3中的元素个数。利用互斥原理得由重复组合的定义得A1是由C的a至少出现4次的所有10—组合组成。如果从A1这些10—组合中任

7、取一个，并且去掉4个a就剩下C的一个6—组合。反之，如果取C的一个6—组合，并且把4个a加进去，便得到了C的且a至少出现4次的10—组合。于是A1的10—组合个数等于C的6—组合个数。因此同样，用类似的方法可知，A2的10—组合个数等于C的5—组合个数，A3的10—组合个数等于C的4—组合个数。于是A1ÇA2是由C的a至少出现4次，同时b至少出现5次的所有10—组合组成。如果从这个10—组合中任取一个，并且去掉4个a和5个b就剩下C的一个1—组合。反之，如果对C的一个1—组合，加进4个a和5个b，就得到了一个a

8、至少出现4次，并且b至少出现5次的10—组合。于是A1ÇA2的10—组合个数等于C的1—组合个数。因此用类似的方法可求出，A1ÇA3的10—组合个数等于C的0—组合个数，A2ÇA3的10—组合中不存在10—组合个数，这样同样也有＝66-28-21-15+3+1+0-0＝6从另一个角度，我们可以这样考虑：重集(nl·al，n2·a2，…，nk·ak}的r一组合个数，等于方程x1+x2+.