2013清北学堂寒假数学集训六组合导学-组合计数.pdf

2013 寒假集训六组合导学，内容中标有★的部分，是中学数学竞赛大纲中提出要求的内容，需要引起 同学们注意，希望能提前做好预习和学习准备. 一、组合计数 知识点 组合计数就是计算集合的元素个数.它是组合数学的重要组成部分. 在具体问题中给出的集合各式各样，都具有实际意义，而且集合中的元素是由某些条件所确定的，要 判定一个元素是否属于某集合A ，已非易事，要确定A 的元素个数就更难了.这正是研究计算问题的原因. 解决组合计算问题虽然不需要高深理论知识，却需要重要的计算原理与思想方法. Ⅰ．几种特殊的排列、组合 1．排列组合题的求解策略 （1）排除：对有限条件的问题，先从总体考虑，再把不符合条件的所有情况排除，这是解决排列组合题的 常用策略． （2）分类与分步:有些问题的处理可分成若干类，用加法原理，要注意每两类的交集为空集，所有各类的 并集是全集；有些问题的处理分成几个步骤，把各个步骤的方法数相乘，即得总的方法数，这是乘法原理． （3）对称思想：两类情形出现的机会均等，可用总数取半得每种情形的方法数． （4）插空：某些元素不能相邻或某些元素在特殊位置时可采用插空法．即先安排好没有限制条件的元素， 然后将有限制条件的元素按要求插入到排好的元素之间． （5）捆绑：把相邻的若干特殊元素“捆绑”为一个“大元素”，然后与其它“普通元素”全排列，然后再 “松绑”，将这些特殊元素在这些位置上全排列． （6）隔板模型：对于将不可辨的球装入可辨的盒子中，求装的方法数，常用隔板模型．如将 12 个完全相 同的球排成一列，在它们之间形成的 11 个缝隙中任意插入 3 块隔板，把球分成 4 堆，分别装入 4 个不同的 盒子中的方法数应为 C3 ，这也就是方程a b c d 12 的正整数解的个数． 11 2．圆排列 n 定义 1：从几个元素中任取 r 个不同元素仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为 c n 个不同元素的 r——圆排列.r——圆排列数记为K r . . n t Pr x 定理 1： K r n n r b q 【证明】对 n 个不同元素取 r 个的任一圆排列，均有 r 种不同的方式展开成 r 个不同的直线排列，且不同的 . 圆排列展开的直线排列也彼此不同，故有r K r Pr ，得正. n n w 3．重复排列 ww 定义 2：从 n 个不同元素中允许重复的任取 r 个元素排成一列，称为 n 个不同元素的 r——可重复排列. r 定理 2：n 个不同元素的 r——可重排列数为 n . r 【证明】在按顺序选取的 r 个元素中，每个元素都有 n 种不同的选法，故由乘法原理有，其排列数为 n . 4．不全相异元素的全排列 定义 3：设 n 个元素可分为 k 组，每一组中的元素是相同的，不同组间的元素是不同的，其中第 i 组的元素 个数为 n （i=1， 2， „， k ）， n +n +„+n =n . 则这 n 个元素的全排列称为不全相异元素的全排列. i 1 2 k