当前位置:首页 >> 学科竞赛 >>

2015年寒假高中数学联赛预习材料(组合)


QBXT/JY/YXCL2015/1-1-3

(2015 年寒假集中培训课程使用)

2015 年寒假高中数学联赛预习材料
(组合部分)

资料说明

本导学用于学员在实际授课之前,了解授课方向及重难点。同时还附上部分知识点的 详细解读。本班型导学共由 4 份书面资料构成。

r />清北学堂学科邮箱 自主招生邮箱 数学竞赛邮箱 物理竞赛邮箱 化学竞赛邮箱 生物竞赛邮箱 理科精英邮箱 清北学堂官方博客 http://blog.sina.com.cn/tsba wuli@qbxt.cn shuxue@qbxt.cn wuli@qbxt.cn huaxue@qbxt.cn bilolgy@qbxt.cn wuli@qbxt.cn
清北学堂微信订阅号 学习资料最新资讯

2015-1 发布

清北学堂教学研究部

清北学堂集中培训课程预习材料

2015 年寒假高中数学联赛预习材料 (组合部分)

知识梳理........................................................................................................................................... 3 排列、组合、概率(permutations, combinatorics, probability) ....................................... 3 1、排列组合的基本公式 ................................................................................................. 3 2、计数方法..................................................................................................................... 4 3、证明组合恒等式的方法 ............................................................................................. 5 4、二项式定理 ................................................................................................................. 6 5、概率............................................................................................................................. 6 6、数学期望与方差 ......................................................................................................... 6 7、概率分布..................................................................................................................... 7 组合问题(combinatorics) ................................................................................................... 7 1、组合计数问题 ............................................................................................................. 7 2、组合恒等式,不等式 ................................................................................................. 7 3、图论............................................................................................................................. 7 4、常用定理..................................................................................................................... 7

www.qbxt.cn

北京清北学堂教育科技有限公司

第2页

清北学堂集中培训课程预习材料

知识梳理
排列、组合、概率(permutations, combinatorics, probability)
1、排列组合的基本公式

1.1 加法、乘法原理 1.2 无重复的排列组合 1.3 可重复的排列组合
(上述三项为高中课内要求掌握内容,请读者自行参考课本)

1.4 圆排列、项链排列
从 n 个不同元素中不重复地取出 m(1≤m≤n)个元素在一个圆周上,叫做这 n 个不同 元素的圆排列。如果一个 m-圆排列旋转可以得到另一个 m-圆排列,则认为这两个圆排列相 同。 n 个不同元素的 m-圆排列个数 N 为:

特别地,当 m=n 时,n 个不同元素作成的圆排列总数 N 为: 1.5 一类不定方程非负整数解的个数
即: “隔板模型”的实际应用例子。隔板模型的具体内容见下方

1.6 错位排列数
一般地,设 n 个编号为 1、2、3、… 、i、…、j、…、n 的不同元素 a1、a2、a3、…、ai、…、 aj、…、an,排在一排,且每个元素均不排在与其编号相同的位置,这样的全错位排列数为 Tn ,则 T2=1,T3=2,Tn= (n-1) ( Tn-1+Tn-2) , (n≥3) n 个元素全错位排列的排列数为:
n?2 n ?3 0 ? An ? ??? ? (?1) n An (1)Tn= An =

n! n! n! ? ? ??? ? (?1)n ? 2! 3! n!

= n !? [

1 1 1 ? ? ??? ? (?1) n ? ] (n≥2). 2! 3! n!
n

(2)Tn=nTn-1+ (?1)
www.qbxt.cn

北京清北学堂教育科技有限公司

第3页

清北学堂集中培训课程预习材料

2、计数方法

2.1 映射法
将所求的数量与已知数量建立映射关系,从而通过求映射数来求解。

2.2 容斥原理
简单集合运算后集合元素的计数比较简单,但对于复杂结构集合,情况远非如此。

简单集合运算后集合元素的计数比较简单,但对于复杂结构集合,情况远非如此。

2.3 递推法
按照某一种标准找出每一步数量的递推关系。并求出 n 取前几个数时的具体值,带入递推 关系式中,从而求得所需要的值。

2.4 折线法
适合“互相追逐”的问题,即每步或+1,或-1,不得超过某个极限。 下面用一道例题来解释这种方法的应用: 甲乙两人参加竞选,甲得 m 张选票,乙得 n 张选票,m>n.问:在 m+n 张选票逐一唱完的过程 中,甲得的票数一直领先的概率是多少? 解:采用折线法。是甲的选票,取 ak=1;是乙的选票,ak=-1.得到 m+n-1 届的折线,甲的票 数一直领先。由折线法公式,得: N= C m ? 1 ? Cm ? m ? n ?1 m ? n ?1 概率为领先数/总可能数. P=

