NOIP数学之排列组合课件.ppt

信息学竞赛中的数学知识 ◆ 集合的运算 ◆ 排列与组合 ◆ 集合及其运算 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. {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、容斥原理 　　在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是： 　　先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 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元 只是其中一种的人数 50÷5=10人 没有玩过其中任何一种的人数 75-20-35-10=10人 足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队,减去这2人，则足球队有球衣28件，篮球队有球衣13件，排球队有球衣16件，三队队员总数为48人， 设学足球的为集合A 篮球为集合B 排球为集合C ∵|A∪B∪C|=48 |A|=28 |B|=13 |C|=16 |A∩B∩C|=0 x=|A∩B|+|B∩C|+|C∩A| ∴28+13+16-x=48 X=9人 3 　１００１＝７＊１１＊１３　　在１——１００１这些自然数中，１００１的约数有：　　１、７、１１、１３、７＊１１、７＊１３、１１＊１３、７＊１１＊１３共８个，　　所以，分母是１００１的最简真分数共有：１００１－８＋１＝９９４个。 ◆排列与组合 1.排列的定义: 从n个不同元素中,任取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列. 排列数公式: 全排列问题： n个不同的元素排成一排，排列方法有： =n*(n-1)*(n-2)*…*2*1=n! 2.组合的定义: 从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出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=m1m2m3…mn 种不同的方法 例如，从A城到B城中间必须经过C城，从A城到C城共有3条路线(设为a