当前位置:首页 >> 其它课程 >>

排列组合


Name_________ Grade__________ Date__________

优胜教育东直门校区

个 性 化 教 材
教 教 学 主 题:

学 重 难 点:

授 课 内 容
排列组合基础知识及习题分析 在介绍排列组合方法之前 我们先来了解一下基本的运算公式!

r />
3 =(5×4×3)/(3×2×1) C5
通过这 2 个例子 看出

2 =(6×5)/(2×1) C6

n Cm

公式 是种子数 M 开始与自身连续的 N 个自然数的降序乘积做为分子。 以取值 N 的阶层作为分母

3 P 5 =5×4×3
通过这 2 个例子

P66 =6×5×4×3×2×1

n =从 M 开始与自身连续 N 个自然数的降序乘积 当 N=M 时 即 M 的阶层 Pm
排列、 组合的本质是研究 “从 n 个不同的元素中, 任取 m (m≤n)个元素, 有序和无序摆放的各种可能性” . 区别排列与组合的标志是“有序”与“无序”. 解答排列、组合问题的思维模式有二: 其一是看问题是有序的还是无序的?有序用“排列” ,无序用“组合” ; 其二是看问题需要分类还是需要分步?分类用“加法” ,分步用“乘法”. 分 类: “做一件事,完成它可以有 n 类方法” ,这是对完成这件事的所有办法的一个分类.分类时,首先 要根据问题的特点确定一个适合于它的分类标准,然后在这个 标准下进行分类;其次,分类时要注意满 足两条基本原则:①完成这件事的任何一种方法必须属于某一类;②分别属于不同两类的两种方法是不 同的方法. 分步: “做一件事,完成它需要分成 n 个步骤” ,这是说完成这件事的任何一种方法,都要分成 n 个步骤. 分步时,首先要根据问题的特点,确定一个可行的分步标准;其次,步骤的设置要满足完成这件事必须 并且只需连续完成这 n 个步骤后,这件事才算最终完成. 两 个原理的区别在于一个和分类有关,一个与分步有关.如果完成一件事有 n 类办法,这 n 类办法彼此 之间是相互独立的,无论那一类办法中的那一种方法都能单独完 成这件事,求完成这件事的方法种数, 就用加法原理;如果完成一件事需要分成 n 个步骤,缺一不可,即需要依次完成所有的步骤,才能完成 这件事,而完成每一个 步骤各有若干种不同的方法,求完成这件事的方法种类就用乘法原理. 在解决排列与组合的应用题时应注意以下几点:

1

1.有限制条件的排列问题常见命题形式: “在”与“不在” “邻”与“不邻” 在解决问题时要掌握基本的解题思想和方法: ⑴“相邻”问题在解题时常用“合并元素法” ,可把两个以上的元素当做一个元素来看,这是处理相邻最 常用的方法. ⑵“不邻”问题在解题时最常用的是“插空排列法”. ⑶“在”与“不在”问题,常常涉及特殊元素或特殊位置,通常是先排列特殊元素或特殊位置. ⑷元素有顺序限制的排列,可以先不考虑顺序限制,等排列完毕后,利用规定顺序的实情求出结果. 2.有限制条件的组合问题,常见的命题形式: “含”与“不含” “至少”与“至多” 在解题时常用的方法有“直接法”或“间接法”. 3. 在处理排列、组合综合题时,通过分析条件按元素的性质分类,做到不重、不漏,按事件的发生过 程分步,正确地交替使用两个原理,这是解决排列、组合问题的最基本的,也是最重要的思想方法. ***************************************************************************** 提供 10 道习题供大家练习 1、三边长均为整数,且最大边长为 11 的三角形的个数为( C ) (A)25 个 (B)26 个 (C)36 个 (D)37 个 -----------------------------------------------------【解析】 根据三角形边的原理 两边之和大于第三边,两边之差小于第三边 可见最大的边是 11 则两外两边之和不能超过 22 因为当三边都为 11 时 是两边之和最大的时候 因此我们以一条边的长度开始分析 如果为 11,则另外一个边的长度是 11,10,9,8,7,6, 。 。 。 。 。 。1 如果为 10 则另外一个边的长度是 10,9,8。 。 。 。 。 。2, (不能为 1 否则两者之和会小于 11,不能为 11,因为第一种情况包含了 11,10 的组合) 如果为 9 则另外一个边的长度是 9,8,7, 。 。 。 。 。 。 。3 (理由同上 ,可见规律出现) 规律出现 总数是 11+9+7+。 。 。 。1=(1+11)×6÷2=36 2、 (1)将 4 封信投入 3 个邮筒,有多少种不同的投法? -----------------------------------------------------------【解析】 每封信都有 3 个选择。信与信之间是分步关系。比如说我先放第 1 封信,有 3 种可能性。接着 再放第 2 封,也有 3 种可能性,直到第 4 封, 所以分步属于乘法原则 即 3×3×3×3=3^4 (2)3 位旅客,到 4 个旅馆住宿,有多少种不同的住宿方法? ------------------------------------------------------------【解析】跟上述情况类似 对于每个旅客我们都有 4 种选择。彼此之间选择没有关系 不够成分类关系。 属于分步关系。如:我们先安排第一个旅客是 4 种,再安排第 2 个旅客是 4 种选择。知道最后一个旅客 也是 4 种可能。根据分步原则属于乘法关系 即 4×4×4=4^3 (3)8 本不同的书,任选 3 本分给 3 个同学,每人一本,有多少种不同的分法? -------------------------------------------------------------

