排列组合基础知识及习题分析原版

1 排列组合基础知识及习题分析排列组合基础知识及习题分析 排列 组合的本质是研究 从 n 个不同的元素中 任取 m m n 个元素 有序和无序摆放的各种可能性 区别排列与组合的标志是 有序 与 无序 解答排列 组合问题的思维模式有二 其一是看问题是有序的还是无序的 有序用 排列 无序用 组合 其二是看问题需要分类还是需要分步 分类用 加法 分步用 乘法 分 类 做一件事 完成它可以有 n 类方法 这是对完成这件事的所有办法的一个分类 分类时 首先 要根据问题的特点确定一个适合于它的分类标准 然后在这个 标准下进行分类 其次 分类时要注意满 足两条基本原则 完成这件事的任何一种方法必须属于某一类 分别属于不同两类的两种方法是不 同的方法 分步 做一件事 完成它需要分成 n 个步骤 这是说完成这件事的任何一种方法 都要分成 n 个步骤 分 步时 首先要根据问题的特点 确定一个可行的分步标准 其次 步骤的设置要满足完成这件事必须并 且只需连续完成这 n 个步骤后 这件事才算最终完成 在解决排列与组合的应用题时应注意以下几点 1 有限制条件的排列问题常见命题形式 在 与 不在 邻 与 不邻 在解决问题时要掌握基本的解题思想和方法 相邻 问题在解题时常用 合并元素法 可把两个以上的元素当做一个元素来看 这是处理相邻最 常用的方法 不邻 问题在解题时最常用的是 插空排列法 在 与 不在 问题 常常涉及特殊元素或特殊位置 通常是先排列特殊元素或特殊位置 元素有顺序限制的排列 可以先不考虑顺序限制 等排列完毕后 利用规定顺序的实情求出结果 2 有限制条件的组合问题 常见的命题形式 含 与 不含 至少 与 至多 在解题时常用的方法有 直接法 或 间接法 3 在处理排列 组合综合题时 通过分析条件按元素的性质分类 做到不重 不漏 按事件的发生过 程分步 正确地交替使用两个原理 这是解决排列 组合问题的最基本的 也是最重要的思想方法 习题 1 三边长均为整数 且最大边长为 11 的三角形的个数为 C A 25 个 B 26 个 C 36 个 D 37 个 2 1 将 4 封信投入 3 个邮筒 有多少种不同的投法 2 3 位旅客 到 4 个旅馆住宿 有多少种不同的住宿方法 3 8 本不同的书 任选 3 本分给 3 个同学 每人一本 有多少种不同的分法 3 七个同学排成一横排照相 1 某甲不站在排头也不能在排尾的不同排法有多少种 3600 2 某乙只能在排头或排尾的不同排法有多少种 1440 3 甲不在排头或排尾 同时乙不在中间的不同排法有多少种 3120 4 甲 乙必须相邻的排法有多少种 1440 2 5 甲必须在乙的左边 不一定相邻 的不同排法有多少种 2520 4 用数字 0 1 2 3 4 5 组成没有重复数字的数 1 能组成多少个四位数 300 2 能组成多少个自然数 1631 3 能组成多少个六位奇数 288 4 能组成多少个能被 25 整除的四位数 21 5 能组成多少个比大的数 479 6 求所有组成三位数的总和 32640 5 生产某种产品 100 件 其中有 2 件是次品 现在抽取 5 件进行检查 1 其中恰有两件次品 的抽法有多少种 2 其中恰有一件次品 的抽法有多少种 3 其中没有次品 的抽法有多少种 4 其中至少有一件次品 的抽法有多少种 5 其中至多有一件次品 的抽法有多少种 6 从 4 台甲型和 5 台乙型电视机中任意取出 3 台 其中至少要有甲型和乙型电视机各 1 台 则不同的取 法共有 7 在 50 件产品中有 4 件是次品 从中任抽 5 件 至少有 3 件是次品的抽法有 种 8 有甲 乙 丙三项任务 甲需 2 人承担 乙 丙各需 1 人承担 从 10 人中选派 4 人承担这三项任务 不同的选法共有 9 12 名同学分别到三个不同的路口进行车流量的调查 若每个路口 4 人 则不同的分配方案共有 种 10 在一张节目表中原有 8 个节目 若保持原有节目的相对顺序不变 再增加三个节目 求共有多少种 安排方法 990 解决排列组合问题的策略解决排列组合问题的策略 1 1 逆逆向向思思维维法法 例题 7 个人排座 甲坐在乙的左边 不一定相邻 的情况有多少种 例题 一个正方体有 8 个顶点 我们任意选出 4 个 有多少种情况是这 4 个点可以构成四面体的 例题 用 0 2 3 4 5 这五个数字 组成没有重复数字的三位数 其中偶数共有 A 24 个 B 30 个 C 40 个 D 60 个 2 2 解含有特殊元素 特殊位置的题解含有特殊元素 特殊位置的题 采用特殊优先安排的策略 采用特殊优先安排的策略 1 无关型 两个特殊位置上分别可取的元素所组成的集合的交是空集 例题 用 0 1 2 3 4 5 六个数字可组成多少个被 10 整除且数字不同的六位数 2 包含型 两个特殊位置上分别可取的元素所组成集合具有包合关系 例题 用 0 1 2 3 4 5 六个数字可组成多少个被 5 整除且数字不同的六位奇数 P55 P44 120 24 96 用 0 1 2 3 4 5 六个数字可组成多少个被 25 整除且数字不同的六位数 25 75 3 3 2 1 2 P44 36 24 60 3 影响型 两个特殊位置上可取的元素既有相同的 又有不同的 例题 用 1 2 3 4 5 这五个数字 可以组成比 20000 大并且百位数字不是 3 的没有重复数字的五位 数有多少个 3 3 解含有约束条件的排列组合问题一解含有约束条件的排列组合问题一 采用合理分类与准确分步的策略采用合理分类与准确分步的策略 例题 例题 平面上 4 条平行直线与另外 5 条平行直线互相垂直 则它们构成的矩形共有 个 4 4 解排列组台混合问题 解排列组台混合问题 采用先选后排策略采用先选后排策略 3 对于排列与组合的混合问题 可采取先选出元素 后进行排列的策略 例 例 4 个不同小球放入编号为 1 2 3 4 的四个盒子 则恰有一个空盒的放法有 种 144 5 5 插板法 插板法 插板法的条件构成 1 元素相同 2 分组不同 3 必须至少分得 1 个 插板法的类型 1 10 块奶糖分给 4 个小朋友 每个小朋友至少 1 块 则有多少种分法 典型插板法典型插板法 点评略点评略 2 10 块奶糖分给 4 个小朋友有多少种方法 凑数插板法 凑数插板法 这个题目对照插板法的这个题目对照插板法的 3 3 个条件我们发个条件我们发 现现 至少满足至少满足 1 1 个这个条件没有 个这个条件没有 所以我们必须使其满足 最好的方法所以我们必须使其满足 最好的方法 就是用就是用 1414 块奶糖来分 至少每块奶糖来分 至少每 人人 1 1 块块 当每个人都分得 当每个人都分得 1 1 块之后 剩下的块之后 剩下的 1010 块就可以随便分了 就回归到了原题块就可以随便分了 就回归到了原题 3 10 块奶糖放到编号为 1 2 3 的 3 个盒子里 每个盒子的糖数量不少于其编号数 则有几种方法 定制插板法 定制插板法 已然是最后一个条件不满足 我们该怎么处理呢 应该学会先去安排已然是最后一个条件不满足 我们该怎么处理呢 应该学会先去安排 使得每个盒子都使得每个盒子都 差差 1 1 个 这样就保证每个盒子必须分得个 这样就保证每个盒子必须分得 1 1 个 从这个思路出发 跟第二个例题是姊妹题个 从这个思路出发 跟第二个例题是姊妹题 思路是一样的思路是一样的 对照条件对照条件 想办法使其和条件吻合 想办法使其和条件吻合 4 8 块奶糖和另外 3 个不同品牌的水果糖要放到编号为 1 11 的盒子里面 每个盒子至少放 1 个 有 多少种方法 多次插空法多次插空法 这里不多讲 见我排列组合基础讲义这里不多讲 见我排列组合基础讲义 6 6 递归法 枚举法 递归法 枚举法 公考也有这样的类型 排错信封问题 还有一些邮票问题 归纳法 例如 5 封信一一对应 5 个信封 其中有 3 个封信装错信封的情况有多少种 例如 10 张相同的邮票 分别装到 4 个相同的信封里面 每个信封至少 1 张邮票 有多少种方法 疑难问题疑难问题 1 1 如何验证重复问题 如何验证重复问题 2 2 关于位置与元素的相同问题 关于位置与元素的相同问题 例如 6 个人平均分配给 3 个不同的班级 跟 6 个学生平分成 3 组的区别 3 3 关于排列组合里面 充分运用对称原理 关于排列组合里面 充分运用对称原理 例题 1 2 3 4 5 五个数字可以组成多少个十位数小于个位数的四位数 例题 7 个人排成一排 其中甲在乙右边 可以不相邻 的情况有多少种 注解 分析 2 种对立情况的概率 即可很容易求解 当对立情况的概率相等 即对称原理 4 4 环形排列和线性排列问题 环形排列和线性排列问题 见我的基础排列组合讲义二习题讲解 例如 3 个女生和 4 个男生围坐在一个圆桌旁 问有多少种方法 例如 3 对夫妇围坐在圆桌旁 男女间隔的坐法有多少种 注解 排列组合中 特殊的地方在于 第一个坐下来的人是作为参照物 所以不纳入排列的范畴 我们 知道 环形排列中 每个位置都是相对的位置 没有绝对位置 所以需要有一个人坐下来作为参照位置 5 5 几何问题 见下面部分的内容 几何问题 见下面部分的内容 例析立体几何中的排列组合问题例析立体几何中的排列组合问题 在数学中 排列 组合无论从内容上还是从思想方法上 都体现了实际应用的观点 4 1 点 1 1 1 1 共面的点共面的点 例题 四面体的一个顶点为 A 从其它顶点与棱的中点中取 3 个点 使它们和点 A 在同一平面上 不同 的取法有 A 30 种 B 33 种 C 36 种 D 39 种 答案 B 点评 此题主要考查组合的知识和空间相像能力 属难度中等的选择题 失误的主要原因是没有把每条 棱上的 3 点与它对棱上的中点共面的情况计算在内 1 1 2 2 不共面的点不共面的点 例 2 四面体的顶点和各棱中点共 10 个点 在其中取 4 个不共面的点 不同的取法共有 A 150 种 B 147 种 C 144 种 D 141 种 解析 从 10 个点中任取 4 个点有 C 10 4 210 种取法 其中 4 点共面的情况有三类 第一类 取 出的 4 个点位于四面体的同一个面内 有 C 6 2 15 种 第二类 取任一条棱上的 3 个点及对棱的 中点 这 4 点共面有 6 种 第三类 由中位线构成的平行四边形 它的 4 个顶点共面 有 3 种 以上三类情况不合要求应减掉 所以不同取法共有 210 4 15 6 3 141 种 答案 D 点评 此题难度很大 对空间想像能力要求高 很好的考察了立体几何中点共面的几种情况 排列 组 合中正难则反易的解题技巧及分类讨论的数学思想 几何型排列组合问题的求解策略几何型排列组合问题的求解策略 有关几何型组合题经常出现在各类试题中 它的求解不仅要具备排列组合的有关知识 而且还要掌握相 关的几何知识 这类题目新颖 灵活 能力要求高 因此要求掌握四种常用求解策略 一一 分步求解分步求解 例 1 圆周上有 2n 个等分点 n 1 以其中三个点为顶点的直角三角形的个数为 解 本题所求的三角形 即为圆的内接直角三角形 由平面几何知识 应分两步进行 先从 2n 个点中构 成直径 即斜边 共有 n 种取法 再从余下的 2n 2 个点中取一点作为直角顶点 有 2n 2 种不同取 法 故总共有 n 2n 2 2n n 1 个直角三角形 故填 2n n 1 例 2 从集合 0 1 2 3 5 7 11 中任取 3 个元素分别作为直线方程 Ax By C 0 中的 A B C 所得的经过坐标原点原直线共有 条 结果用数值来表示 解 因为直线过原点 所以 C 0 从 1 2 3 5 7 11 这 6 个数中任取 2 个作为 A B 两数的顺序 不同 表示的直线也不同 所以直线的条数为 P 6 2 30 二二 分类求解分类求解 例 3 四边体的一个顶点为 A 从其它顶点与各棱的中点中取 3 点 使它们和 A 在同一平面上 不同取法 有 A 30 种 B 33 种 C 36 种 D 39 种 解 符合条件的取法可分三类 4 个点 含 A 在同一侧面上 有 3 30 种 4 个点 含 A 在侧 棱与对棱中点的截面上 有 3 种 由加法原理知不同取法有 33 种 故选 B 三三 排除法求解排除法求解 例 4 从正方体的 6 个面中选取 3 个面 其中有 2 个面不相邻的选法共有 A 8 种 B 12 种 C 16 种 D 20 种 解 由六个任取 3 个面共有 C 6 3 20 种 排除掉 3 个面都相邻的种数 即 8 个角上 3 个平面相邻 的特殊情形共 8 种 故符合条件共有 20 8 12 种 故选 B 例 5 正六边形的中心和顶点共 7 个点 以其中 3 个点为顶点的三角形共有 个 解 从 7 个点中任取 3 个点 共有 C 7 3 35 个 排除掉不能构成三角形的情形 3 点在同一直线 5 上有 3 个 故符合条件的三角形共有 35 3 32 个 四四 转化法求解转化法求解 例 6 空间六个点 它们任何三点不共线 任何四点不共面 则过每两点的直线中有多少对异面直线 解 考虑到每一个三棱锥对应着 3 对异面直线 问题就转化为能构成多少个三棱锥 由于这六个点可构 成 C 6 4 15 个三棱锥 故共有 3 15 45 对异面直线 例 7 一个圆的圆周上有 10 个点 每两个点连接一条弦 求这些弦在圆内的交点个数最多有几个 解 考虑到每个凸四边形的两条对角线对应一个交点 则问题可转化为构成凸四边形的个数 显然可构 成 C 10 4 210 个圆内接四边形 故 10 个点连成的点最多能在圆中交点 210 个 6 6 染色问题 染色问题 不涉及环形染色不涉及环形染色 可以采用特殊区域优先处理的方法来分步解决 可以采用特殊区域优先处理的方法来分步解决 环形染色可采用如下公式解决 环形染色可采用如下公式解决 AnAn a a 1 1 n a 1 1 n n a 1 1 n n n 表示被划分的个数 表示被划分的个数 a a 表示颜色种类表示颜色种类 原则 被染色部分编号 并按编号顺序进行染色 根据情况分类 在所有被染色的区域 区分特殊和一般 特殊区域优先处理 例题 1 将 3 种作物种植在如图 4 所示的 5 块试验田里 每块种植一种作物 且相邻的试验田不能种同一 种作物 则有多少种种植方法 图 1 例题 2 用 5 种不同颜色为图中 ABCDE 五个部分染色 相邻部分不能同色 但同一种颜色可以反复使用 也可以不使用 则符合要求的不同染色方法有多少种 图 2 例题 3 将一个四棱锥的五个顶点染色 使同一条棱的 2 个端点不同色 且只由五个颜色可以使用 有多 少种染色方法 图 3 例题 4 一个地区分为如图 4 所示的五个行政区域 现在有 4 种颜色可供选择 给地图着色 要求相邻区 域不同色 那么则有多少种染色方法 图 4 例题 5 某城市中心广场建造了一个花圃 分 6 个部分 如图 5 现在要栽种 4 种不同的颜色的花 每 6 部分栽种一种且相邻部分不能种同样颜色的花 则有多少种不同栽种方式 图 5 1 排列组合题 系列之二 排列组合题 系列之二 一 1 2 3 4 作成数字不同的三位数 试求其总和 但数字不重复 解析 组成 3 位数 我们以其中一个位置 百位 十位 个位 为研究对象就会发现 当某个位置固定 比如是 1 那么 其他的 2 个位置上有多少种组合 这个大家都知道 是剩下的 3 个数字的全排列 P32 我们研究的位置上每个数字都会出现 P32 次 所以每个位置上的数字之和就可以求出来了 个位是 P32 1 2 3 4 60 十位是 P32 1 2 3 4 10 600 百位是 P32 1 2 3 4 100 6000 所以总和是 6660 二 将 PROBABILITY 11 个字母排成一列 排列数有 种 若保持 P R O 次序 则排列数 有 种 解析 这个题目就是直线全排列出现相同元素的问题 在我的另外一个帖子里面有介绍 ead htm tid html 1 我们首先把相同元素找出来 B 有 2 个 I 有 2 个 我们先看作都是不同的 11 个元素全排列 这样就简 单的多是 P11 11 然后把相同的元素能够形成的排列剔除即可 P11 P2 2 P2 2 2 第 2 个小问题 因要保持 PRO 的顺序 就将 PRO 视为相同元素 跟 B I 类似的性质 则其排列数有 1 1 2 2 3 种 三 李先生与其太太有一天邀请邻家四对夫妇共 10 人围坐一圆桌聊天 试求下列各情形之排列数 1 男女间隔而坐 2 主人夫妇相对而坐 3 每对夫妇相对而坐 7 4 男女间隔且夫妇相邻 5 夫妇相邻 6 男的坐在一起 女的坐在一起 解析 1 这个问题也在 介绍过 先简单介绍一下环形排列的特征 环形排列相对于直线排列缺少的就是参照物 第一个坐下来的人是没有 参照物的 所以无论做哪个位置都是一样的 所以从这里我们就可以看出 环形排列的特征是 第一个人是 做参照物 不参与排列 下面就来解答 6 个小问题 1 先让 5 个男的或 5 个女的先坐下来 全排列应该是 P44 空出来的位置他们的妻子 丈夫 妻子 丈夫 的 全排列这个时候有了参照物所以排列是 P55 答案就是 P44 P55 2880 种 2 先让主人夫妇找一组相对座位入座 其排列就是 P11 记住不是 P22 这个时候其他 8 个人再入座 就 是 P88 所以此题答案是 P88 3 每对夫妇相对而坐 就是捆绑的问题 5 组相对位置有一组位置是作为参照位置给第一个入座的夫妇的 剩下的 4 组位置就是 P44 考虑到剩下来的 4 组位置夫妇可以互换位置即 P44 2 4 384 4 夫妇相邻 且间隔而坐 我们先将每对夫妇捆绑 那么就是 5 个元素做环形全排列 即 P44 这里在从性 别上区分 男女看作 2 个元素 可以互换位置 即答案是 P44 2 48 种 值得注意的是 这里不是 2 4 因为要 互换位置 必须 5 对夫妇都得换 要不然就不能保持男女间隔 5 夫妇相邻 这个问题显然比第 4 个问题简单多了 即看作捆绑 答案就是 P44 但是这里却是每对夫妇呼 唤位置都可以算一种方法的 即 最后答案是 P44 2 5 6 先从大方向上确定男女分开座 那么我们可以通过性别确定为 2 个元素做环形全排列 即 P1 1 剩下 的 5 个男生和 5 个女生单独做直线全排列 所以答案是 P1 1 P55 P55 四 在一张节目表中原有 8 个节目 若保持原有节目的相对顺序不变 再增加三个节目 求共有多少 种安排方法 8 解析 这个题目相信大家都见过 就是我们这次 2008 年国家公务员考试的一道题目 这是排列组合的一种方法 叫做 2 次插空法或多次插空法 直接解答较为麻烦 我们知道 8 个节目相对位置不动 前后共计 9 个间隔 故可先用一个节目去插 9 个空 位 有 C9 取 1 种方法 这样 9 个节目就变成了 10 个间隔 再用另一个节目去插 10 个空位 有 C10 取 1 种方法 同理用最后一个节目去插 10 个节目形成的 11 个间隔中的一个 有 C11 取 1 方法 由乘法原理 得 所有不同的添加方法为 9 10 11 990 种 方法 2 我们先安排 11 个位置 把 8 个节目按照相对顺序放进去 在放另外 3 个节目 11 个位置选 3 个出 来进行全排列 那就是 P11 3 11 10 9 990 五 0 1 2 3 4 5 五个数字能组成多少个被 25 整除的四位数 解析 这里考察了一个常识性的问题 即 什么样数才能被 25 整除 即这个数的后 2 位必须是 25 或者 50 或者 75 或者 00 方可 后两位是 25 的情况有 千位只有 3 个数字可选 0 不能 百位也是 3 个可选 即 3 3 9 种 后两位是 50 的情况有 剩下的 4 个数字进行选 2 位排列 P4 2 12 种 75 不可能 因为数字中没有 7 00 也不可能 因为数字不能重复 共计 9 12 21 种 2 插板法插板法 的条件模式隐藏运用分析的条件模式隐藏运用分析 在说这在说这 2 2 道关于道关于 插板法插板法 的排列组合题目之前 我们需要弄懂一个问题 的排列组合题目之前 我们需要弄懂一个问题 插板法排列组合是需要什么条件下才可以使用 这个问题清楚了 我们在以后的答题中插板法排列组合是需要什么条件下才可以使用 这个问题清楚了 我们在以后的答题中 就可以尽量的变就可以尽量的变 化题目使其满足这个条件 化题目使其满足这个条件 这个条件就是 分组或者分班等等分组或者分班等等 至少分得一个元素 至少分得一个元素 注意条件是注意条件是 至少分得至少分得 1 1 个元素 个元素 好我们先来看题目 例题 1 某学校四 五 六三个年级组织了一场文艺演出 共演出 18 个节目 如果每个年级至少演出 4 个节目 那么这三个年级演出节目数的所有不同情况共有几种 解析 9 这个题目是 Q 友出的题目 题目中是不考虑节目的不同性 你可以视为 18 个相同的节目 不区分 发现 3 个年级都是需要至少 4 个节目以上 跟插板法的条件有出入 插板法的条件是至少 1 个 这个 时候对比一下 我们就有了这样的思路 为什么我们不把 18 个节目中分别给这 3 个年级各分配 3 个节 目 这样这 3 个班级就都少 1 个 从而满足至少 1 个的情况了 3 3 9 还剩下 18 9 9 个 剩下的 9 个节目就可以按照插板法来解答 9 个节目排成一排共计 8 个间隔 分别选取其中任意 2 个间 隔就可以分成 3 份 班级 C8 取 2 28 练习题目 有 10 个相同的小球 分别放到编号为 1 2 3 的盒子里 要使得每个盒子的小球个数不小于其编号数 那么有多少种放法 解析 还是同样的原理 每个盒子至少的要求和插板法有出入 那么我们第一步就是想办法满足插板法的要求 编号 1 的盒子是满足的 至少需要 1 个 编号 2 至少需要 2 个 那么我们先给它 1 个 这样就差 1 个 编号 3 至少需要 3 个 那么我们先给它 2 个 这样就差 1 个 现在三个盒子都满足插板法的要求了 我们看还剩下几个小球 10 1 2 7 7 个小球 6 个间隔 再按照插板法来做 C6 2 15 种 3 纠错纠错 两个相同的正方体的六个面上分别标有数字的排列组合问题两个相同的正方体的六个面上分别标有数字的排列组合问题 有两个相同的正方体 每个正方体的六个面上分别标有数字 1 2 3 4 5 6 将两个正方体放到桌面 上 向上的一面数字