(m ? n)C m m?n m?n
m (m ? n)Cm ?n m ?1 (m ? n)Cm? n ?1

www.qbxt.cn

北京清北学堂教育科技有限公司

第4页

清北学堂集中培训课程预习材料

2.5 算两次法
在数学中, 算两次是一个非常常用的数学技巧, 常常在组合问题中被提到。 其具体的思想是: 对一个具体问题的对象,以 A 方法研究出来的结果是 a,以 B 方法研究出来的结果是 b,由 此 a=b。此思想虽然明显,但在实际使用时由于方法甲与方法乙通常有明显的差异,因此能 把两个表面上相去甚远的式子联系起来。 (依然没有例题,就跟看笑话似的,大家自己感受 一下)

2.6 母函数法
把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成幂级数间的运 算关系,最后由幂级数来确定离散数列的构造。 简要地说,母函数方法是将一个有限或无限的数列 和如下形式的多项式 f ( x) ? a 0 ? a1 x ? a 2 x ? …… ? ak x ? …… 联系起来,构成对应关系
2 k

{ak } ? f ( x) 。这个f (x)就称为的母函数或生产函数。意思是这个数 {ak } 是由多项式f (x)
产生的。

2.7 常用组合计数思想
1)排除:对有限条件的问题,先从总体考虑,再把不符合条件的所有情况排除,这是解决 排列组合题的常用策略。 2)分类与分步:有些问题的处理可分成若干类,用加法原理,要注意每两类的交集为空集, 所有各类的并集是全集;有些问题的处理分成几个步骤,把各个步骤的方法数相乘, 即得 总的方法数,这是乘法原理。 3)对称思想:两类情形出现的机会均等,可用总数取半得每种情形的方法数。 4)插空:某些元素不能相邻或某些元素在特殊位置时可采用插空法。即先安排好没有限制 条件的元素,然后将有限制条件的元素按要求插入到排好的元素之间。 5)捆绑:把相邻的若干特殊元素“捆绑”为一个“大元素”,然后与其它“普通元素”全排列,然 后再“松绑”,将这些特殊元素在这些位置上全排列。 6)隔板模型:类似求解不定方=M(,M∈N(i=1,2,3??n))的非负整数解的个数的问题, 可以采用隔板法。将 m 个相同的小球与(n-1)个隔板进行排列,第一个隔板之前的小球数 为值,第一个隔板与第二个隔板之前的小球数为值,以此类推。 3、证明组合恒等式的方法

3.1 组合模型法
直接利用组合数的意义来证明. 即构造一个组合问题的模型, 把等式两边看成同一组问题的 两种计算方法,由解的唯一性,即可证明组合恒等式.

www.qbxt.cn

北京清北学堂教育科技有限公司

第5页

清北学堂集中培训课程预习材料

3.2 归纳与递推方法 3.3 母函数法
把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成幂级数间的运 算关系,最后由幂级数来确定离散数列的构造。 简要地说,母函数方法是将一个有限或无限的数列 和如下形式的多项式 f ( x) ? a 0 ? a1 x ? a 2 x ? …… ? ak x ? …… 联系起来,构成对应关系
2 k

{ak } ? f ( x) 。这个f (x)就称为的母函数或生产函数。意思是这个数 {ak } 是由多项式f (x)
3.4组合互逆公式

设{an}是一个给定的数列,若 bk= ? (?1) l
l ?0 k k

? ?a ,k=0,1,2,?,
k l l

an= ? (?1) k
k ?0

? ?b ,n=0,1,2,?,
n k k

则称{an}与{bk}为一对组合互逆公式
此外,还有 Abel 方法、算子方法等。 4、二项式定理

1 n ?1 2 n?2 2 n ?1 ( a ? b) n ? a n ? Cn a b ? Cn a b ? ? ? Cn abn ?1 ? b n
0 1 2 2n ? Cn ? Cn ? Cn ? n ?1 n ? Cn ? Cn

5、概率
5.1 独立事件概率 5.2 互逆事件概率 5.3 条件概率
(此为高中课本内容,由读者自行学习)

6、数学期望与方差
(此为高中课本内容,由读者自行学习)
www.qbxt.cn 北京清北学堂教育科技有限公司 第6页

清北学堂集中培训课程预习材料

7、概率分布
二项分布、几何分布、正态分布(此为高中课本内容,由读者自行学习)

组合问题(combinatorics) 1、组合计数问题
(参见上一部分的 1 和 2)

