数学竞赛论-5组合

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

1、2-5数学竞赛中的组合问题数学竞赛中的组合数学不是一个严格的概念，它离中学教材最远，通常指中学代数、几何、算术（数论）之外的内容（俗称杂题）．对中学生而言，这类问题的基本特点是不需要专门的数学语言就可以表述明白，解决起来也没有固定的程式（非常规），常需精巧的构思．从内容上可以归结为两大类：组合计数问题，组合设计问题．（1）组合计数问题这包括有限集合元素的计算、相应子集的计算、集合分拆方法数的计算等，表现为数值计算、组合恒等式或组合不等式的证明．知识基础是加法原理、乘法原理和排列组合公式；常用的方法有：代数恒等变形、二项式定理、数学归纳

2、法、递推、组合分析、容斥原理等．（2）组合设计问题其基本含义是，对有限集合，按照性质来作出安排，有时，只是证实具有性质的安排是否存在、或者验证作出的安排是否具有性质（称为存在性问题，又可分为肯定型、否定型和探究型）；有时，则需把具体安排（或具体性质）找出来（称为构造型问题）；进一步，还要找出较好的安排（称为最优化问题）．值得注意的一个新趋势是组合与几何、数论的结合，产生组合几何、组合数论，它们与集合分拆一起组成IMO试题的三个热点，突出而鲜明的体现数学竞赛的“问题解决”特征．这三方面之所以成为热点，从思维方式、解题技巧上分析，是因为其

3、更适宜数学尖子的脱颖而出，且常与现代数学思想相联系；从技术层面上分析，还由于都能方便提供挑战中学生的新颖题目．链接资料组合数学又称组合分析或组合学．研究将有限个元素安排到适合（服从）某些限制条件的集合．有三个基本问题：（1）组态问题，解决存在这种安排的条件，给出明确的结论；　（2）组态存在时，确定其数目或将它们进行分类；（3）研究安排的性质和结构，包括最优化问题．组合数学最早出现的是神话传说：大禹时代（公元前2200年）的神龟背上驮着的幻方，古代称为"九宫"，即　　492　357　　816　　　一般是将放到格子中，使每行每列各数之和相

4、等，称为阶幻方．还有缺角棋盘的覆盖问题、柯克曼１５女生散步问题、欧拉３６名军官问题都是著名的组合学例子．现代科学技术中，又提出离散性问题及关系结构分析，图论、信息论、编码、实验设计、线性规定划等领域也提了一系列问题，促进了组合学的发展．一．中的组合题（智力题）1．数量统计从开始，占20%2．基本类型（1）组合计数问题：①问题类型有限集合元素的计算，子集的计算，集合分拆的计算②解题方法：代数恒等变形二项式定理组合等式递推组合分析容斥原理数学归纳法．（2）组合设计问题：对集合A，按照某种性质P来作出安排．①问题类型存在性问题，构造性问题，

5、最优化问题．②解题方法：构造法、反证法抽屉原理染色方法递推方法更多的解题技巧见§2-73．发展特点以组合计数、组合设计为基础，与数论、几何交叉，形成组合数论、组合几何、集合分拆三大热点．二、基础知识（与基本类型相一致）有７个定义、9条定理：定义１从个不同的元素中取出个，按照一定的顺序排成一列，叫做从个不同的元素中取出个元素的一个排列．相异元素排列数的计算公式为：．定义２从个不同的元素中取出个，并成一组，叫做从个不同的元素中取出个元素的一个组合．相异元素组合数的计算公式为：．定理１（加法原理）做一件事，完成它可以有类办法，在第一类办法中

6、有种不同的方法，在第二类办法中有种不同的方法，，在第类办法中有种不同的方法，那么完成这件事共有种不同的方法．定理2（乘法原理）做一件事，完成它需要分成个步骤，做第一步有种不同的方法，做第二步有种不同的方法，，做第步有种不同的方法，那么完成这件事共有种不同的方法．定理3组合恒等式（1）（2）（3）（4）定理4（二项式定理）定义３从个不同的元素中取出个，按照一定的顺序排在一个封闭曲线上，叫做环形排列（或循环排列、圆排列）．相异元素的圆排列数公式为：定义４从个不同的元素中，允许重复取出个元素，按照一定的顺序排成一列，称为个相异元素允许重复的

7、元排列．相异元素的可重复排列数计算公式为：定义５从个不同的元素中，允许重复取出个元素，不管怎样的顺序并成一组，称为个相异元素允许重复的元组合．相异元素的可重复组合数计算公式为：定义６若个元素中，有个，个个，且，则这个元素的全排列，称为不尽相异元素的全排列．不尽相异元素的全排列公式为：定义７如果是一个元有限集合，那么，它的子集组成的集合叫做的一个子集系．定理5元集合中含有个元素的子集有个；集合的所有子集共个．定理6（抽屉原理）（1）若把元素放进个集合，则必存在一个集合至少放有个元素．（2）若把个元素放进个集合，则至少有个集合的元素一样多

8、．（3）若把元素放进个集合，则必有一个集合至多含有个元素．定理7（容斥原理）设集合，记为对于全集的补集，则(1)(2)　　定理8（自然数的良序性）自然数的任一非空子集中，必有一个元素是最小的．　　定理9设是两个有限元集合