高中奥赛数学竞赛专题讲座 组合数学课件.ppt

1、 数学竞赛中数学竞赛中 的组合问题的组合问题 （一）主要类型（一）主要类型1、组合计数问题、组合计数问题 包括有限集合元素的计算、相应子集的计算、包括有限集合元素的计算、相应子集的计算、集合分拆方法数的计算等，表现为数值计算、组合集合分拆方法数的计算等，表现为数值计算、组合恒等式或组合不等式的证明知识基础是加法原理、恒等式或组合不等式的证明知识基础是加法原理、乘法原理和排列组合公式；常用的方法有：代数恒乘法原理和排列组合公式；常用的方法有：代数恒等变形、二项式定理、数学归纳法、递推、组合分等变形、二项式定理、数学归纳法、递推、组合分析、容斥原理等析、容斥原理等一、概论一、概论（一）主要类型（一

2、）主要类型1、组合计数问题包括：、组合计数问题包括：问题类型：问题类型：主要有：有限集合元素的计算、子集的计算、集合分主要有：有限集合元素的计算、子集的计算、集合分拆的计算拆的计算解题方法：解题方法：主要有：代数恒等变形、二项式定理、组合等式、递主要有：代数恒等变形、二项式定理、组合等式、递推、组合分析、容斥原理、数学归纳法。推、组合分析、容斥原理、数学归纳法。一、概论一、概论（一）主要类型（一）主要类型2、组合设计问题、组合设计问题 其基本含义是，对有限集合，按照性质来作出其基本含义是，对有限集合，按照性质来作出安排，有时，只是证实具有性质的安排是否存在、安排，有时，只是证实具有性质的安排是

3、否存在、或者验证作出的安排是否具有性质（称为存在性问或者验证作出的安排是否具有性质（称为存在性问题，又可分为肯定型、否定型和探究型）；有时，题，又可分为肯定型、否定型和探究型）；有时，则需把具体安排（或具体性质）找出来（称为构造则需把具体安排（或具体性质）找出来（称为构造型问题）；进一步，还要找出较好的安排（称为最型问题）；进一步，还要找出较好的安排（称为最优化问题）优化问题）一、概论一、概论（一）主要类型（一）主要类型2、组合设计问题：对集合、组合设计问题：对集合A，按照某种性质，按照某种性质P来作出来作出安排，包括安排，包括问题类型问题类型主要有：存在性问题，构造性问题，最优化问题主要有：

4、存在性问题，构造性问题，最优化问题解题方法：解题方法：主要有：构造法、反证法、抽屉原理、染色方法、主要有：构造法、反证法、抽屉原理、染色方法、递推方法递推方法一、概论一、概论（二）（二）发展特点发展特点 以组合计数、组合设计为基础，与数论、几何以组合计数、组合设计为基础，与数论、几何交叉，形成组合数论、组合几何、集合分拆三大热交叉，形成组合数论、组合几何、集合分拆三大热点点，突出而鲜明的体现数学竞赛的，突出而鲜明的体现数学竞赛的“问题解决问题解决”特征这三方面之所以成为热点，从思维方式、解特征这三方面之所以成为热点，从思维方式、解题技巧上分析，是因为其更适宜数学尖子的脱颖而题技巧上分析，是因为

5、其更适宜数学尖子的脱颖而出，且常与现代数学思想相联系；从技术层面上分出，且常与现代数学思想相联系；从技术层面上分析，还由于都能方便提供挑战中学生的新颖题目析，还由于都能方便提供挑战中学生的新颖题目一、概论一、概论有个定义、有个定义、9个定理：个定理：定义定义 从从n个不同的元素中取出个不同的元素中取出m个，按照一定个，按照一定的顺序排成一列，叫做从的顺序排成一列，叫做从n个不同的元素中取出个不同的元素中取出m个元素的一个排列个元素的一个排列相异元素排列数的计算公式为：相异元素排列数的计算公式为：二、二、基础知识基础知识 11n!11mnmnmnACmmnnmnnnAo 定义定义 从从n个不同的