2

Name_________ Grade__________ Date__________

优胜教育东直门校区

【解析】分步来做 第一步:我们先选出 3 本书 即多少种可能性 C8 取 3=56 种 第二步:分配给 3 个同学。 P33=6 种 这 里稍微介绍一下为什么是 P33 ,我们来看第一个同学可以有 3 种书选择,选择完成后,第 2 个同学就 只剩下 2 种选择的情况,最后一个同学没有选择。即 3×2×1 这是分步选择符合乘法原则。最常见的例 子就是 1,2,3,4 四个数字可以组成多少 4 位数? 也是满足这样的分步原则。 用 P 来计算是因为每个 步骤之间有约束作用 即下一步的选择受到上一步的压缩。 所以该题结果是 56×6=336 3、 七个同学排成一横排照相. (1)某甲不站在排头也不能在排尾的不同排法有多少种? (3600) --------------------------------------------【解析】 这个题目我们分 2 步完成 第一步: 先给甲排 应该排在中间的 5 个位置中的一个 即 C5 取 1=5 第二步: 剩下的 6 个人即满足 P 原则 P66=720 所以 总数是 720×5=3600 (2)某乙只能在排头或排尾的不同排法有多少种? (1440) ------------------------------------------------【解析】 第一步:确定乙在哪个位置 排头排尾选其一 C2 取 1=2 第二步:剩下的 6 个人满足 P 原则 P66=720 则总数是 720×2=1440 (3)甲不在排头或排尾,同时乙不在中间的不同排法有多少种? (3120) --------------------------------------------------【解析】特殊情况先安排特殊 第一种情况:甲不在排头排尾 并且不在中间的情况 去除 3 个位置 剩下 4 个位置供甲选择 C4 取 1=4, 剩下 6 个位置 先安中间位置 即除了甲乙 2 人,其 他 5 人都可以 即以 5 开始,剩下的 5 个位置满足 P 原则 即 5×P55=5×120=600 总数是 4×600=2400 第 2 种情况:甲不在排头排尾, 甲排在中间位置 则 剩下的 6 个位置满足 P66=720 因为是分类讨论。所以最后的结果是两种情况之和 即 2400+720=3120 (4)甲、乙必须相邻的排法有多少种? (1440) ----------------------------------------------【解析】相邻用捆绑原则 2 人变一人,7 个位置变成 6 个位置,即分步讨论 第 1: 选位置 C6 取 1=6 第 2: 选出来的 2 个位置对甲乙在排 即 P22=2 则安排甲乙符合情况的种数是 2×6=12 剩下的 5 个人即满足 P55 的规律=120 则 最后结果是 120×12=1440 (5)甲必须在乙的左边(不一定相邻)的不同排法有多少种?(2520) ------------------------------------------------------【解析】 这个题目非常好,无论怎么安排甲出现在乙的左边 和出现在乙的右边的概率是一样的。 所以我们不考虑 左右问题 则总数是 P77=5040 ,根据左右概率相等的原则 则排在左边的情况种数是 5040÷2=2520 4、用数字 0,1,2,3,4,5 组成没有重复数字的数. (1)能组成多少个四位数? (300)
3

-------------------------------------------------------【解析】 四位数 从高位开始到低位 高位特殊 不能排 0。 则只有 5 种可能性 接下来 3 个位置满足 P53 原则=5×4×3=60 即总数是 60×5=300 (2)能组成多少个自然数? (1631) --------------------------------------------------------【解析】自然数是从个位数开始所有情况 分情况 1 位数: C6 取 1=6 2 位数: C5 取 2×P22+C5 取 1×P11=25 3 位数: C5 取 3×P33+C5 取 2×P22×2=100 4 位数: C5 取 4×P44+C5 取 3×P33×3=300 5 位数: C5 取 5×P55+C5 取 4×P44×4=600 6 位数: 5×P55=5×120=600 总数是 1631 这里解释一下计算方式 比如说 2 位数: C5 取 2×P22+C5 取 1×P11=25 先从不是 0 的 5 个数字中取 2 个排列 即 C5 取 2×P22 还有一种情况是从不是 0 的 5 个数字中选一个和 0 搭配成 2 位数 即 C5 取 1×P11 因为 0 不能作为最高位 所以最高位只有 1 种可能 (3)能组成多少个六位奇数? (288) --------------------------------------------------【解析】高位不能为 0 个位为奇数 1,3,5 则 先考虑低位,再考虑高位 即 3×4×P44=12×24=288 (4)能组成多少个能被 25 整除的四位数? (21) ---------------------------------------------------【解析】 能被 25 整除的 4 位数有 2 种可能 后 2 位是 25: 3×3=9 后 2 位是 50: P42=4×3=12 共计 9+12=21 (5)能组成多少个比 201345 大的数? (479) -----------------------------------------------【解析】 从数字 201345 这个 6 位数看 是最高位为 2 的最小 6 位数 所以我们看最高位大 的 6 位数是多少? 4×P55=4×120=480 去掉 201345 这个数 即比 201345 大的有 480-1=479 (6)求所有组成三位数的总和. (32640) --------------------------------------------【解析】每个位置都来分析一下 百位上的和:M1=100×P52(5+4+3+2+1) 十位上的和:M2=4×4×10(5+4+3+2+1) 个位上的和:M3=4×4(5+4+3+2+1) 总和 M=M1+M2+M3=32640

于等于 2

5、生产某种产品 100 件,其中有 2 件是次品,现在抽取 5 件进行检查. (1) “其中恰有两件次品”的抽法有多少种? (152096) 【解析】 也就是说被抽查的 5 件中有 3 件合格的 ,即是从 98 件合格的取出来的 所以 即 C2 取 2×C98 取 3=152096

4

Name_________ Grade__________ Date__________

优胜教育东直门校区

(2) “其中恰有一件次品”的抽法有多少种? (7224560) 【解析】同上述分析,先从 2 件次品中挑 1 个次品,再从 98 件合格的产品中挑 4 个 C2 取 1×C98 取 4=7224560 (3) “其中没有次品”的抽法有多少种? (67910864) 【解析】则即在 98 个合格的中抽取 5 个 C98 取 5=67910864 (4) “其中至少有一件次品”的抽法有多少种? (7376656) 【解析】全部排列 然后去掉没有次品的排列情况 就是至少有 1 种的 C100 取 5-C98 取 5=7376656 (5) “其中至多有一件次品”的抽法有多少种? (75135424) 【解析】所有的排列情况中去掉有 2 件次品的情况即是至多一件次品情况的 C100 取 5-C98 取 3=75135424 6、从 4 台甲型和 5 台乙型电视机中任意取出 3 台,其中至少要有甲型和乙型电视机各 1 台,则不同的取 法共有( ) (A)140 种 (B)84 种 (C)70 种 (D)35 种 -------------------------------------------------------【解析】根据条件我们可以分 2 种情况 第一种情况:2 台甲+1 台乙 即 C4 取 2×C5 取 1=6×5=30 第二种情况:1 台甲+2 台乙 即 C4 取 1×C5 取 2=4×10=40 所以总数是 30+40=70 种 7、在 50 件产品中有 4 件是次品,从中任抽 5 件,至少有 3 件是次品的抽法有__种. ------------------------------------------------------【解析】至少有 3 件 则说明是 3 件或 4 件 3 件:C4 取 3×C46 取 2=4140 4 件:C4 取 4×C46 取 1=46 共计是 4140+46=4186 8、 有甲、 乙、 丙三项任务, 甲需 2 人承担, 乙、 丙各需 1 人承担.从 10 人中选派 4 人承担这三项任务, 不 同的选法共有( C ) (A)1260 种 (B)2025 种 (C)2520 种 (D)5040 种 --------------------------- 【解析】分步完成 第一步:先从 10 人中挑选 4 人的方法有:C10 取 4=210 第二步:分配给甲乙并的工作是 C4 取 2×C2 取 1×C1 取 1=6×2×1=12 种情况 则根据分步原则 乘法关系 210×12=2520

9、12 名同学分别到三个不同的路口进行车流量的调查,若每个路口 4 人,则不同的分配方案共有_____ 种 C(4,12)C(4,8)C(4,4) ------------------------ 【解析】每个路口都按次序考虑 第一个路口是 C12 取 4
5

