NOIP初赛知识点-信息学竞赛中的数学知识(2018)

初赛知识复习2018-10信息学竞赛中的数学知识◆集合的运算◆排列与组合◆集合及其运算1、集合的运算：并、交、补、差2、容斥原理1、集合的运算：并、交、补、差并：∪交：∩补：^或～或差:-ABABAABA∪BA∩BAA-B8. （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-B)∪(~C-B)为（）.A.{a,b,c,d}B.{a,b,d,e}C.{b,d,e}D.{b,c,d,e}E.{d,f,g}1245ABC2.（NOIP11）设全集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}2、容斥原理　　在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：　　先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。对有限集合S，用　　表示S的元素个数S容斥原理的第一形式：设A，B是有限集合，则ABABAB容斥原理的第二形式：设A、B、C是有限集合，则ABCABCBCCAABABC1、（NOIP10-2004）75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。55*2+20+x=700/5x=10（玩过一次的）75-55-10=1020人55人20人2、某学校足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有3人同时参加3个队，那么同时只参加两个队的队员有多少？[解析]：因为三个球队球衣总和为30+15+18=63，而队员总数为50，因此有63-50=13件球衣是重复穿的，又根据条件“有3人同时参加3个队”，也就是说，这3个人穿9件衣，即多余6件，13-6=7，因此，还有7人同时只参加两个队。３、分母是1001的最简分数一共有多少个？解析：1001=7*11*13,只要分子不含7、11、13的因数,就是最简分数,这里要求的是最简真分数(否则就有无穷多个答案)；从1到1001中,能被7整除的数有1001/7=143个；能被11整除的数有1001/11=91个；能被13整除的数有1001/13=77个；以上统计中还包含了：能被7*11=77整除的数1001/77=13个；能被7*13=91整除的数1001/91=11个；能被11*13=143整除的数1001/143=7个；以上三个数中又包含了1001,所以含有因数7、11、13的数共有143+91+77-（13+11+7)+1=281个,于是在1001个数中,不含因数7、11、13的数共有1001-281=720个,故所求的最简真分数有720个.◆排列与组合1.排列的定义:从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.)!(!)1()2)(1(mnnmnnnnPmn排列数公式:全排列问题：n个不同的元素排成一排，排列方法有：nnP=n*(n-1)*(n-2)*…*2*1=n!2.组合的定义:从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.组合数公式:排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题.)!(!!!)1()2)(1(mnmnmmnnnnPPCmmmnmn加法原理和乘法原理从A到C共有多少中走法？ABC1+1+2*3=8种例1:学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？解先排学生共有种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有种选法.根据乘法原理,共有的不同坐法为种.88P47P4788PP结论1插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.例2:5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?解因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有种排法,其中女生内部也有种排法,根据乘法原理,共有种不同的排法.33P66P3366PP结论2捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.例3:袋中有不同年份生产的5分硬币23个,不同年份生产的1角硬币10个,如果从袋中取出2元钱,有多少种取法?解把所有的硬币全部取出来,将得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有种取法.110123323CCC结论3剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法.分析此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.例4学校安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序?解不加任何限制条件,整个排法有种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有种.99P9921P结论4对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求.分析对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性.例5某个班级共有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?解43人中任抽5人的方法有种,正副班长,团支部书记都不在内的抽法有种,所以正副班长,团支部书记至少有1人在内的抽法有种.543C540C540543CC结论5排异法:有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除.分析此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.圆周排列：从n个不同的元素中取r个沿一圆周排列，排列的方案：rnP/rN个元素的圆周排列：nnP/n=（n-1）!有重复元素的排列问题：如：n1个a，n2个b，n3个c，排成一排，有多少种排列方法。123123()!!*!*!nnnnnn重复元素的组合问题：从n种不同的元素中取r个的元素的组合，允许有重复元素的组合：1rnrC典型模型：r个相同的小球，放到n个不同的盒子里，所有的放置方法。2.（NOIP7）平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三边形？3、（NOIP10）由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个。A.40320B.39600C.840D.780E.60先求子串中含至少含一个abc的情况数：3a5b2c中扣去一个abc后剩下2a4b1c2a4b1c组成的字符串有（2+4+1）!/（2!*4!*1!）＝105种把abc插入其中,有（2+4+1）+1＝8种插法总计为105*8＝840种但这里面含有两个abc的情况也算在内了,并且每个含两个abc的子串都被多算了一次（可以理解吧）所以要扣去多算的含两个abc的情况数：3a5b2c中扣去2个abc后剩下1a3b把2个abc当作两个元素,与1个a及3个b排列组合有(2+1+3)!/(2!*1!*3!)=60种所以本题答案为840-60＝780种.思路：一共六个元素嘛,题目要求包含子串abc的,从六个里面取出三个固定看做一个元素X,最后就变成了把四个元素：aacX这四个元素来排序,12个先求子串中含至少含一个abc的情况数：3ab2c中扣去一个abc后剩下2a1c2a1c组成的字符串有（2+1）!/2!＝3种把abc插入其中,有（2+1）+1＝4种插法总计为3*4＝12种1．(NOIP8)在书架上放有编号为1，2，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时：原来位置为：123放回去时只能为：312或231这两种问题：求当n=5时满足以上条件的放法共有多少种？（不用列出每种放法）答案为：44递推式：F[N]=(N-1)*(F[N-1]+F[N-2])初始值：f[1]=0；f[2]=1错排问题：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递推、寻找规律问题递推式：f[n]=(n-1)*(f[n-1]+f[n-2])初始值：f[1]=0；f[2]=1答案为：4423in…………(n-1)×f[n-1]××××11递推、寻找规律问题递推式：f[n]=(n-1)*(f[n-1]+f[n-2])初始值：f[1]=0；f[2]=1;答案为：44123in…………1i(n-1)×f[n-2]×××错位重排11111()!(......(1))2!3!4!5!nfnnn错排的计算公式：几类重要的递推关系：一、第二类Stirling数　　　　问题一：放置小球n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种：1)bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S(n-1,m-1)2)bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为m*S(n-1,m)S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n1,m1)边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)问题二：集合划分问题。　　设S是一个包含n个元素的集合，S={b1,b2,b3,…,bn},现需要将S集合划分为m个满足如下条件的集合S1,S2,…Sm。　　　Si≠∮;　　　Si∩Sj=∮;　　　S1∪S2∪…∪Sm=S;(1=I,j=m)则称S1,S2,…,Sm是S的一个划分。编程：输入n和m的值，输出不同的划分方案数。要求：输入数据有一行，第一个数