清北学堂 2012年五一数学精品班(集训七)组合导学(组合计数 组合应用-凸图形 凸包等).pdf

北京清北学堂教育科技有限公司     电话：010010   网址：    组合导学  一、 组合计数  知识点： （1）几种特殊的排列、组合 1．圆排列 定义1：从几个元素中任取r个不同元素仅按元素之间的相对位置而不分首尾排 成一个圆圈，这种排列称为n个不同元素的r——圆排列。r——圆排列数记为 K r . n P r 定理1：K r n n r 2．重复排列 定义2：从n个不同元素中允许重复的任取r个元素排成一列，称为n个不同元 素的r——可重复排列. r 定理2：n个不同元素的r——可重排列数为n . 3．不全相异元素的全排列 定义3：设n个元素可分为k组，每一组中的元素是相同的，不同组间的元素是 不同的，其中第i组的元素个数为ni(i=1, 2, …, k ), n +n ++n n . 则 1 2 k 这n个元素的全排列称为不全相异元素的全排列. n ! 定理3：n个元素的不全相异元素的全排列个数为 n !n !n ! 1 2 k 4．多组组合 定义4：将n个不同的元素分成k组的组合称为n个不同元素的k——组合. 1    北京清北学堂教育科技有限公司     电话：010010   网址：    定理4：对于一个n个不同元素的k——组合，若第i组有ni个元素（i=1, 2, …， n ! k），则不同的分组方法数为 n !n !n ! 1 2 k 5．重重组合 定义5：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素 的r——可重组合. 定理5：n个不同元素的r——可重组合的个数为Cr . n+r −1 （2）枚举法 所谓枚举法就是把集合A中的元素一一列举出来，从而计算出集体A的元素个数。 它是最基本，也是最简单的计算数方法。应用枚举法计数的关键在于一一列举集 合中的元素时必须做到既不重又不漏。 （3）分类计数原理与分步计数原理 分类计算原理 完成一件事，有几种方式，第一种方式有m种方法，第二种方式 有n种方法，……最后一种方式有r种方法.不管采取哪一种方法都能完成这件 事，则完成这件事的方法总数为m+n+…+r . 分步计数原理 完成一件事，有几个步骤，第一步有m种方法，第二步有n种方 法，…，最后一步有r种方法，要完成这件事，必须通过每一步，则完成这件事 的方法总数为m·n……r. 应用分类