第二个路口是 C8 取 4 第三个路口是 C4 取 4 则结果是 C12 取 4×C8 取 4×C4 取 4 可能到了这里有人会说 三条不同的路不是需要 P33 吗 其实不是这样的 在我们从 12 人中任意抽取人数 的时候,其实将这些分类情况已经包含了对不同路的情况的包含。 如果再×P33 则是重复考虑了 如果这里不考虑路口的不同 即都是相同路口 则情况又不一样 因为我们在分配人数的时候考虑了路口 的不同。所以最后要去除这种可能情况 所以在上述结果的情况下要÷P33 10、在一张节目表中原有 8 个节目,若保持原有节目的相对顺序不变,再增加三个节目,求共有多少种 安排方法? 990 ------------------------ 【解析】 这是排列组合的一种方法 叫做 2 次插空法 直接解答较为麻烦, 故可先用一个节目去插 9 个空位, 有 P(9,1)种方法; 再用另一个节目去插 10 个空位, 有 P(10,1)种方法;用最后一个节目去插 11 个空位,有 P(11,1)方法,由乘法原理得:所有不同的添加 方法为 P(9,1)×P(10,1)×P(11,1)=990 种。 另解:先在 11 个位置中排上新添的三个节目有 P(11,3)种,再在余下的 8 个位置补上原有的 8 个节目, 只有一解,所以所有方法有 P311×1=990 种。 解决排列组合问题的策略 1 、逆向思维法:我们知道排列组合都是对一个元素集合进行筛选排序。我们可以把这个集合看成 数学上的单位 1 ,那么 1 = a + b 就是我们构建逆向思维的数学模型了, 当 a 不利于我们运算求 解的时候,我们不妨从 b 的角度出发思考,这样同样可以求出 a = 1 - b 。 例题: 7 个人排座,甲坐在乙的左边(不一定相邻)的情况有多少种? 例题:一个正方体有 8 个顶点 我们任意选出 4 个,有多少种情况是这 4 个点可以构成四面体的。 例题:用 0,2,3,4,5 这五个数字,组成没有重复数字的三位数,其中偶数共有( ) A.24 个 B.30 个 C.40 个 D.60 个 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 、解含有约束条件的排列组合问题一――采用合理分类与准确分步的策略 例题:平面上 4 条平行直线与另外 5 条平行直线互相垂直,则它们构成的矩形共有________个。

6

Name_________ Grade__________ Date__________

优胜教育东直门校区

简析:按构成矩形的过程可分为如下两步:第一步.先在 4 条平行线中任取两条,有 C4 取 2 种取法;第 二步再在 5 条平行线中任取两条,有 C5 取 2 种取法。这样取出的四条直线构成一个矩形,据乘法原理, 构成的矩形共有 6×10=60 个 4、解排列组台混合问题——采用先选后排策略 对于排列与组合的混合问题,可采取先选出元素,后进行排列的策略。 例:4 个不同小球放入编号为 1、2、3、4 的四个盒子,则恰有一个空盒的放法有___种。144 5、插板法 插板法的条件构成: 1 元素相同,2 分组不同,3 必须至少分得 1 个 插板法的类型: (1) 、10 块奶糖分给 4 个小朋友,每个小朋友至少 1 块,则有多少种分法?(典型插板法 点评略) (2) 、10 块奶糖分给 4 个小朋友有多少种方法?(凑数插板法: 这个题目对照插板法的 3 个条件我们发 现 至少满足 1 个这个条件没有, 所以我们必须使其满足,最好的方法 就是用 14 块奶糖来分,至少每 人 1 块 ,当每个人都分得 1 块之后,剩下的 10 块就可以随便分了,就回归到了原题) (3) 、10 块奶糖放到编号为 1,2,3 的 3 个盒子里,每个盒子的糖数量不少于其编号数,则有几种方法? (定制插板法: 已然是最后一个条件不满足,我们该怎么处理呢,应该学会先去安排 使得每个盒子都 差 1 个, 这样就保证每个盒子必须分得 1 个, 从这个思路出发, 跟第二个例题是姊妹题 思路是一样的 对 照条件 想办法使其和条件吻合! ) (4) 、8 块奶糖和另外 3 个不同品牌的水果糖要放到编号为 1~11 的盒子里面,每个盒子至少放 1 个,有 多少种方法?(多次插空法 这里不多讲,见我排列组合基础讲义) 6、递归法(枚举法) 公考也有这样的类型, 排错信封问题,还有一些邮票问题 归纳法: 例如:5 封信一一对应 5 个信封,其中有 3 个封信装错信封的情况有多少种? 枚举法: 例如:10 张相同的邮票 分别装到 4 个相同的信封里面,每个信封至少 1 张邮票,有多少种方法? 枚举: 1,1,1,7 1,1,2,6 1,1,3,5 1,1,4,4 1,2,2,5 1,2,3,4 1,3,3,3 2,2,2,4 2,2,3,3 9 种方法! 疑难问题 1、如何验证重复问题 2、关于位置与元素的相同问题,
7