2、组合恒等式,不等式
(参见上一部分的 3)

3、图论
3.1 托兰定理 3.2 拉姆塞定理
定理内容:在一个聚会中,当聚会人数大于或等于 6 时,则必定有 3 个人彼此认识或 者彼此都不认识。 拉姆塞定理的证明通常用图论的方法, 大体思路就是用六个点代表参加聚会的六个人, 将相互认识的两个人用红线连接, 不认识的用蓝线连接, 这样就得到一个由六个点以及六个 点之间的 15 条线构成的图形。结果是,不论你怎么连接,总能够出现一个三边全为红线或 者三边全为蓝线的三角形, 说明六个人中总有三个人互相认识或者互相不认识, 这就证明了 拉姆塞定理。 拉姆塞定理可以看做是抽屉原理的一个延伸。

4、常用定理
4.1 抽屉原理
表述一:把多于n 个的物体放到n 个抽屉里,则至少有一个抽屉里的东西不少于两件。 表述二:把多于mn??k(k ??0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于m ?1 个的物体。 表述三:把无穷多件物体放入n 个抽屉,则至少有一个抽屉里有无穷个物体。 抽屉原理为解决一些存在性问题提供了一种巧妙的方法。

www.qbxt.cn

北京清北学堂教育科技有限公司

第7页

清北学堂集中培训课程预习材料

4.2 极端原理
1)最小数原理、最大数原理 命题一有限个实数中,必有一个最小数(也必有一个最大数)。 命题二任意有限个两两不同的实数可以从小到大排列顺序。 上述两个命题对无穷多个实数可 能不成立, 例如对于集合{2-n|n∈N}, 其中就没有最小的数。 对于自然数集, 有最小数原理: 若 M 是自然数集 N 的任一非空子集(有限或无限均可) ,则 M 中必有最小的数。 2)最短长度原理、最短长度原理 1:任意给定两点,所有连接这两点的线中,以直线段的长度为最短。 2:在连接一已知点和已知直线或已知平面的点的所有线中,以垂线段的长度为最短。

www.qbxt.cn

北京清北学堂教育科技有限公司

第8页


相关文章:
【解答】清北学堂2015年寒假数学联赛模拟(李建泉)
【解答】清北学堂2015年寒假数学联赛模拟(李建泉)_学科竞赛_高中教育_教育专区。清北学堂 2015 年寒假数学联赛模拟(李建泉命制) ? 的中点分别为 M , N ,对角...
2015年全国高中数学联合竞赛的通知 (1)
关于组织我省中学生 参加 2015 年全国高中数学联合竞赛的通知各设区市教研室、数学会 根据中国数学会高中数学联赛组织委员会通知以及江西省教育厅基教处学科竞赛立项...
2015年全国高中数学联赛决赛
2015年全国高中数学联赛决赛_学科竞赛_高中教育_教育专区。2015 年全国高中数学...试卷包括 4 道解答题,涉及平面几何、代数、数论、 组合四个方面。前两道题每...
近五年全国高中数学联赛选编——组合
近五年全国高中数学联赛选编——组合_学科竞赛_高中教育_教育专区。2015高中数学联赛备考经典 近五年全国高中数学联赛选编——组合 2015.8.17 1.(2010 年 加试 4...
2015年高中数学竞赛辅导计划
2015年高中数学竞赛辅导计划_高二数学_数学_高中教育_教育专区。数学竞赛2015 年高中数学竞赛辅导计划为搞好 2015 年全国数学(安徽赛区)联赛备考工作,并以此为契机,培...
2015年全国高中数学联赛模拟卷二试
2015年全国高中数学联赛模拟卷二试_数学_高中教育_教育专区。2014 年全国高中...组合 1、(本题 40 分)在△ABC 中,AB>BC,K、M 分别 是边 AB 和 AC ...
全国高中数学联赛初赛试卷(校拟)(含参考答案)
全国高中数学联赛初赛试卷(校拟)(含参考答案)_学科竞赛_高中教育_教育专区。高中...东北师大附中理科学霸高中化学选修5笔记240份文档 2015小学生寒假作业 ...
全国高中数学联赛竞赛大纲
年中国数学会普及工作委员会举办全国高中数学联赛以来...提供足够的材料,指导他们阅读,发展他们的数学才能。 ...4.组合问题 圆排列,有重复元素的排列与组合,组合...
高中数学联赛模拟试题(二)部分答案
高中数学联赛模拟试题(二)部分答案_学科竞赛_高中教育...家装材料选购攻略 高端水龙头贵在哪儿 橱柜行业多“...2015小学生寒假作业 小学五年级趣味语文题 小学四...
更多相关标签: