《排列组合与集合的简单教程》由会员分享，可在线阅读，更多相关《排列组合与集合的简单教程（27页珍藏版）》请在金锄头文库上搜索。
1、 集合及其运算,1、集合的运算：并、交、补、差 2、容斥原理,1、集合的运算：并、交、补、差 并： 交： 补：或或 差: -,A,B,A,B,A,A,B,A B,A B,A-B,8. （NOIP9）设全集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 1、（NOIP10）设全集I = a, b, c, d, e, f, g，集合A = a, b, c， B = b, d, e，C = e, f, g，那么集合为（ ）。 A. a, b, c, d B. a, b, d, e C
2、. b, d, e D. b, c, d, e E. d, f, g 2. （NOIP11）设全集I = a, b, c, d, e, f, g, h， 集合BA= a, b, c, d, e, f， C A= c, d, e，AB = a, d，那么集合C B A 为（ ）。 A. c, e B. d, e C. e D. c, d, e E. d, f,2、容斥原理,在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是： 先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这
3、种计数的方法称为容斥原理。,对有限集合S，用 表示S的元素个数,容斥原理的第一形式：设A，B是有限集合，则,容斥原理的第二形式：设A、B、C是有限集合，则,1、（NOIP10）75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。 2、某学校足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队，那么同时只参加两个队的队员有多少？ 、分母是1001的最简分数一共有多少个？,10，9,72
4、0,排列与组合,1.排列的定义:,从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.,排列数公式:,全排列问题： n个不同的元素排成一排，排列方法有：,=n*(n-1)*(n-2)*2*1=n!,2.组合的定义:,从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.,组合数公式:,排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题.,加法原理和乘法原理 从A到C共有多少中走法？,A,B,C,例1 :学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方
5、式？,解 先排学生共有 种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有 种选法.根据乘法原理,共有的不同坐法为 种.,结论1 插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.,例2 : 5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?,解 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法.,结论2 捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法
6、来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.,例3 : 袋中有不同年份生产的5分硬币23个,不同年份生产的1角硬币10个,如果从袋中取出2元钱,有多少种取法?,解 把所有的硬币全部取出来,将得到 0.0523+0.1010=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法.,结论3 剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法.,分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理
7、出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.,例4 学校安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序?,解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有 种.,结论4 对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求.,分析 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决
8、了.并且也避免了问题的复杂性.,例5 某个班级共有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?,解 43人中任抽5人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有1人在内的抽法有 种.,结论5 排异法:有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除.,分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.,圆周排列： 从n个不
9、同的元素中取r个沿一圆周排列，排列的方案：,/r,N个元素的圆周排列：,/n,=（n-1）!,有重复元素的排列问题： 如： n1个a，n2个b，n3个c，排成一排，有多少种排列方法。,重复元素的组合问题： 从n种不同的元素中取r个的元素的组合，允许有重复元素的组合：,典型模型： r个相同的小球，放到n个不同的盒子里，所有的放置方法。,2.（NOIP7）平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？ 2、 （NOIP10）由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（ ）个。 A. 4
10、0320 B. 39600 C. 840 D. 780 E. 60,1 (NOIP8) 在书架上放有编号为1 ，2 ，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n = 3时： 原来位置为：1 2 3 放回去时只能为：3 1 2 或 2 3 1 这两种 问题：求当n = 5时满足以上条件的放法共有多少种？（不用列出每种放法）,错排问题： n个不同元素的错排问题： 如：1，2，3，。，n 的错排问题，i不在第i个位置的排列方法。 分析： 设f(n)为n个不同元素的错排方案。 第一部分：n先不动，把另外的n-1个数错排，方案是：f（n-1），然后n和另外的n-1个每一个交换，共有(n-1)*f(n-1)种方案。 第二部分：n和其他的n-1个之一交换，其余的n-2个错排，共有 （n-1）*f（n-2）种方案。 由加法原理： f(n)=(n-1)*(f(n-1)+f(n-2) f(1)=0;f(2)=1;,44,错排的计算公式：,