例如: 6 个人平均分配给 3 个不同的班级,跟 6 个学生平分成 3 组的区别 3、关于排列组合里面,充分运用对称原理。 例题: 1,2,3,4,5 五个数字可以组成多少个十位数小于个位数的四位数? 例题:7 个人排成一排,其中甲在乙右边(可以不相邻)的情况有多少种? 注解:分析 2 种对立情况的概率,即可很容易求解。 当对立情况的概率相等,即对称原理。 4、环形排列和线性排列问题。 (见我的基础排列组合讲义二习题讲解) 例如:3 个女生和 4 个男生围坐在一个圆桌旁。 问有多少种方法? 例如:3 对夫妇围坐在圆桌旁,男女间隔的坐法有多少种? 注解:排列组合中,特殊的地方在于,第一个坐下来的人是作为参照物,所以不纳入排列的范畴,我们 知道,环形排列中 每个位置都是相对的位置,没有绝对位置,所以需要有一个人坐下来作为参照位置。 5、几何问题:见下面部分的内容。 例析立体几何中的排列组合问题 在数学中,排列、组合无论从内容上还是从思想方法上,都体现了实际应用的观点。 1 点 1.1 共面的点 例题: 四面体的一个顶点为 A,从其它顶点与棱的中点中取 3 个点,使它们和点 A 在同一平面上,不同 的取法有( ) A.30 种 B.33 种 C.36 种 D.39 种 答案:B 点评:此题主要考查组合的知识和空间相像能力;属难度中等的选择题,失误的主要原因是没有把每条 棱上的 3 点与它对棱上的中点共面的情况计算在内。 1.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,

8

Name_________ Grade__________ Date__________

优胜教育东直门校区

所得的经过坐标原点原直线共有____条(结果用数值来表示). 解:因为直线过原点,所以 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 点在同一直线 上有 3 个,故符合条件的三角形共有 35-3=32 个. 四 转化法求解 例 6 空间六个点,它们任何三点不共线,任何四点不共面,则过每两点的直线中有多少对异面直线? 解:考虑到每一个三棱锥对应着 3 对异面直线,问题就转化为能构成多少个三棱锥. 由于这六个点可构 成 C(6,4)=15 个三棱锥,故共有 3×15 =45 对异面直线. 例 7 一个圆的圆周上有 10 个点,每两个点连接一条弦,求这些弦在圆内的交点个数最多有几个? 解:考虑到每个凸四边形的两条对角线对应一个交点,则问题可转化为构成凸四边形的个数.显然可构 成 C(10,4)=210 个圆内接四边形,故 10 个点连成的点最多能在圆中交点 210 个. 6、染色问题: 不涉及环形染色 可以采用特殊区域优先处理的方法来分步解决。 环形染色可采用如下公式解决: An=(a-1)^n+(a-1)×(-1)^n n 表示被划分的个数,a 表示颜色种类 原则:被染色部分编号,并按编号顺序进行染色,根据情况分类 在所有被染色的区域,区分特殊和一般,特殊区域优先处理 例题 1:将 3 种作物种植在如图 4 所示的 5 块试验田里,每块种植一种作物,且相邻的试验田不能种同一 种作物。则有多少种种植方法?

图1 例题 2:用 5 种不同颜色为图中 ABCDE 五个部分染色,相邻部分不能同色,但同一种颜色可以反复使用, 也可以不使用,则符合要求的不同染色方法有多少种?

图2
9

例题 3:将一个四棱锥的五个顶点染色,使同一条棱的 2 个端点不同色,且只由五个颜色可以使用,有多 少种染色方法?

图3 例题 4:一个地区分为如图 4 所示的五个行政区域,现在有 4 种颜色可供选择,给地图着色,要求相邻区 域不同色,那么则有多少种染色方法?

图4 例题 5:某城市中心广场建造了一个花圃,分 6 个部分(如图 5) 现在要栽种 4 种不同的颜色的花,每 部分栽种一种且相邻部分不能种同样颜色的花,则有多少种不同栽种方式?

图 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 次序,则排列数 有______种。 [解析]
10

Name_________ Grade__________ Date__________

优胜教育东直门校区

这个题目就是直线全排列出现相同元素的问题:在我的另外一个帖子里面有介绍:http://bbs.qzzn.com/ read-htm-tid-9487547.html (1)我们首先把相同元素找出来,B 有 2 个, I 有 2 个 我们先看作都是不同的 11 个元素全排列 这样就简 单的多是 P11,11 然后把相同的元素能够形成的排列剔除即可 P11/(P2,2*P2,2)=9979200。 (2)第 2 个小问题 因要保持 PRO 的顺序,就将 PRO 视为相同元素(跟 B,I 类似的性质) ,则其排列数有 1 1!/(2!×2!×3! )= 166320 种。

(三) 李先生与其太太有一天邀请邻家四对夫妇共 10 人围坐一圆桌聊天,试求下列各情形之排列数:

(1)男女间隔而坐。 (2)主人夫妇相对而坐。 (3)每对夫妇相对而坐。 (4)男女间隔且夫妇相邻。 (5)夫妇相邻。 (6)男的坐在一起,女的坐在一起。 [解析] (1) 这个问题也在 http://bbs.qzzn.com/read-htm-tid-9487547.html 介绍过 先简单介绍一下环形排列的特征,环形排列相对于直线排列缺少的就是参照物.第一个坐下来的人是没有 参照物的,所以无论做哪个位置都是一样的. 所以从这里我们就可以看出 环形排列的特征是 第一个人 是做参照物,不参与排列. 下面就来解答 6 个小问题: (1)先让 5 个男的或 5 个女的先坐下来 全排列应该是 P44, 空出来的位置他们的妻子(丈夫), 妻子(丈 夫)的全排列这个时候有了参照物所以排列是 P55 答案就是 P44*P55=2880 种

(2)先让主人夫妇找一组相对座位入座 其排列就是 P11(记住不是 P22 ),这个时候其他 8 个人再入座,就 是 P88,所以此题答案是 P88

(3)每对夫妇相对而坐,就是捆绑的问题 .5 组相对位置有一组位置是作为参照位置给第一个入座的夫妇 的,剩下的 4 组位置就是 P44, 考虑到剩下来的 4 组位置夫妇可以互换位置即 P44*2^4=384

11

(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 个节目,若保持原有节目的相对顺序不变,再增加三个节目,求共有多少 种安排方法? [解析] 这个题目相信大家都见过 就是我们这次 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 或者 5 0,或者 75 或者 00 方可. 后两位是 25 的情况有:千位只有 3 个数字可选(0 不能) 百位也是 3 个可选 即 3*3=9 种

12

Name_________ Grade__________ Date__________

优胜教育东直门校区

后两位是 50 的情况有:剩下的 4 个数字进行选 2 位排列 P4,2=12 种 75 不可能,因为数字中没有 7 00 也不可能,因为数字不能重复 共计 9+12=21 种

2. “插板法”的条件模式隐藏运用分析
在说这 2 道关于“插板法”的排列组合题目之前,我们需要弄懂一个问题: 插板法排列组合是需要什么条件下才可以使用?这个问题清楚了, 我们在以后的答题中 就可以尽量的变 化题目使其满足这个条件。 这个条件就是: 分组或者分班等等 至少分得一个元素。 好我们先来看题目, 例题 1:某学校四、五、六三个年级组织了一场文艺演出,共演出 18 个节目,如果每个年级至少演出 4 个节目,那么这三个年级演出节目数的所有不同情况共有几种? 【解析】 这个题目是 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 的盒子是满足的 至少需要 1 个,

13

编号 2 至少需要 2 个,那么我们先给它 1 个, 这样就差 1 个 编号 3 至少需要 3 个,那么我们先给它 2 个, 这样就差 1 个 现在三个盒子都满足插板法的要求了 我们看还剩下几个小球 ? 10-1-2=7 7 个小球 6 个间隔 再按照插板法来做 C6,2=15 种!

3. 【纠错】两个相同的正方体的六个面上分别标有数字的排列组合问题
有两个相同的正方体,每个正方体的六个面上分别标有数字 1、2、3、4、5、6。将两个正方体放到桌面 上,向上的一面数字之和为偶数的有多少种情形?( ) A.9 B.12 C.18 D.24 -------------------------- 很多教材给出的答案是 18 这里我更正以下:

请大家注意红色字体 “相同” 如果一个显示 3,一个显示 1, 交换以下 是 1,3 是否是 2 种呢? 显然不是 是 1 种 这是这个题目存在的陷阱
------------------ 方法一: 为偶数的情形 分 2 种情况 (1)、奇数+奇数:(1,3,5) C(3,1)×C(3,1)注意因为这里是相同的两个色子。所以 3,1 和 1,3 是不区分的 要去掉 C3,2= 3 种 实际上是 6 种, (2)、偶数+偶数(2,4,6) 偶数的情况跟奇数相同 也是 6 种! 答案是 6+6=12 方法二:当然我们也可以算总的, 那么就是 C6,1×C6,1-C6,2=36-15=21 种 (为什么要减去 C(6,2 ), 因为任意 2 个数字颠倒都是一种情况) 看奇数: 奇数=奇数+偶数 C3,1×C3,1=9 种 所以答案是 21-9=12 种

4. 【讨论】裴波纳契数列的另类运用

14

Name_________ Grade__________ Date__________

优胜教育东直门校区

先说典型的裴波纳契数列: 图片:

裴波纳契数列 就是移动求和 A+B=C 因为第一个月这对小兔长成大兔 所以第一个月还是 1 对 即 A 从 1 开始。第 2 个月开始剩下一对小兔 合计 2 对 B 从 2 开始。 1,2,3,5,8,13,21,34,55,89,144,233 小明家住二层,他每次回家上楼梯时都是一步迈两级或三级台阶。已知相邻楼层之间有 16 级台阶,那么 小明从一层到二层共有多少种不同的走法? A:54 B:64 C:57 D:37

------------------- 这个题目刚刚看到讨论 我也用排列组合的办法参与了讨论 现在我再来说说裴波纳契数列的解法 楼梯级数:1,2,3,4,5,6........ 走法情况:0,1,1,1,2,2........ 这是一个裴波纳契的间隔运用 因为他没有走 1 步的情况

即 A+B=D
0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37

在举例 1 题:小明家住二层,他每次回家上楼梯时都是一步迈一级,两级或三级台阶。已知相邻楼层之 间有 10 级台阶,那么小明从一层到二层共有多少种不同的走法? 因为是 1,2,3 级都可以所以可以采用 A+B+C=D 的 裴波纳契数列变式! 列举前 3 个 分别是 1,2,3 则 10 个是 1,2,4,7,13,24,44,81,149,274

练习题目:小明家住二层,他每次回家上楼梯时都是一步迈一级或三级台阶。已知相邻楼层之间有 10 级 台阶,那么小明从一层到二层共有多少种不同的走法?

15

排列与组合习题
1.6 个人分乘两辆不同的汽车,每辆车最多坐 4 人,则不同的乘车方法数为( A.40 B.50 C.60 D.70 ) )

