信息学竞赛中的数学知识信息学竞赛中的数学知识 集合的运算 排列与组合 集合及其运算1 1、集合的运算：并、交、补、差、集合的运算：并、交、补、差 2 2、容斥原理、容斥原理1 1、集合的运算：并、交、补、差、集合的运算：并、交、补、差并：并：交：交：补：补： 或或或或差差: -: -A AB BA AB BA AA AB BA BA BA BA BA-BA-B8.8. （NOIP9NOIP9）设全集）设全集E=1E=1，2 2，3 3，4 4，55，集合，集合A=1A=1，44，B=1B=1，2 2，55，C=2C=2，44，则集合（，则集合（A BA B）C C 为（为（ ）。）。A A） 空集空集 B B） 11C C） 33，55D D）11，55 E E） 11，3 3，551 1、（、（NOIP10NOIP10）设全集）设全集I = a, b, c, d, e, f, gI = a, b, c, d, e, f, g，集合，集合A = a, b, cA = a, b, c， B = b, d, eB = b, d, e，C = e, f, gC = e, f, g，那么集合为（，那么集合为（ ）。）。 A. a, b, c, d B. a, b, d, e A. a, b, c, d B. a, b, d, e C. b, d, e D. b, c, d, e E. d, f, g C. b, d, e D. b, c, d, e E. d, f, g2. 2. （NOIP11NOIP11）设全集）设全集I = a, b, c, d, e, f, g, hI = a, b, c, d, e, f, g, h， 集合集合BABA = a, b, c, d, e, f= a, b, c, d, e, f， C AC A = c, d, e= c, d, e，AB = a, dAB = a, d，那么集合，那么集合C B A C B A 为（为（ ）。）。 A. c, e B. d, e C. e D. c, d, e E. d, fA. c, e B. d, e C. e D. c, d, e E. d, f2 2、容斥原理、容斥原理在计数时，为了使重叠部分不被重复计算，人们研在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为数的方法称为容斥原理容斥原理。对有限集合对有限集合S S，用表示，用表示S S的元素个数的元素个数 容斥原理的第一形式：容斥原理的第一形式：设设A A，B B是有限集合，则是有限集合，则容斥原理的第二形式：设容斥原理的第二形式：设A A、B B、C C是有限集合，则是有限集合，则 1、（NOIP10）75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。2、某学校足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队，那么同时只参加两个队的队员有多少？ 、分母是1001的最简分数一共有多少个？1：只是玩过其中两种的有只是玩过其中两种的有55-20=35人人只是玩过其中一种人所花费用只是玩过其中一种人所花费用 700-20*（5*3）-35*（5*2）=50元元只是其中一种的人数只是其中一种的人数 505=10人人没有玩过其中任何一种的人数没有玩过其中任何一种的人数 75-20-35-10=10人人足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队,减去这2人，则足球队有球衣28件，篮球队有球衣13件，排球队有球衣16件，三队队员总数为48人，设学足球的为集合A 篮球为集合B 排球为集合C |ABC|=48 |A|=28 |B|=13 |C|=16 |ABC|=0 x=|AB|+|BC|+|CA| 28+13+16-x=48X=9人人 3在这些自然数中，的约数有：、共个，所以，分母是的最简真分数共有：个。排列与组合排列与组合1.1.排列的定义排列的定义: :从从n n个不同元素中个不同元素中, ,任取任取m m个元素个元素, ,按照一定的顺序排成一按照一定的顺序排成一列列, ,叫做从叫做从n n个不同元素中取出个不同元素中取出m m个元素的一个排列个元素的一个排列. .排列数公式排列数公式: :全排列问题：全排列问题： n n个不同的元素排成一排，排列方法有：个不同的元素排成一排，排列方法有：=n*(n-1)*(n-2)*=n*(n-1)*(n-2)*2*1=n!*2*1=n!2.2.组合的定义组合的定义: :从从n n个不同元素中个不同元素中, ,任取任取m m个元素个元素, ,并成一组并成一组, ,叫做从叫做从n n个个不同元素中取出不同元素中取出m m个元素的一个组合个元素的一个组合. .组合数公式组合数公式: :排列与组合的区别与联系排列与组合的区别与联系: :与顺序有关的为排列问题与顺序有关的为排列问题, ,与顺序与顺序无关的为组合问题无关的为组合问题. . 加法原理：加法原理：做一件事情，完成它有做一件事情，完成它有N类办法，在第一类办法中有类办法，在第一类办法中有M1种不同的方法，在第二类办法中有种不同的方法，在第二类办法中有M2种不同的方种不同的方法，法，在第，在第N类办法中有类办法中有M(N)种不同的方法，那种不同的方法，那么完成这件事情共有么完成这件事情共有M1+M2+M(N)种不同的方法。种不同的方法。 比如说：从北京到上海有比如说：从北京到上海有3种方法可以直接到达上海，种方法可以直接到达上海，1：火车：火车3个班次个班次 2：飞机：飞机2个班次个班次 3：轮船：轮船4个班次个班次，那么从北京那么从北京-上海的方法上海的方法N=3+2+4=9种种 乘法原理：乘法原理：做一件事，完成它需要分成做一件事，完成它需要分成n个步骤，做第一个步骤，做第一 步有步有m1种不同的方法，做第二步有种不同的方法，做第二步有m2不同的方法，不同的方法，做，做第第n步有步有mn不同的方法不同的方法.那么完成这件事共有那么完成这件事共有 N=m1m2m3mn 种不同的方法种不同的方法例如，从例如，从A城到城到B城中间必须经过城中间必须经过C城，从城，从A城到城到C城共城共有有3条路线条路线(设为设为a，b，c)，从，从C城到城到B城共有城共有2条路线条路线(设为设为m，t)，那么，从，那么，从A城到城到B城共有城共有32=6条路线条路线am，at，bm，bt，cm，ct加法原理和乘法原理加法原理和乘法原理从从A到到C共有多少共有多少种种走法？走法？ABC共有共有N=1+3*2+1=8种种做题方法与实例做题方法与实例例例1 1 :学校师生合影，共学校师生合影，共8 8个学生，个学生，4 4个老师，要个老师，要求老师在学生中间，且老师互不相邻，共有多求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？少种不同的合影方式？解解 先排学生共有先排学生共有 种排法种排法, ,然后把老师插入学生之然后把老师插入学生之间的空档，共有间的空档，共有7 7个空档可插个空档可插, ,选其中的选其中的4 4个空档个空档, ,共有共有 种选法种选法. .根据乘法原理根据乘法原理, ,共有的不同坐法为共有的不同坐法为 种种. .结论结论1 1 插入法插入法: :对于某两个元素或者几个元素要求不对于某两个元素或者几个元素要求不相邻的问题相邻的问题, ,可以用插入法可以用插入法. .即先排好没有限制条件的即先排好没有限制条件的元素元素, ,然后将有限制条件的元素按要求插入排好元素然后将有限制条件的元素按要求插入排好元素的空档之中即可的空档之中即可. .例例2 : 2 : 5 5个男生个男生3 3个女生排成一排个女生排成一排,3,3个女生要排在一起个女生要排在一起, ,有多少种不同的排法有多少种不同的排法? ? 解解 因为女生要排在一起因为女生要排在一起, ,所以可以将所以可以将3 3个女生看成是个女生看成是一个人一个人, ,与与5 5个男生作全排列个男生作全排列, ,有有 种排法种排法, ,其中女生内其中女生内部也有部也有 种排法种排法, ,根据乘法原理根据乘法原理, ,共有共有 种不同的排种不同的排法法. .结论结论2 2 捆绑法捆绑法: :要求某几个元素必须排在一起的问题要求某几个元素必须排在一起的问题, ,可以用捆绑法来解决问题可以用捆绑法来解决问题. .即将需要相邻的元素合并即将需要相邻的元素合并为一个元素为一个元素, ,再与其它元素一起作排列再与其它元素一起作排列, ,同时要注意合同时要注意合并元素内部也可以作排列并元素内部也可以作排列. .例例3 3 : : 袋中有不同年份生产的袋中有不同年份生产的5 5分硬币分硬币2323个个, ,不同年份生产的不同年份生产的1 1角硬币角硬币1010个个, ,如果从袋中取如果从袋中取出出2 2元钱元钱, ,有多少种取法有多少种取法? ?解解 把所有的硬币全部取出来把所有的硬币全部取出来, ,将得到将得到 0.0523+0.1010=2.150.0523+0.1010=2.15元元, ,所以比所以比2 2元多元多0.150.15元元, ,所所以剩下以剩下0.150.15元即剩下元即剩下3 3个个5 5分或分或1 1个个5 5分与分与1 1个个1 1角角, ,所以所以共有共有 种取法种取法. .结论结论3 3 剩余法剩余法: :在组合问题中在组合问题中, ,有多少取法有多少取法, ,就有多少就有多少种剩法种剩法, ,他们是一一对应的他们是一一对应的, ,因此因此, ,当求取法困难时当求取法困难时, ,可可转化为求剩法转化为求剩法. .分析分析 此题是一个组合问题此题是一个组合问题, ,若是直接考虑取钱的问题若是直接考虑取钱的问题的话的话, ,情况比较多情况比较多, ,也显得比较凌乱也显得比较凌乱, ,难以理出头绪来难以理出头绪来. .但是如果根据组合数性质考虑剩余问题的话但是如果根据组合数性质考虑剩余问题的话, ,就会很就会很容易解决问题容易解决问题. .例例4 4 学校安排考试科目学校安排考试科目9 9门门, ,语文要在数学之前考语文要在数学之前考, ,有有多少种不同的安排顺序多少种不同的安排顺序? ?解解 不加任何限制条件不加任何限制条件, ,整个排法有整个排法有 种种,“,“语文安排语文安排在数学之前考在数学之前考”, ,与与“数学安排在语文之前考数学安排在语文之前考”的排法的排法是相等的是相等的, ,所以语文安排在数学之前考的排法共有所以语文安排在数学之前考的排法共有 种种. .结论结论4 4 对等法对等法: :在有些题目中在有些题目中, ,它的限制条件的肯定与它的限制条件的肯定与否定是对等的否定是对等的, ,各占全体的二分之一各占全体的二分之一. .在求解中只要求在求解中只要求出全体出全体, ,就可以得到所求就可以得到所求. .分析分析 对于任何一个排列问题对于任何一个排列问题, ,就其中的两个元素来讲的就其中的两个元素来讲的话话, ,他们的排列顺序只有两种情况他们的排列顺序只有两种情况, ,并且在整个排列中并且在整个排列中, ,他们出现的机会是均等的他们出现的机会是均等的, ,因此要求其中的某一种情况因此要求其中的某一种情况, ,能够得到全体能够得到全体, ,那么问题就可以解决了那么问题就可以解决了. .并且也避免了并且也避免了问题的复杂性问题的复杂性. .例例5 5 某个班级共有某个班级共有4343位同学位同学, ,从中任抽从中任抽5 5人人, ,正、副班正、副班长、团支部书记至少有一人在内的抽法有多少种长、团支部书记至少有一人在内的抽法有多少种? ?解解 4343人中任抽人中任抽5 5人的方法有人的方法有 种种, ,正副班长正副班长, ,团支部团支部书记都不在内的抽法有书记都不在内的抽法有 种种, ,所以正副班长所以正副班长, ,团支部书团支部书记至少有记至少有1 1人在内的抽法有人在内的抽法有 种种. .结论结论5 5 排异法排异法: :有些问题有些问题, ,正面直接考虑比较复杂正面直接考虑比较复杂, ,而它而它的反面往往比较简捷的反面往往比较简捷, ,可以先求出它的反面可以先求出它的反面, ,再从整体中再从整体中排除排除. .分析分析 此题若是直接去考虑的话此题若是直接去考虑的话, ,就要将问题分成好几就要将问题分成好几种情况种情况, ,这样解题的话这样解题的话, ,容易造成各种情况遗漏或者重容易造成各种情况遗漏或者重复的情况复的情况. .而如果从此问题相反的方面去考虑的话而如果从此问题相反的方面去考虑的话, ,不不但容易理解但容易理解, ,而且在计算中也是非常的简便而且在计算中也是非常的简便. .这样就可这样就可以简化计算过程以简化计算过程. .圆周排列：圆周排列： 从从n n个不同的元素中取个不同的元素中取r r个沿一圆周排列，排列的方案：个沿一圆周排列，排列的方案：/rN N个元素的圆周排列：个元素的圆周排列：/n= =（n-1n-1）! !有重复元素的排列问题：有重复元素的排列问题：如：如：n n1 1个个a a，n n2 2个个b b，n n3 3个个c c，排成一排，有多少种排列方法。，排成一排，有多少种排列方法。重复元素的组合问题：重复元素的组合问题： 从从n n种不同的元素中取种不同的元素中取r r个的元素的组合，允个的元素的组合，允许有重复元素的组合：许有重复元素的组合：典型模型：典型模型： r r个相同的小球，放到个相同的小球，放到n n个不同的盒子里，所有个不同的盒子里，所有的放置方法。的放置方法。1.1.（NOIP7NOIP7）平面上有三条平行直线，每条直线上分别有）平面上有三条平行直线，每条直线上分别有5 5，6,76,7个点，且不同直线上三个点都不在同一条直线上。个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？问用这些点为顶点，能组成多少个不同四边形？2 2、 （NOIP10NOIP10）由）由3 3个个a a，5 5个个b b和和2 2个个c c构成的所有字符串中，构成的所有字符串中，包含子串包含子串“abcabc”的共有（的共有（ ）个。）个。 A. 40320 B. 39600 C. 840 D. 780 E. 60A. 40320 B. 39600 C. 840 D. 780 E. 601分两种情况分两种情况 (1)4(1)4个点在两条直线上个点在两条直线上 A A上上2 2个点和个点和B B上上2 2个点个点 有有C(5,2)*C(6,2)=10*15=150 C(5,2)*C(6,2)=10*15=150 在在ACAC上有上有C(5,2)*C(7,2)=10*21=210 C(5,2)*C(7,2)=10*21=210 在在BCBC上有上有C(6,2)*C(7,2)=15*21=315 C(6,2)*C(7,2)=15*21=315 (2)(2)在一直线上有在一直线上有2 2点，令二点分别在另两条直线上点，令二点分别在另两条直线上 则若则若A A上有上有2 2点，是点，是C(5,2)C(5,2)，BCBC上各一点，分别有上各一点，分别有6 6种和种和7 7种可能，种可能，是是C(5,2)*6*7=420 C(5,2)*6*7=420 同理若同理若B B上上2 2点是点是C(6,2)*5*7=525 C(6,2)*5*7=525 若若C C上上2 2点则点则C(7,2)*5*6=630 C(7,2)*5*6=630 所以一共所以一共150+210+315+420+525+630=2250 150+210+315+420+525+630=2250 2一共一共 是是1010个字母个字母当当abcabc在第一位时在第一位时, ,后面一共有后面一共有105105种排列种排列 (7!/(2!*4!)=105)(7!/(2!*4!)=105) 当当abcabc在第二位时在第二位时, ,也是也是105105种种 . . 当当abcabc在第八位时在第八位时, ,也是也是105. 105*8=840105. 105*8=840种种 里面有重复的里面有重复的, ,要减去要减去, ,就是减去有就是减去有2 2个字字串个字字串abcabc的的. . 一共一共6060种种 (6!/(2!*3!)=60) (6!/(2!*3!)=60) 所以所以840-60=780840-60=780种种