9512.net
甜梦文库
当前位置:首页 >> 数学 >>

NOIP数学之排列组合



信息学竞赛中的数学知识 ◆ 集合的运算 ◆ 排列与组合

◆ 集合及其运算
1、集合的运算:并、交、补、差 集合的运算: 2、容斥原理

1、集合的运算:并、交、补、差 集合的运算: 并:∪ 交:∩ 补:^或~或 差: A B A
A ∩ B

B

A

A

B A-B

A ∪ B

A

NOIP9)设全集E={1 E={1, 5},集合A={1 4},B={1, A={1, 5},C={2, 8. (NOIP9)设全集E={1,2,3,4,5},集合A={1,4},B={1,2,5},C={2, 4},则集合(A ∩B)∪~C 为( 4},则集合( ∩B) )。 {3, {1, {1, A) 空集 B) {1} C) {3,5} D){1,5} E) {1,3,5} g},集合A c}, 1、(NOIP10)设全集I = {a, b, c, d, e, f, g},集合A = {a, b, c}, 、(NOIP10)设全集I NOIP10 e}, g},那么集合为( B = {b, d, e},C = {e, f, g},那么集合为( )。 A. {a, b, c, d} B. {a, b, d, e} D. {b, c, d, e} C. {b, d, e} E. {d, f, g} NOIP11)设全集I h}, 2. (NOIP11)设全集I = {a, b, c, d, e, f, g, h}, 集合B∪A B∪A? f}, 集合B∪A= {a, b, c, d, e, f}, A? e}, d},那么集合C∩ 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,用 S 表示S的元素个数

容斥原理的第一形式: 是有限集合, 容斥原理的第一形式:设A,B是有限集合,则

A∪ B = A + B ? A∩ B
容斥原理的第二形式:设A、B、C是有限集合,则 容斥原理的第二形式: 是有限集合,

A∪ B ∪C = A + B + C ? B ∩C ? C ∩ A ? A∩ B + A∩ B ∩C

? 1、(NOIP10)75名儿童到游乐场去玩。他们可以骑

旋转木马,坐滑行铁道,乘宇宙飞船。已知其中20人 这三种东西都玩过,55人至少玩过其中的两种。若每 样乘坐一次的费用是5元,游乐场总共收入700,可知 有 名儿童没有玩过其中任何一种。
?2、某学校足球队有球衣30件,篮球队有球衣15件,

排球队有球衣18件,三队队员总数为50人,其中有2人 同时参加3个队,那么同时只参加两个队的队员有多少?
?3、分母是1001的最简分数一共有多少个?

10,9

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

1001=7*11*13 在1——1001这些自然数中,1001 的约数有: 1、7、11、13、7*11、7*13、 11*13、7*11*13共8个, 所以,分母是1001的最简真分数共有: 1001-8+1=994个。

◆排列与组合

1.排列的定义: 1.排列的定义: 排列的定义 从n个不同元素中,任取m个元素,按照一定的顺序排成一 个不同元素中,任取m个元素, 叫做从n个不同元素中取出m个元素的一个排列. 列,叫做从n个不同元素中取出m个元素的一个排列. 排列数公式: 排列数公式:

全排列问题: 全排列问题: n个不同的元素排成一排,排列方法有: 个不同的元素排成一排,排列方法有:

P