2.有 6 个座位连成一排,现有 3 人就坐,则恰有两个空座位相邻的不同坐法有( A.36 种 B.48 种 C.72 种 D.96 种

3.只用 1,2,3 三个数字组成一个四位数,规定这三个数必须同时使用,且同一数字不能相邻出现,这样 的四位数有( A.6 个 ) B .9 个 C.18 个 D.36 个 )

4. 男女学生共有 8 人, 从男生中选取 2 人, 从女生中选取 1 人, 共有 30 种不同的选法, 其中女生有( A.2 人或 3 人 B.3 人或 4 人 C.3 人 D.4 人

5.某幢楼从二楼到三楼的楼梯共 10 级,上楼可以一步上一级,也可以一步上两级,若规定从二楼到三 楼用 8 步走完,则方法有( A.45 种 ) C.28 种 D.25 种

B.36 种

6.某公司招聘来 8 名员工,平均分配给下属的甲、乙两个部门,其中两名英语翻译人员不能分在同一 个部门,另外三名电脑编程人员也不能全分在同一个部门,则不同的分配方案共有( )

7.已知集合 A={5},B={1,2},C={1,3,4},从这三个集合中各取一个元素构成空间直角坐标系中点的 坐标,则确定的不同点的个数为( A.33 B.34 ) C.35 D.36 )

