排列组合综合应用问题.ppt

排列组合综合应用题 引入 前面我们已经学习和掌握了排列组合问题的求解方法 下面我们要在复习 巩固已掌握的方法的基础上 学习和讨论排列 组合的综合问题 和应用问题 问题 解决排列组合问题一般有哪些方法 应注意什么问题 解排列组合问题时 当问题分成互斥各类时 根据加法原理 可用分类法 当问题考虑先后次序时 根据乘法原理 可用特殊位置法 特殊元素法 上述两种称 直接法 当问题的反面简单明了时 可通过求差排除法 采用 间接法 另外 排列中 相邻 问题可采用捆绑法 分离 问题可用插空法 定序问题倍缩法等 解排列组合问题 一定要做到 不重 不漏 分为三组 一组5人 一组4人 一组3人 分为甲 乙 丙三组 甲组5人 乙组4人 丙组3人 分为甲 乙 丙三组 一组5人 一组4人 一组3人 分为甲 乙 丙三组 每组4人 分为三组 每组4人 例1 有12人 按照下列要求分配 求不同的分法种数 C125 C74 C33 C125 C74 C33 C125 C74 C33 A33 C124 C84 C44 分成三组 其中一组2人 另外两组都是5人 一 分配问题 小结 练习1说明了非平均分配 平均分配以及部分平均分配问题 1 非平均分配问题中 没有给出组名与给出组名是一样的 可以直接分步求 给出了组名而没指明哪组是几个 可以在没有给出组名 或给出组名但不指明各组多少个 种数的基础上乘以组数的全排列数 2 平均分配问题中 给出组名的分步求 若没给出组名的 一定要在给出组名的基础上除以组数的全排列数 3 部分平均分配问题中 先考虑不平均分配 剩下的就是平均分配 这样分配问题就解决了 结论 给出组名 非平均中未指明各组个数 的要在未给出组名的种数的基础上 乘以组数的阶乘 例2 某乒乓球队有8男7女共15名队员 现进行混合双打训练 两边都必须要1男1女 共有多少种不同的搭配方法 分析 每一种搭配都需要2男2女 所以先要选出2男2女 有C82 C72种 然后考虑2男2女搭配 先排男队员 再排女队员 所以总的搭配方法有种 二 搭配问题 先组后排 例3 高一要从全年级10名独唱选手中选出6名在歌咏会上表演 出场安排甲 乙两人都不唱中间两位的安排方法有多少种 三 有条件限制的排列问题 例4 已知集合A 1 2 3 4 5 6 7 8 9 求含有5个元素 且其中至少有两个是偶数的子集的个数 四 有条件限制的组合问题 解法1 5个元素中至少有两个是偶数可分成三类 2个偶数 3个奇数 3个偶数 2个奇数 4个偶数 1个奇数 所以共有子集个数为C42 C53 C43 C52 C44 C51 105 解法2 从反面考虑 全部子集个数为C95 而不符合条件的有两类 5个都是奇数 4个奇数 1个偶数 所以共有子集个数为C95 C55 C54 C41 105 下面解法错在哪里 例4 已知集合A 1 2 3 4 5 6 7 8 9 求含有5个元素 且其中至少有两个是偶数的子集的个数 至少有两个偶数 可先由4个偶数中取2个偶数 然后再由剩下的7个数中选3个组成5个元素集合且满足至少有2个是偶数 成以共有子集C42 C73 210 个 用 具体排 来看一看是否重复 如C42中的一种选法是 选4个偶数中的2 4 又C73中选剩下的3个元素不6 1 3组成集合 2 4 6 1 3 再看另一种选法 由C42中选4个偶数中的4 6 又C73中选剩下的3个元素选2 1 3组成集合 4 6 2 1 3 显然这是两个相同和子集 所以重复了 重复的原因是分类不独立 五 排列组合混合问题 例5 从6名男同学和4名女同学中 选出3名男同学和2名女同学分别承担A B C D E5项工作 一共有多少种分配方案 解1 分三步完成 1 选3名男同学有C63种 2 选2名女同学有C42种 3 对选出的5人分配5种不同的工作有A55种 根据乘法原理C63 C42 A55 14400 种 解2 把工作当作元素 同学看作位置 1 从5种工作中任选3种 组合问题 分给6个男同学中的3人 排列问题 有C53 A63种 第二步 将余下的2个工作分给4个女同学中的2人有A42种 根据乘法原理共有C53 A63 A42 14400 种 亦可先分配给女同学工作 再给男同学分配工作 分配方案有C52 A42 A63 14400 种 例6 九张卡片分别写着数字0 1 2 8 从中取出三张排成一排组成一个三位数 如果6可以当作9使用 问可以组成多少个三位数 解 可以分为两类情况 若取出6 则有种方法 若不取6 则有种方法 根据分类计数原理 一共有 602种方法 六 化归策略例7 25人排成5 5方阵 现从中选3人 要求3人不在同一行也不在同一列 不同的选法有多少种 变式7 某城市的街区由12个全等的矩形区组成其中实线表示马路 从A走到B的最短路径有多少种 七 错位排列 例9 编号为1至6的6个小球放入编号为1至6的6个盒子里 每个盒子放一个小球 其中恰有2个小球与盒子的编号相同的放法有 种 解 选取编号相同的两组球和盒子的方法有 种 其余4组球与盒子需错位排列有9种放法 故所求方法有15 9 135种 练习1 4位同学各写了一张明信片 然后统一收齐放到盒子里 每位同学再去抽取一张 问他们均不拿到自己的有多少种拿法 练习2用三种不同的颜色填涂如图3 3方格中的9个区域 要求每行每列的三个区域都不同颜色 则不同的填涂方法有多少种 解 第一行的涂法种数是 第二行的涂法相当于三个元素的错位排列 涂法种数是 2 第三行只有1种涂法 共有种 八 分类组合 隔板处理 例10 从6个学校中选出30名学生参加数学竞赛 每校至少有1人 这样有几种选法 分析 问题相当于把个30相同球放入6个不同盒子 盒子不能空的 有几种放法 这类问可用 隔板法 处理 解 采用 隔板法 得 练习 1 将8个学生干部的培训指标分配给5个不同的班级 每班至少分到1个名额 共有多少种不同的分配方法 2 从一楼到二楼的楼梯有17级 上楼时可以一步走一级 也可以一步走两级 若要求11步走完 则有多少种不同的走法 巩固练习 1 4名优等生被保送到3所学校 每所学校至少得1名 则不同的保送方案总数为 A 36 B 24 C 12 D 6 2 若把英语单词 error 中字母的拼写顺序写错了 则可能出现的错误的种数是 A 20 B 19 C 10 D 69 3 小于50000且含有两个5 而其它数字不重复的五位数有 个 A B C D A B B 4 某城新建的一条道路上有12只路灯 为了节省用电而不影响正常的照明 可以熄灭其中三盏灯 但两端的灯不能熄灭 也不能熄灭相邻的两盏灯 可以熄灭的方法共有 A 种 B 种 C 种 D 种 A 5 对某种产品的6件不同的正品和4件不同的次品 一一进行测试 至区分出所有次品为止 若所有次品恰好在第5次测试时全部发现 则这样的测试方法有种可能 解 由题意知前5次测试恰有4次测到次品 且第5次测试是次品 故有 种可能 6 有四同学在同一天的上 下参加 身高与体重 立定跳远 肺活量 握力 台阶 五个项目的测试 每位同学上 下各测试一个项目 且不重复 若上午不测 握力 项目 下午不测 台阶 项目 其余项目上 下午都各测试一人 则不同的安排方式有 种 分析 上午测试安排方式有 下午测试方式分为 1 若上午测试 台阶 的同学下午测试 握力 的安排方式 2 2 若上午测试 台阶 的同学下午不测试 握力 的安排方式 9 264 上午项目 身高与体重 立定跳远 肺活量 台阶 下午项目 身高与体重 立定跳远 肺活量 握力 7 5名乒乓球队员中 有2名老队员和3名新队员 现从中选出3名队员排成1 2 3号参加团体比赛 则入选的3名队员中至少有一名老队员 且1 2号中至少有1名新队员的排法有 种 以数字作答 8 某学习小组有5个男生3个女生 从中选3名男生和1名女生参加三项竞赛活动 每项活动至少有1人参加 则有不同参赛方法 种 解 采用先组后排方法 9 3名医生和6名护士被分配到3所学校为学生体检 每校分配1名医生和2名护士 不同的分配方法共有多少种 解法一 边分边排 解法二 依次确定到第一 第二 第三所学校去的医生和护士 10 15人按照下列要求分配 求不同的分法种数 1 分为三组 每组5人 共有 种不同的分法 2 分为甲 乙 丙三组 一组7人 另两组各4人 共有 种不同的分法 3 分为甲 乙 丙三组 一组6人 一组5人 一组4人 共有 种不同的分法 11 8名同学选出4名站成一排照相 其中甲 乙两人都不站中间两位的排法有 种 12 某班有27名男生13女生 要各选3人组成班委会和团支部每队3人 3人中2男1女 共有 种不同的选法 例2 求不同的排法种数 6男2女排成一排 2女相邻 6男2女排成一排 2女不能相邻 4男4女排成一排 同性者相邻 4男4女排成一排 同性者不能相邻 分析 由2女捆绑成一人与6男全排列 再把2女全排列 有A77 A22种 捆绑法 把6男2女8人全排列 扣去2女 相邻 就是2女 不相邻 所以有A88 A77 A22种 排除法 还可用 插空法 直接求解 先把6男全排列 再在6男相邻的7个空位中排2女 所以共有A66 A72种 分离排列问题 思考 对于不相邻的分离排列能否都用 排除法 若改5男3女排成一列 3女不相邻 用排除法得对吗 4男4女排成一列 同性者相邻 把4男 4女捆绑成一个排列 然后同性者之间再全排列 所在地共有A22 A44 A44种 捆绑法 同性不相邻必须男女都排好 即男奇数位 女偶数位 或者对调 总排列数为A22 A44 A44种 一 有条件限制的排列问题 例1 5个不同的元素a b c d e每次取全排列 a e必须排在首位或末位 有多少种排法 a e既不在首位也不在末位 有多少种排法 a e排在一起多少种排法 a e不相邻有多少种排法 a在e的左边 可不相邻 有多少种排法 解 解题思路 分两步完成 把a e排在首末两端有A22种 再把其余3个元素排在中间3个位置有A33种 由乘法共有A22 A33 12 种 排法 优先法 二 排列组合应用问题 解 先从b c d三个选其中两个排在首末两位 有A32种 然后把剩下的一个与a e排在中间三个位置有A33种 由乘法原理 共有A32 A33 36种排列 间接法 A55 4A44 2A33 种 排法 解 捆绑法 a e排在一起 可以将a e看成一个整体 作为一个元素与其它3个元素全排列 有A44种 a e两个元素的全排列数为A22种 由乘法原理共有A44 A22 种 排列 解 排除法 即用5个元素的全排列数A55 扣除a e排在