n =n*(n-1)*(n=n*(n-1)*(n-2)*…*2*1=n! n

2.组合的定义: 2.组合的定义: 组合的定义 从n个不同元素中,任取m个元素,并成一组,叫做从n个 个不同元素中,任取m个元素,并成一组,叫做从n 不同元素中取出m个元素的一个组合. 不同元素中取出m个元素的一个组合. 组合数公式: 组合数公式:
C =
m n

Pn n ( n ? 1 )( n ? 2 ) ? ( n ? m + 1 ) = = m m! Pm
m

n! m ! ( n ? m )!

排列与组合的区别与联系:与顺序有关的为排列问题, 排列与组合的区别与联系:与顺序有关的为排列问题,与顺序 无关的为组合问题. 无关的为组合问题.

加法原理: 加法原理: 做一件事情,完成它有N类办法 类办法, 做一件事情,完成它有 类办法,在第一类办法中有 M1种不同的方法,在第二类办法中有 种不同的方 种不同的方法, 种不同的方法 在第二类办法中有M2种不同的方 类办法中有M(N)种不同的方法,那 种不同的方法, 法,……,在第 类办法中有 ,在第N类办法中有 种不同的方法 么完成这件事情共有M1+M2+……+M(N)种不同的方法。 么完成这件事情共有 种不同的方法。 种不同的方法 比如说:从北京到上海有3种方法可以直接到达上海 种方法可以直接到达上海, 比如说:从北京到上海有 种方法可以直接到达上海, 1:火车3个班次 1:火车3个班次 2:飞机 个班次 :飞机2个班次 3:轮船 个班次, 个班次, :轮船4个班次 那么从北京-上海的方法 上海的方法N=3+2+4=9种 那么从北京 上海的方法 种

乘法原理: 乘法原理: 做一件事,完成它需要分成n个步骤 个步骤, 步有m1 做一件事,完成它需要分成 个步骤,做第一 步有 种不同的方法,做第二步有m2不同的方法 不同的方法, , 种不同的方法,做第二步有 不同的方法,……,做 步有mn不同的方法 那么完成这件事共有 不同的方法.那么完成这件事共有 第n步有 步有 不同的方法 N=m1m2m3…mn 种不同的方法 例如, 城到B城中间必须经过 城到C城共 例如,从A城到 城中间必须经过 城,从A城到 城共 城到 城中间必须经过C城 城到 条路线(设为 城到B城共有 有3条路线 设为 ,b,c),从C城到 城共有 条路线 条路线 设为a, , , 城到 城共有2条路线 (设为 ,t),那么,从A城到 城共有 ×2=6条路线 设为m, ,那么, 城到B城共有 设为 城到 城共有3× 条路线 am,at,bm,bt,cm,ct , , , , ,

加法原理和乘法原理 共有多少种走法? 从A到C共有多少种走法? 到 共有多少种走法

A

B

C

共有N=1+3*2+1=8种 种 共有

做题方法与实例

学校师生合影, 个学生, 个老师, 例1 :学校师生合影,共8个学生,4个老师,要 求老师在学生中间,且老师互不相邻, 求老师在学生中间,且老师互不相邻,共有多 少种不同的合影方式? 少种不同的合影方式?

解 之间的空档,共有7个空档可插,选其中的4个空档, 之间的空档,共有7个空档可插,选其中的4个空档,共 种选法.根据乘法原理, 有 P 7 4 种选法.根据乘法原理,共有的不同坐法为 P88 P74 种. 结论1 插入法: 结论1 插入法:对于某两个元素或者几个元素要求 不相邻的问题,可以用插入法. 不相邻的问题,可以用插入法.即先排好没有限制条 件的元素, 件的元素,然后将有限制条件的元素按要求插入排好 元素的空档之中即可. 元素的空档之中即可.

P88 种排法,然后把老师插入学生 种排法, 先排学生共有

个男生3个女生排成一排,3个女生要排在一起, ,3个女生要排在一起 例2 : 5个男生3个女生排成一排,3个女生要排在一起, 有多少种不同的排法? 有多少种不同的排法?

因为女生要排在一起,所以可以将3 解 因为女生要排在一起,所以可以将3个女生看成是 一个人, 个男生作全排列, 种排法, 一个人,与5个男生作全排列,有 P66 种排法,其中女生内 种排法,根据乘法原理, 部也有P33 种排法,根据乘法原理,共有P66 P33 种不同的排 法. 结论2 捆绑法:要求某几个元素必须排在一起的问题, 结论2 捆绑法:要求某几个元素必须排在一起的问题, 可以用捆绑法来解决问题. 可以用捆绑法来解决问题.即将需要相邻的元素合并 为一个元素,再与其它元素一起作排列, 为一个元素,再与其它元素一起作排列,同时要注意合 并元素内部也可以作排列. 并元素内部也可以作排列.

袋中有不同年份生产的5分硬币23 23个 例3 : 袋中有不同年份生产的5分硬币23个, 不同年份生产的1角硬币10个,如果从袋中取 角硬币10个 10 元钱,有多少种取法? 出2元钱,有多少种取法?

此题是一个组合问题, 分析 此题是一个组合问题,若是直接考虑取钱的问 题的话,情况比较多,也显得比较凌乱, 题的话,情况比较多,也显得比较凌乱,难以理出头绪 但是如果根据组合数性质考虑剩余问题的话, 来.但是如果根据组合数性质考虑剩余问题的话,就 会很容易解决问题. 会很容易解决问题. 把所有的硬币全部取出来, 解 把所有的硬币全部取出来,将得到 0.05×23+0.10×10=2.15元 所以比2元多0.15 0.15元 0.05×23+0.10×10=2.15元,所以比2元多0.15元,所 以剩下0.15元即剩下3 0.15元即剩下 分或1 分与1 以剩下0.15元即剩下3个5分或1个5分与1个1角,所以 3 1 1 C23 + C23 ? C10 种取法. 种取法. 共有 结论3 剩余法:在组合问题中,有多少取法, 结论3 剩余法:在组合问题中,有多少取法,就有多少 种剩法,他们是一一对应的,因此,当求取法困难时, 种剩法,他们是一一对应的,因此,当求取法困难时,可 转化为求剩法. 转化为求剩法.

学校安排考试科目9 语文要在数学之前考, 例4 学校安排考试科目9门,语文要在数学之前考,有 多少种不同的安排顺序? 多少种不同的安排顺序?

对于任何一个排列问题, 分析 对于任何一个排列问题,就其中的两个元素来讲 的话,他们的排列顺序只有两种情况, 的话,他们的排列顺序只有两种情况,并且在整个排列 他们出现的机会是均等的, 中,他们出现的机会是均等的,因此要求其中的某一种 情况,能够得到全体,那么问题就可以解决了. 情况,能够得到全体,那么问题就可以解决了.并且也避 免了问题的复杂性. 免了问题的复杂性. P99 种,“语文安排 不加任何限制条件, 解 不加任何限制条件,整个排法有 在数学之前考” 数学安排在语文之前考”的排法 在数学之前考”,与“数学安排在语文之前考”1 P99 是相等的, 是相等的,所以语文安排在数学之前考的排法共有 2 种. 结论4 对等法:在有些题目中, 结论4 对等法:在有些题目中,它的限制条件的肯定与 否定是对等的,各占全体的二分之一. 否定是对等的,各占全体的二分之一.在求解中只要求 出全体,就可以得到所求. 出全体,就可以得到所求.

某个班级共有43位同学,从中任抽5 43位同学 例5 某个班级共有43位同学,从中任抽5人,正、副 班长、团支部书记至少有一人在内的抽法有多少种? 班长、团支部书记至少有一人在内的抽法有多少种?

此题若是直接去考虑的话, 分析 此题若是直接去考虑的话,就要将问题分成好几 种情况,这样解题的话, 种情况,这样解题的话,容易造成各种情况遗漏或者重 复的情况.而如果从此问题相反的方面去考虑的话, 复的情况.而如果从此问题相反的方面去考虑的话,不 但容易理解,而且在计算中也是非常的简便. 但容易理解,而且在计算中也是非常的简便.这样就可 以简化计算过程. 以简化计算过程. 5 C43 种,正副班长,团支部 43人中任抽 人中任抽5 正副班长, 解 43人中任抽5人的方法有 5 C40 种,所以正副班长,团支部书 书记都不在内的抽法有 所以正副班长, 5 5 C 43 ? C 40 种. 记至少有1 记至少有1人在内的抽法有 结论5 排异法:有些问题,正面直接考虑比较复杂, 结论5 排异法:有些问题,正面直接考虑比较复杂,而它 的反面往往比较简捷,可以先求出它的反面, 的反面往往比较简捷,可以先求出它的反面,再从整体中 排除. 排除.

圆周排列: 圆周排列:
从n个不同的元素中取r个沿一圆周排列,排列的方案: 个不同的元素中取r个沿一圆周排列,排列的方案:

P /r
N个元素的圆周排列: 个元素的圆周排列:

r n

P /n =(n-1)!

n n

有重复元素的排列问题: 有重复元素的排列问题:
如: 排成一排,有多少种排列方法。 n1个a,n2个b,n3个c,排成一排,有多少种排列方法。

(n1 + n2 + n3 )! n1 !* n2 !* n3 !

重复元素的组合问题: 重复元素的组合问题:
从n种不同的元素中取r个的元素的组合,允 种不同的元素中取r个的元素的组合, 许有重复元素的组合: 许有重复元素的组合:

C
典型模型: 典型模型:

r n + r ?1 ?1

r个相同的小球,放到n个不同的盒子里,所有 个相同的小球,放到n个不同的盒子里, 的放置方法。 的放置方法。

1.(NOIP7)平面上有三条平行直线,每条直线上分别有7 1.(NOIP7)平面上有三条平行直线,每条直线上分别有7, 个点,且不同直线上三个点都不在同一条直线上。 5,6个点,且不同直线上三个点都不在同一条直线上。 问用这些点为顶点,能组成多少个不同四边形? 问用这些点为顶点,能组成多少个不同四边形? NOIP10) 构成的所有字符串中, 2、 (NOIP10)由3个a,5个b和2个c构成的所有字符串中, 包含子串“abc”的共有( 包含子串“abc”的共有( )个。 A. 40320 B. 39600 C. 840 D. 780 E. 60

1

分两种情况 (1)4个点在两条直线上 个点和B (1)4个点在两条直线上 A上2个点和B上2个点 有 AC上有 C(5,2)*C(6,2)=10*15=150 在AC上有 BC上有 C(5,2)*C(7,2)=10*21=210 在BC上有 C(6,2)*C(7,2)=15*21=315 (2)在一直线上有2 则若A (2)在一直线上有2点,令二点分别在另两条直线上 则若A 在一直线上有 上有2 C(5,2),BC上各一点 分别有6种和7种可能, 上各一点, 上有2点,是C(5,2),BC上各一点,分别有6种和7种可能, 同理若B 点是C(6,2)*5*7=525 是C(5,2)*6*7=420 同理若B上2点是C(6,2)*5*7=525 若C 点则C(7,2)*5*6=630 上2点则C(7,2)*5*6=630 所以一共 150+210+315+420+525+630=2250

2
10个字母 一共 是10个字母 abc在第一位时 后面一共有105 在第一位时, 105种排列 当abc在第一位时,后面一共有105种排列 (7!/(2!*4!)=105) abc在第二位时 也是105 在第二位时, 105种 当abc在第二位时,也是105种 abc在第八位时 也是105. 105*8=840种 在第八位时, ... 当abc在第八位时,也是105. 105*8=840种 里面有重复的,要减去,就是减去有2个字字串abc abc的 里面有重复的,要减去,就是减去有2个字字串abc的. 一共60 60种 所以840 60=780种 840一共60种 (6!/(2!*3!)=60) 所以840-60=780种



更多相关文章:
cmx-gfj_m排列组合131
排列组合131题 24页 免费 NOIP数学之排列组合 33页 10财富值 概率计算题 45页...--别林斯基排列组合 131 题+详解 1.3 名医生和 6 名护士被分配到 3 所所...
NOIP2002普及组解题报告
NOIP2002普及组解题报告_初二数学_数学_初中教育_教育专区。NOIP2002普及组 ...由于组合不同于排列,与这 k 个数的排列顺序无 关,所以我们可以令 a[I]...
NOIP NOIP复历届解析加备考指导
NOIP-2009-A 潜伏者 动态规划 子序列 DP,贪心优化 数学 模拟 置换群,贪心 ...。 道的。 1. 排列生成算法 . 2. 组合生成算法 . 3. 排列按序生成法 ....
NOIP初赛复习——算法2
NOIP初赛复习——算法2_理学_高等教育_教育专区。OK...mod 规律公式 4.排列组合数,错排 5.Catalan 数 ...由于数字较大,数学不好的他不会统计,所以他请你来...
NOIP复习资料(C++版)_图文
NOIP复习资料(C++版)_学科竞赛_高中教育_教育专区。noip 前言NOIP 复习资料(C++...185 第十一单元 数学基础 ... 116 组合数学 ... 116 组合数的计算! ......
算法试题之一
5页 5财富值 NOIP数学之排列组合 33页 10财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
NOIP复习资料
NOIP复习资料_计算机软件及应用_IT/计算机_专业资料...直接输出结果或仅仅简单的数学计算 (如 y=n/2*3...(0, depth) 2.3 DFS 产生全排列组合(无重集...
NOIP排列组合问题的十种解题策略
NOIP中排列组合问题的十种解题策略_计算机软件及应用_IT/计算机_专业资料。排列一...3页 免费 NOIP数学--排列组合 28页 免费 NOIP数学--总述 45页 免费©...
历年NOIP问题求解
历年NOIP问题求解_学科竞赛_初中教育_教育专区。信息...___个 解:这是个排列组合问题中的组合问题。 ...衡水中学文科学霸高中数学笔记 清华附中文科学霸高中政治...
初赛习题分析二
noip 初赛 复赛 试题 解析noip 初赛 复赛 试题 解析隐藏>> 一、单项选择题 (...【分析】432 用排列组合即可,先确定 12346 的顺序,然后将 7 插入内部有两个...
更多相关标签:
数学排列组合    高中数学排列组合    数学排列组合公式    高中数学排列与组合    高中数学排列组合习题    高中数学排列组合题型    高中数学排列组合公式    高中数学排列组合教案    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图