6、元素中取出个不同的元素中取出m个，并成一个，并成一组，叫做从组，叫做从n个不同的元素中取出个不同的元素中取出m个元素的个元素的一个组合一个组合o 相异元素组合数的计算公式为：相异元素组合数的计算公式为：二、二、基础知识基础知识 11123111mnmnnmmmnmnCmnCmmmnnnAACo 定理定理 （加法原理）（加法原理）o 定理定理2 （乘法原理）（乘法原理）o 定理3 组合恒等式o(1)o(2)o(3)o(4)二、二、基础知识基础知识 0mn mnnCCmn1111mmmnnnCCCmn02.nknnkC010.nkknkCo 定理定理4 （二项式定理）（二项式定理）o o 定义定义

7、 从从n个不同的元素中取出个不同的元素中取出m个，按照一个，按照一定的顺序排在一个封闭曲线上，叫做环形排列定的顺序排在一个封闭曲线上，叫做环形排列（或循环排列、圆排列）（或循环排列、圆排列）o 相异元素的相异元素的 圆排列数公式为：圆排列数公式为：二、二、基础知识基础知识 0.nnkn kknkabC abmnmnCmmAmnf!1,o 定义定义 从从n个不同的元素中，允许重复取出个不同的元素中，允许重复取出m个元素，按照一定的顺序排成一列，称为个元素，按照一定的顺序排成一列，称为n个个相异元素允许重复的相异元素允许重复的m元排列元排列o 相异元素的可重复排列数计算公式为：相异元素的可重复排列

8、数计算公式为：o 定义定义 从从n个不同的元素中，允许重复取出个不同的元素中，允许重复取出m个元素，不管怎样的顺序并成一组，称为个元素，不管怎样的顺序并成一组，称为n个个相异元素允许重复的相异元素允许重复的m元组合元组合o 相异元素的可重复组合数计算公式为：相异元素的可重复组合数计算公式为：二、二、基础知识基础知识,.mU n mn1,.mn mf n mC定义定义 若若n个元素中，有个元素中，有n1个个a1，n2个个a2个个a，且，则这个元素的且，则这个元素的全排列，称为不尽相异元素的全排列全排列，称为不尽相异元素的全排列不尽相异元素的全排列公式为：不尽相异元素的全排列公式为：定义定义 如果

9、是一个元有限集合，那么，它如果是一个元有限集合，那么，它的子集组成的集合的子集组成的集合叫做的一个子集系叫做的一个子集系二、二、基础知识基础知识 12mnnnn1212!,.!mmnV n nnn nn12,mA AA12,mRA AA定理定理5 元集合中含有个元素的子集有元集合中含有个元素的子集有个；集合的所有子集共有个个；集合的所有子集共有个o 定理定理6（抽屉原理）（抽屉原理）o（1）把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。o（2）把多于mn+1个的物体放到n个抽屉里，则至少有一个抽屉里有不少于m+1的物体。（3）把（mn1）个物体放入n个抽屉中，其中必有一个

10、抽屉中至多有（m1）个物体。二、二、基础知识基础知识 0kknknC2n举例说明抽屉原理抽屉原理o例1 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道理.o解 从三种玩具中挑选两件，搭配方式只能是下面六种：o（兔、兔），（兔、熊猫），（兔、长颈鹿），（熊猫、熊猫），（熊猫、长颈鹿），（长颈鹿、长颈鹿）o把每种搭配方式看作一个抽屉，把7个小朋友看作物体，那么根据原则1，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式，选的玩具相同.举例说明抽屉原理抽屉原理o 例2正方体各面上

