2014年国庆高中数学竞赛班型知识点梳理3

2014 年 国庆 高中数学竞赛班型知识点梳理 （第 三 次） 资料 说明 本 导学用于学员在实际授课之前，了解授课方向及重难点。同时还附上部分知识点的详细解读。 本 班型导学共由 4 份 书面资料构成。 清北学堂集中培训课程知识点梳 理 （ 2014 年 国庆 集中培训课程使用） QBXT/JY/ZSD2014/9-1-3 2014-9-20 发布 清北学堂教学研究部 清北学堂学科邮箱 自主招生邮箱 数学竞赛邮箱 物理竞赛邮箱 化学竞赛邮箱 生物竞赛邮箱 理科精英邮箱 清北学堂官方博客 /tsba 清北学堂微信订阅号 学习资料最新资讯 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 2 页 2014 年 国庆 高中数学竞赛班型知识点梳理 (组合数学部分 ) 目录 一、 课程重点及难点概述 . 3 二、 清北导学 . 4 排列与组合 . 4 知识点 . 4 组合恒等式 . 6 重点及难点 . 6 知识点 . 6 思考题 . 7 常用排列组合思想 . 8 知识点 . 8 抽屉原理、容斥原理、极端原理 . 9 知识点 . 9 思考题 . 10 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 3 页 一、 课程重点及难点概述 本次 课程 的重点 为组合计数 。 应用基本组合计数原理和组合恒等式来解决实际问题是本次课程的难点。 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 4 页 二、 清北导学 排列与组合 知识点 1. 排列 ： 从 n 个不同元素中，任取 ),( 均为自然数与 nmnmm 个元素按照一定的顺序排成一列，叫做从 n 个不同的元素中取出 m 个元素的一个排列。从 n 个不同的元素中取出 )( nmm 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 mnA 表示。 123)2()1(! nnnn )!( !)1()2)(1( mn nmnnnnA mn 2. 组合： 从 n 个不同元素中，任取 ),( 均为自然数与 nmnmm 个元素并成一组，叫做从 n 个不同的元素中取出 m 个元素的一个组合。从 n 个不同的元素中取出)( nmm 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数，用符号 mnC 表示。!)!( !123)2()1( )1()2)(1( mmn nmmm mnnnnC mn 3. 二项式定理 ： ni iininn baCba 0)( 常用形式 nnnnnnn CCCC 1102 nnnnnnnn CCCC )1()1(0 1110 4. 分类 计数 原理 ： 完成一件事，有几种方式，第一种方式有 m 种方法，第二种方式有n 种方法，最后一种方式有 r 种方法 .不管采取哪一种方法都能完成这件事，则完成这件事的方法总数为 rnm 。应用分类计数原理的关键在于分划。 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 5 页 5. 分步计数原理 ：完成一件事，有几个步骤，第一步有 m 种方法，第二步有 n 种方法，最后一步有 r 种方法，要完成这件事，必须通过每一步，则完成这件事的方法总数为 rnm 。应用分步计数原理的关键在于分解。 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 6 页 组合恒等式 重点及难点 掌握基本的排列组合恒等式、学会组合表达式的化简是本次课程的重点。综合应用组合恒等式和排列组合数学意义来证明某些组合恒等式是本次课程的难点。 知识点 1. 常用 排列组合公式 ： 0)1(212)1()1()1()!(!)1()1()!(!321021011111nnnnnnnnnnnnnmrmnmnmnrnrnrnrnrnrnrnnrnmnmnCCCCCCCCCCCCCCrnCCCCCCmmmnnnmnmnCmnnnmnnA 2. 母函数法 把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成幂级数间的运算关系，最后由幂级数来确定离散数列的构造。 简要地说，母函数方法是将一个有限或无限的数列 , 210 kk aaaaa 和如下形式的多项式 kk xaxaxaaxf 2210)( 联系起来，构成对应关系 ka )(xf 。 这个 )(xf 就称为 ka 的母函数或生产函数 。 意思是这个数列 ka 是由多项式 )(xf产生的 。 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 7 页 例如：组合数列 nnnn CCC , 10 的母函数是 nx)1( 因为由二项式定理可得 nnnnnn xCxCCx 10)1( nx)1( 是最常见的母函数 . 设 ka 与 kb 是两个 给定 的数列，为了确定它们之间的某种关系，可分别写出二者所对应的母函数，再研究这两个母函数间的某种关系从而确定两个数列之间的关系，这便是母函数方法解题的基本思想 。母函数的思想还在很多其他领域有所应用，如概率论中常用的矩母函数法。 思考题 一、求证： nknk n nnnC0122 !2 )!2(2 二、求证： nkk knknk nC0 1222 12)1( 三、设 1n ，且两个自然数的集合满足 , 2121 nn bbbaaa ，其合集满足 1|1| njibbnjiaa jiji （集合相等包括元素重数相等）。求证：存在自然数 h ，使得 hn 2 （提示：利用母函数法） 四、求证： !1 )!2()()()( 22120 nn nCCC nnnn 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 8 页 常用排列组合思想 知识点 （ 1）排除：对有限条件的问题，先从总体考虑，再把不符合条件的所有情况排除，这是解决排列组合题的常用策略 。 （ 2）分类与分步 :有些问题的处理可分成若干类，用加法原理，要注意每两类的交集为空集，所有各类的并集是全集；有些问题的处理分成 几个步骤，把各个步骤的方法数相乘，即得总的方法数，这是乘法原理。 （ 3）对 称思想：两类情形出现的机会均等，可用总数取半得每种情形的方法数。 （ 4）插空：某些元素不能相邻或某些元素在特殊位置时可采用插空法。 即先安排好没有限制条件的元素， 然后将有限制条件的元素按要求插入到排好的元素之间。 （ 5）捆绑：把相邻的若干特殊元素 “ 捆绑 ” 为一个 “ 大元素 ” ，然后与其它 “ 普通元素 ” 全排列，然后再 “ 松绑 ” ，将这些特殊元素在这些位置上全 排列。 （ 6）隔板模型： 类似求解不定方程 ),( NMwzyxMwzyx 的非负整数解的个数的问题，可以采用隔板法。将 M 个相同的小球与 3 个隔板进行排列，第一个隔板之前的小球数为 x 值，第一个隔板与第二个隔板之前的小球数为 y 值，第二个隔板与第三个隔板之前的小球数为 z 值，第三个隔板之前的小球数为 w 值。 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 9 页 抽屉原理、容斥原理、极端原理 知识点 1. 抽屉原理 表述一： 把多于 n 个的物体放到 n 个 抽屉 里，则至少有一个抽屉里的东西不少于两件 。 表述二： 把多于 )0( kkmn 个的物体放到 n 个抽屉里，则至少有一个抽屉里有不少于 1m 个 的物体。 表述三： 把无穷多件物体放入 n 个抽屉，则至少有一个抽屉里有无穷个物体。 抽屉原理为解决一些存在性问题提供了一种巧妙的方法。 2. 容斥原理 简单集合运算后集合元素的计数比较简单，但对于复杂结构集合，情况远非如此。 )()()()( BAC a r dBC a r dAC a r dBAC a r d )()()()()()()()(CBAC a r dCBC a r dCAC a r dBAC a r dCC a r dBC a r dAC a r dCBAC a r d )()1()()()()(1111inikjinkjini jijiiiniAC a r dAAAC a r dAAC a r dAC a r dAC a r d 容斥的思想除了在计数方面有所应用外，在求解传递函数的 Mason 公式中也有所体现。 3. 极端原理 1. 最小数原理、最大数原理 命题一有限个实数中，必有一个最小数（也必有一个最大数）。 命题二任意有限个两两不同的实数可以从小到大排列顺序。上述两个命题对无穷多个实数可能不成立，例如对于集合 2-n|n N，其中就没有最小的数。对于自然数集，有最小数原理：若 M 是自然数集 N 的任一非空子集（有限或无限均可），则 M 中必有最小的数。 2 最短长度原理 、 最短长度原理 清北学堂集中培训课程知识点梳理 北京清北学堂教育科技有限公司 第 10 页 1：任意给定两点，所有连接这两点的线中，以直线段的长度为最短。 2：在连接一已知点和已知直线或已知平面的点的所有线