noip数学之排列组合

《noip数学之排列组合》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学竞赛中的数学知识◆集合的运算◆排列与组合◆集合及其运算1、集合的运算：并、交、补、差2、容斥原理1、集合的运算：并、交、补、差并：∪交：∩补：^或～或差:-ABABAABA∪BA∩BA-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={

2、e,f,g}，那么集合为（）。A.{a,b,c,d}B.{a,b,d,e}C.{b,d,e}D.{b,c,d,e}E.{d,f,g}2.（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、容斥原理在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把

3、包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。对有限集合S，用　　表示S的元素个数容斥原理的第一形式：设A，B是有限集合，则容斥原理的第二形式：设A、B、C是有限集合，则1、（NOIP10）75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。2、某学校足球

4、队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队，那么同时只参加两个队的队员有多少？３、分母是1001的最简分数一共有多少个？1：只是玩过其中两种的有55-20=35人只是玩过其中一种人所花费用700-20*（5*3）-35*（5*2）=50元只是其中一种的人数50÷5=10人没有玩过其中任何一种的人数75-20-35-10=10人足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队,减去这2人，

5、则足球队有球衣28件，篮球队有球衣13件，排球队有球衣16件，三队队员总数为48人，设学足球的为集合A篮球为集合B排球为集合C∵

6、A∪B∪C

7、=48

8、A

9、=28

10、B

11、=13

12、C

13、=16

14、A∩B∩C

15、=0x=

16、A∩B

17、+

18、B∩C

19、+

20、C∩A

21、∴28+13+16-x=48X=9人3１００１＝７＊１１＊１３　　在１——１００１这些自然数中，１００１的约数有：　　１、７、１１、１３、７＊１１、７＊１３、１１＊１３、７＊１１＊１３共８个，　　所以，分母是１００１的最简真分数共有：１００１－８＋１＝９９４个。

22、◆排列与组合1.排列的定义:从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.排列数公式:全排列问题：n个不同的元素排成一排，排列方法有：=n*(n-1)*(n-2)*…*2*1=n!2.组合的定义:从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.组合数公式:排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题.加法原理：做一件事情，完成它有N类办法，在第一类办法中有M1种不同的方法，在第二类办法中

23、有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=m1m2m3…mn种不同的方法例如，从A城到B城中间必须经过C城，从A城到C城共有3条路线(

24、设为a，b，c)，从C城到B城共有2条路线(设为m，t)，那么，从A城到B城共有3×2=6条路线am，at，bm，bt，cm，ct加法原理和乘法原理从A到C共有多少种走法？ABC共有N=1+3*2+1=8种做题方法与实例例1:学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？解先排学生共有种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有种选法.根据乘法原理,共有的