8.由 1、2、3、4、5、6 组成没有重复数字且 1、3 都不与 5 相邻的六位偶数的个数是( A.72 B.96 C.108 D.144

9.如果在一周内(周一至周日)安排三所学校的学生参观某展览馆,每天最多只安排一所学校,要求甲学 校连续参观两天,其余学校均只参观一天,那么不同的安排方法有( A.50 种 B.60 种 C.120 种 D.210 种 )

10.安排 7 位工作人员在 5 月 1 日到 5 月 7 日值班,每人值班一天,其中甲、乙二人都不能安排在 5 月 1 日和 2 日,不同的安排方法共有________种.(用数字作答) 11.今有 2 个红球、3 个黄球、4 个白球,同色球不加以区分,将这 9 个球排成一列有________种不同 的排法.(用数字作答) 12.将 6 位志愿者分成 4 组,其中两个组各 2 人,另两个组各 1 人,分赴世博会的四个不同场馆服务, 不同的分配方案有________种(用数字作答). 13.要在如图所示的花圃中的 5 个区域中种入 4 种颜色不同的花,要求相邻区域 不同色,有________种不同的种法(用数字作答). 14. 将标号为 1,2,3,4,5,6 的 6 张卡片放入 3 个不同的信封中.若每个信封 放 2 张,其中标号为 1,2 的卡片放入同一信封,则不同的方法共有 (A)12 种 (B)18 种 (C)36 种 (D)54 种 15. 某单位安排 7 位员工在 10 月 1 日至 7 日值班,每天 1 人,每人值班 1 天,若 7 位员工中的甲、乙排
16

Name_________ Grade__________ Date__________

优胜教育东直门校区

在相邻两天,丙不排在 10 月 1 日,丁不排在 10 月 7 日,则不同的安排方案共有 A. 504 种 B. 960 种 C. 1008 种 D. 1108 种 16. 由 1、2、3、4、5、6 组成没有重复数字且 1、3 都不与 5 相邻的六位偶数的个数是 (A)72 (B)96 (C) 108 (D)144 17. 在某种信息传输过程中,用 4 个数字的一个排列(数字允许重复)表示一个信息,不同排列表示不同 信息,若所用数字只有 0 和 1,则与信息 0110 至多有两个对应位置上的数字相同的信息个数为 A.10 B.11 C.12 D.15 18. 现安排甲、乙、丙、丁、戌 5 名同学参加上海世博会志愿者服务活动,每人从事翻译、导游、礼仪、 司机四项工作之一,每项工作至少有一人参加。甲、乙不会开车但能从事其他三项工作,丙丁戌都能胜 任四项工作,则不同安排方案的种数是 A.152 B.126 C.90 D.54
w_w_w.k*s 5*u.c o*m

19. 甲组有 5 名男同学,3 名女同学;乙组有 6 名男同学、2 名女同学。若从甲、乙两组中各选出 2 名同 学,则选出的 4 人中恰有 1 名女同学的不同选法共有( D ) (A)150 种 (B)180 种 (C)300 种 (D)345 种 20. 将甲、乙、丙、丁四名学生分到三个不同的班,每个班至少分到一名学生,且甲、乙两名学生不能分 到同一个班,则不同分法的种数为

A.18

B.24

C .30

D.36

21. 2 位男生和 3 位女生共 5 位同学站成一排,若男生甲不站两端,3 位女生中有且只有两位女生相邻, 则不同排法的种数是 A. 60 B. 48 C. 42 D. 36 22. 从 10 名大学生毕业生中选 3 个人担任村长助理,则甲、乙至少有 1 人入选,而丙没有入选的不同选 法的种数位 [ C] A 85 B 56 C 49 D 28

23. 3 位男生和 3 位女生共 6 位同学站成一排,若男生甲不站两端,3 位女生中有且只有两位女生相邻, 则不同排法的种数是 A. 360 B. 188 C. 216 D. 96

17


相关文章:
高中排列组合知识点汇总及典型例题(全)
[解析] 本题考查排列组合的综合应用,据题意可先将两名翻译人员分到两个部门,共有 2 种方法,第二步将 3 名电脑编程人员分成两组,一组 1 1 2 1 人另一...
排列组合的二十种解法(最全的排列组合方法总结)
10 的传球方式有___ 对于条件比较复杂的排列组合问题,不易用 公式进行运算,树图会收到意想不到的结果 练习: 分别编有 1,2,3,4,5 号码的人与椅,其中 ...
高中数学排列组合相关公式
排列组合公式——熊雄 排列定义:从 n 个不同的元素中,取 r 个不重复的元素,按次序排列,称为从 n 个中取 r 个的无重排列。排列的全体组成的集合用 P(n,...
排列组合基本概念
排列组合基本概念 两个基本原理 1.加法原理:做一件事,完成它可以有 n 类办法,在第一类办法中 加法原理: 类办法, 加法原理 做一件事, 种不同的方法, 种不...
排列组合和排列组合计算公式
排列组合排列组合计算公式_公务员考试_资格考试/认证_教育专区。公考重涉及到的排列组合计算公式及真题。排列组合公式/排列组合计算公式 排列 P---和顺序有关 组...
排列组合基础知识
排列组合基础知识_高三数学_数学_高中教育_教育专区。介绍加法原理、乘法原理、排列及组合的相关基础知识。排列组合基础知识 一、两大原理 1.加法原理 (1)定义:做...
排列组合
我们能得到一个组合的原则, 【同类的元素只能写在一个组合数里】,c21 和 c 99 2 里都含有次品这一类元素,违背了 这一原则所以是错误的对于排列组合的问题大家...
排列组合基础知识及解题技巧
排列组合基础知识及解题技巧_高三数学_数学_高中教育_教育专区。排列组合基础知识及习题分析 在介绍排列组合方法之前 我们先来了解一下基本的运算公式! 3 C5 =(5...
排列组合典型例题
排列组合典型例题_数学_高中教育_教育专区。典型例题一例 1 用 0 到 9 这 10 个数字.可组成多少个没有重复数字的四位偶数? 解法 1:当个位数上排“0”时,...
更多相关标签:
排列组合公式 | 排列组合算法 | 排列组合公式c | 关键词排列组合 | 排列组合计算器 | 排列 | 排列组合计算公式 | 排列数公式 |