11、涂上红色或蓝色的油漆（每面只涂一种色），证明正方体一定有三个面颜色相同.o 证明：把两种颜色当作两个抽屉，把正方体六个面当作物体，那么6=22+2，根据原则二，至少有三个面涂上相同的颜色.举例说明抽屉原理抽屉原理o例3 从自然数1，2，3，99，100这100个数中随意取出51个数来，求证：其中一定有两个数，它们中的一个是另一个的倍数.o解设第一个抽屉里放进数：1，12，122，123，124，125，126；o第二个抽屉时放进数：3，32，322，323，324，325；o第三个抽屉里放进数：5，52，522，523，524；oo第二十五个抽屉里放进数：49，492；o第二十六个抽屉里放进数

12、：51.oo第五十个抽屉里放进数：99.o那么随意取出51个数中，必有两个数同属一个抽屉，其中一个数是另一个数的倍数.定理定理7（容斥原理）设集合（容斥原理）设集合 ，记，记 为为 对于全集的补集，则对于全集的补集，则(1)(2)定理定理8（自然数的良序性）自然数的任一非空子集中，（自然数的良序性）自然数的任一非空子集中，必有一个元素是最小的必有一个元素是最小的 二、二、基础知识基础知识 12,nAa aa12,mA AAAiAiA12mAAA1111121.miijijkiij mij k nmmAAAAAAAAA 1212.mmAAAAAAA定理9 设A,B是两个有限元集合，分别是两集合的

13、元素个数，f是A到B的一个映射（）若f是单射，则 ；特别的，f是单射而非满射，则（）若f是满射，则（）若f是一一映射（双射），则 二、二、基础知识基础知识,A BABABABAB（二）、高中数学竞赛大纲 中组合问题的要求1、圆排列，有重复元素的排列与组合，组合恒等式2、组合计数，组合几何 3、抽屉原理4、容斥原理 5、极端原理6、图论问题 7、集合的划分8、覆盖9、平面凸集、凸包及应用*（加试中暂不考，但在冬令营中可能考）二、二、基础知识基础知识 o1、计数问题、计数问题三、题型举例三、题型举例 o1、计数问题、计数问题三、题型举例三、题型举例 o2、染色问题、染色问题三、题型举例三、题型举例

14、 o3、存在性问题、存在性问题三、题型举例三、题型举例 o4、组合构造、组合构造三、题型举例三、题型举例 o5、组合数论、组合数论三、题型举例三、题型举例 o6、操作性问题、操作性问题三、题型举例三、题型举例 o7、最值性问题、最值性问题三、题型举例三、题型举例 o8、图论、图论o9、组合方法、组合方法o10、综合问题、综合问题三、题型举例三、题型举例 在高中数学联赛的所有题目中，相信最让大家头痛的莫过于组合在高中数学联赛的所有题目中，相信最让大家头痛的莫过于组合题了，有些同学觉得做组合题很容易就绕晕了，不知道如何下手；有题了，有些同学觉得做组合题很容易就绕晕了，不知道如何下手；有些同学看了答

15、案总是会说，这个题想法太怪了，不可能想不出来；有些同学看了答案总是会说，这个题想法太怪了，不可能想不出来；有些同学好不容易想出了答案，却经常因为表达不清楚而得不到分。确些同学好不容易想出了答案，却经常因为表达不清楚而得不到分。确实，组合题对数学思维的要求非常高，它经常作为联赛二试的最后一实，组合题对数学思维的要求非常高，它经常作为联赛二试的最后一题出现，会比另外几块内容难上很多，但也并不是无迹可寻的。题出现，会比另外几块内容难上很多，但也并不是无迹可寻的。组合问题的知识点并不多，主要在于对问题性质的探索与思考。组合问题的知识点并不多，主要在于对问题性质的探索与思考。联赛中组合题以存在性问题和最值问题以及组合数论问题为主，这类联赛中组合题以存在性问题和最值问题以及组合数论问题为主，这类问题的关键常常在于构造例子或反例。因此，只要我们多加练习这两问题的关键常常在于构造例子或反例。因此，只要我们多加练习这两类问题，在联赛中还是可以拿到满意的分数的。类问题，在联赛中还是可以拿到满意的分数的。四、结束语四、结束语 2016-07-232016-07-23