[TOC] # 集合的运算 ## 并、交、补、差 ### 概念 * 并：∪ * 交：∩ * 补：^或～或 * 差: - :-:  ### 例题 1. 设全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，则集合（A ∩ B）∪ ~C 为（      ）。 A） 空集    B） {1}   C） {3，5}   D）{1，5}     **E） {1，3，5}** 2. 设全集I = {a, b, c, d, e, f, g, h}， 集合B ∪ A= {a, b, c, d, e, f}， C ∩ A= {c, d, e}，A ∩ ~B = {a, d}， 那么集合C ∩ B ∩ A 为（ ）。 **A）{c, e} ** B) {d, e} C) {e} D) {c, d, e} E) {d, f} ## 容斥原理 ### 概念 * 在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为**容斥原理**。 * 对有限集合S，用表示S的元素个数。 * 容斥原理的第一形式：设A，B是有限集合，则 :-:  * 容斥原理的第二形式：设A、B、C是有限集合，则 :-:  ### 例题 1. 75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有多少名儿童没有玩过其中任何一种。 > **700/5=140人次 > 140-20*3=80人次（玩2种+玩1种） > 55-20=35人（玩2种） > 80-35*2=10人次（玩1种） > 75-20-35-10=10人（一种都没玩）** 2. 某学校足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队，那么同时只参加两个队的队员有多少？ > ** 分析： > A+B+C-(A与B重合+A与C重合+B与C重合)+A、B、C重合=总数 > 30+15+18-(A与B重合+A与C重合+B与C重合)+2=50 > (A与B重合+A与C重合+B与C重合)=30+15+18+2-50=15人 ** 3. 例题：分母是1001的最简分数一共有多少个？ > **分析： > 1001=7×11×13 > 分子中不能含有质因数7、11、13 > 即1至1001中，不能被7、11、13整除的数有多少个？ > 1001÷7=143 > 1001÷11=91 > 1001÷13=77 > 1001÷[7,11]=13, [7,11]----7和11的最小公倍数 > 1001÷[7,13]=11, ------- > 1001÷[11,13]=7, ----- > 1001÷[7,11,13]=1  > 143+91+77-(13+11+7)+1=281个 > 不能被7，11，13整除的数有 1001-281=720个** # 排列与组合 ## 排列的定义 * 排列的定义：从n个不同元素中,任取m个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。 * 排列数公式:  * 全排列问题：n个不同的元素排成一排，排列方法有：  ## 组合的定义 * 组合的定义：从n个不同元素中，任取m个元素，并成一组，叫做从n个不同元素中取出m个元素的一个组合。 * 组合数公式：  >[danger]排列与组合的区别与联系：与顺序有关的为排列问题，与顺序无关的为组合问题。 # 加法原理和乘法原理 ## 加法原理 做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有`$ m_{n} $`种不同的方法，那么完成这件事共有N=m1+m2+m3+…+mn种不同方法。每一种方法都能够直接达成目标。 ## 乘法原理 做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有`$ m_{n} $`种不同的方法，那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法。 从A到C共有多少中走法？ ## 例题 1. 学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？ > 解：先排学生共有`$ P_{8}^{8} $`种排法，然后把老师插入学生之间的空档，共有7个空档可插，选其中的4个空档,共有`$ P_{7}^{4} $`种选法.根据乘法原理,共有的不同坐法为`$ P_{8}^{8} P_{7}^{4} $`种。 > 插入法：对于某两个元素或者几个元素要求不相邻的问题，可以用插入法。即先排好没有限制条件的元素，然后将有限制条件的元素按要求插入排好元素的空档之中即可。 2. 书架上有21本书，编号从1到21，从其中选4本，其中每两本的编号都不相邻的选法一共有多少种？ > 插空法：假如书架上现已放好了17本书，现要将4本书插入进去且使之任意两本不相邻，即在18个空中插入4本书，列式为：`$ C_{18}^{4} $`=3060。 3. 5个男生3个女生排成一排，3个女生要排在一起,有多少种不同的排法？ > 解：因为女生要排在一起，所以可以将3个女生看成是一个人，与5个男生作全排列,有`$ P_{6}^{6} $`种排法，其中女生内部也有`$ P_{3}^{3} $`种排法，根据乘法原理，共有`$ P_{6}^{6} P_{3}^{3} $`种不同的排法。 > 捆绑法：要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列。 4. 袋中有不同年份生产的5分硬币23个,不同年份生产的1角硬币10个,如果从袋中取出2元钱,有多少种取法？ > 分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题. > 解：把所有的硬币全部取出来,将得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有`$ C_{23}^{3}+C_{21}^{1}+C_{10}^{1} $` > 剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法. 5. 学校安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序? > 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性. > 解：不加任何限制条件,整个排法有`$ P_{9}^{9} $`种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有`$ (1/2)*P_{3}^{3} $`。 > 对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求. 6. 某个班级共有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种? > 分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程. > 解:43人中任抽5人的方法有`$ C_{43}^{5} $`种,正副班长,团支部书记都不在内的抽法有`$ C_{40}^{5} $`种,所以正副班长,团支部书记至少有1人在内的抽法有`$ C_{43}^{5}-C_{40}^{5} $`种. > 排异法:有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除.