有约束条件的排列问题张用.ppt

1 2 1排列 有约束条件的排列问题 例1 某年全国足球甲级A组联赛共有14个队参加 每队要与其余各队在主 客场分别比赛一次 共进行多少场比赛 解 14个队中任意两队进行1次主场比赛与1次客场比赛 对应于从14个元素中任取2个元素的一个排列 因此 比赛的总场次是 有约束条件的排列问题 课本例题2 以人为标准进行分步 第一名同学有5种选择 第二名同学有5种选择 第三名同学也有5种选择 因此有 例2 1 有5本不同的书 从中选3本送给3名同学 每人各1本 共有多少种不同的送法 2 有5种不同的书 买3本送给3名同学 每人各1本 共有多少种不同的送法 有约束条件的排列问题 课本例题3 例3 用0到9这10个数字 可以组成多少个没有重复数字的三位数 解法一 对排列方法分步思考 从位置出发 或 有约束条件的排列问题 课本例题4 解法二 对排列方法分类思考 符合条件的三位数可分为两类 根据加法原理 从元素出发分析 例3 用0到9这10个数字 可以组成多少个没有重复数字的三位数 有约束条件的排列问题 课本例题4 解法三 间接法 从0到9这十个数字中任取三个数字的排列数为 所求的三位数的个数是 其中以0为排头的排列数为 逆向思维法 例3 用0到9这10个数字 可以组成多少个没有重复数字的三位数 有约束条件的排列问题 课本例题4 例4 由数字1 2 3 4 5组成没有重复数字的五位数 其中小于50000的偶数共有多少个 有约束条件的排列问题 2或4 1 3或2 4之一 例4 由数字1 2 3 4 5组成没有重复数字的五位数 其中小于50000的偶数共有多少个 有约束条件的排列问题 1或3或5 2或4 5 例4 由数字1 2 3 4 5组成没有重复数字的五位数 其中小于50000的偶数共有多少个 有约束条件的排列问题 例5 6个人站成前后两排照相 要求前排2人 后排4人 那么不同的排法共有 A 30种B 360种C 720种D 1440种 C 分排问题直排处理 有约束条件的排列问题 例6 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 1 男甲排在正中间 特殊元素 位置 优先法 有约束条件的排列问题 例6 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 2 男甲不在排头 女乙不在排尾 女乙在排头时 女乙不在排头时 所以共有 720 3000 3720种 有约束条件的排列问题 女乙 不甲乙 5 5 例6 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 2 男甲不在排头 女乙不在排尾 有约束条件的排列问题 间接法 例6 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 3 三个女生排在一起 相邻问题 捆绑法 有约束条件的排列问题 例6 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 4 三个女生两两都不相邻 不相邻问题 插空法 有约束条件的排列问题 例6 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 5 全体站成一排 甲 乙 丙三人自左向右顺序不变 定序问题 消序法 有约束条件的排列问题 定序问题 插空法 例6 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 6 若甲必须在乙的右边 可以相邻 也可以不相邻 有多少种站法 有约束条件的排列问题 定序问题 消序法 定序问题 插空法 例7 7位同学站成一排 共有多少种不同的排法 解 问题可以看作 7个元素的全排列A77 5040 7位同学站成一排 其中甲站在中间的位置 共有多少种不同的排法 解 问题可以看作 余下的6个元素的全排列A66 720 有约束条件的排列问题 7位同学站成一排 其中甲不站在首位 共有多少种不同的排法 解一 甲站其余六个位置之一有A61种 其余6人全排列有A66种 共有A61A66 4320 解二 从其他6人中先选出一人站首位 有A61 剩下6人 含甲 全排列 有A66 共有A61A66 4320 解三 7人全排列有A77 甲在首位的有A66 所以共有A77 A66 7A66 A66 4320 有约束条件的排列问题 4 7位同学站成一排 甲 乙只能站在两端的排法共有多少种 解 根据分步计数原理 第一步甲 乙站在两端有A22种 第二步余下的5名同学进行全排列有A55种则共有A22A55 240种排列方法 A55 A55 A22 A22 有约束条件的排列问题 5 7位同学站成一排 甲 乙不能站在排头和排尾的排法共有多少种 解 第一步从 除去甲 乙 其余的5位同学中选2位同学站在排头和排尾有A52种方法 第二步从余下的5位同学中选5位进行排列 全排列 有A55种方法 所以一共有A52A55 2400种排列方法 有约束条件的排列问题 间接法 6 若甲不在排头 乙不在排尾 有多少种不同的排法 解法一 直接法 以甲作为分类标准 分为两类 第一类 先安排甲在中间 再安排乙 有 第二类 先安排甲在排尾 再安排其他人 有 共有 3720种方法 有约束条件的排列问题 直接法 解法二 间接法 所有排法中除去不符合的 共有 3720种方法 所有排法 甲在排头 乙在排尾 甲在排头 乙在排尾 有约束条件的排列问题 间接法 例8 四位男生 三位女生排队照相 根据下列要求 各有多少不同的排法 1 七个人排一列 四个男生必须连排在一起 有约束条件的排列问题 1 捆绑法 四个男生看作一个元素和三个女生共四个元素有A44种排法 四个男生全排列有A44种排法由乘法原理共有 例8 四位男生 三位女生排队照相 根据下列要求 各有多少不同的排法 2 男女生相间排列 有约束条件的排列问题 男女男女男女男共有A44A33 144 例9 将5列车停在5条不同的轨道上 其中a列车不停在第一轨道上 b列车不停在第二轨道上 那么不同的停放方法有 A 120种 B 96种 C 78种 D 72种 特殊元素 或位置 优先安排 B 先算出5列火车排5条铁轨的排法 然后扣除掉A列车停在第一轨道上的方法总数 再扣除掉B列车停在第二轨道上的方法总数 再加上前面重复扣除的既满足A列车停在第一轨道上 又满足B列车停在第二轨道上的方法总数 就是所求的不同的停放方法 例9 将5列车停在5条不同的轨道上 其中a列车不停在第一轨道上 b列车不停在第二轨道上 那么不同的停放方法有 A 120种 B 96种 C 78种 D 72种 特殊元素 或位置 优先安排 解法2 不相邻问题 插空法 不相邻问题 插空法 捆绑法 七人排成一排 甲 乙两人必须相邻 且甲 乙都不与丙相邻 则不同的排法有 种 A 960种 B 840种C 720种 D 600种 相邻 用 捆绑 不邻 就 插空 从7盆不同的盆花中选出5盆摆放在主席台前 其中有两盆花不宜摆放在正中间 则一共有 种不同的摆放方法 例5 一天要排语 数 英 体 班会六节课 要求上午的四节课中 第一节不排体育课 数学排在上午 下午两节中有一节排班会课 问共有多少种不同的排法 特殊元素应该优先考虑1 数学排上午4种排法 班会排下午2种排法 其他四门课全排列24种排法 共4 2 24 1922 体育排第一节 数学3种排法 班会2种排法 其他三门课全排列6种排法 共3 2 6 363 用第一种排法减去第二种192 36 156 有约束条件的排列问题 例8 一天要排语 数 英 体 班会六节课 要求上午的四节课中 第一节不排体育课 数学排在上午 下午两节中有一节排班会课 问共有多少种不同的排法 分析 共是6节课讨论 上午第一节不能是体育 班会 则第一节就有4种可能第二节开始不能是班会 减去前面一节 还有4种第三节减去2节 班会 有3种可能第四节减去3节 班会 有2种可能第5节 早上排了4节了 下午 剩下一节跟班会有2种可能 第6节全部排好了就一节课1种可能 共4 4 3 2 2 1 192 疑问 若剩下的一节是数学呢 法一 1 当体育课被安排在下午 则在除班会以外的四节课在上午可以随便安排 共有种可能 再有下午的体育和班会共有 2种排法 所以共有 48种方法 2 当体育课被安排在上午 则在除班会以外的四节课中必须选出一门课与班会一起被安排在下午 共有种排法 在余下的三门课与体育课共四节被安排在上午 上午第一节有3种选法 第二节有3种选法 第三节有2种选法 第四节有1种选法 即 3 3 2 1种 共有 144种 由1 2 共48 144 192 而数在下午有36种 综上 有48 144 36 156种 法二 分析 共是6节课 综上 48 108 156 3 三名女生和五名男生排成一排 如果女生全排在一起 有多少种不同排法 如果女生全分开 有多少种不同排法 如果两端都不能排女生 有多少种不同排法 如果两端不能都排女生 有多少种不同排法 A66A33 4320 A55A63 14400 A52A66 14400 A52A66 2A31A51A66 36000或A88 A32A66 36000 练习 某小组7人排队照相 以下各有几种不同的排法 1 若排成两排 前排3人 后排4人 2 若排成两排 前排3人 后排4人 甲必排在前排 乙必排在后排 3 甲不在左端 乙不在右端 4 甲乙不相邻 5 甲 乙 丙均不相邻 6 甲乙必须间隔2人 小结 1 对有约束条件的排列问题 应注意如下类型 某些元素不能在或必须排列在某一位置 某些元素要求连排 即必须相邻 某些元素要求分离 即不能相邻 某些元素要求顺序一定 2 基本的解题方法 有特殊元素或特殊位置的排列问题 通常是先排特殊元素或特殊位置 称为优先处理特殊元素 位置 法 优先法 特殊元素 特殊位置优先安排策略 某些元素要求必须相邻时 可以先将这些元素看作一个元素 与其他元素排列后 再考虑相邻元素的内部排列 这种方法称为 捆绑法 相邻问题捆绑处理的策略 某些元素不相邻排列时 可以先排其他元素 再将这些不相邻元素插入空挡 这种方法称为 插空法 不相邻问题插空处理的策略 4 某些元素顺序一定时 可以用总排列数除以这几个元素的全排列数 这种方法称为 倍除法 定序问题倍除处理的策略 综合应用 练 课本P27页4 5 6 7 简答 1 有4个男生和3个女生排成一排 按下列要求各有多少种不同排法 3 甲 乙两同学必须相邻 而且丙不能站在排头和排尾 4 若甲 乙两名女生相邻 且不与第三名女生相邻 1 7位同学站成一排 甲 乙只能站在两端 2 7位同学站成一排 甲 乙不能站在两端 5 甲 乙 丙3名同学必须相邻 而且要求乙 丙分别站在甲的两边 讨论 3 1 因为a不等于0 先确定a 有A 4 1 4 然后从剩下4个数中选2个 有A 4 2 4 3 12 故可以组成4 12 48个不同的一元二次方程 2 1 c 0时 方程总有解 A 4 2 4 3 12 2 c不等于0 b 0时 方程总无解 3 a b c均不为0时 满足b 2 4 a c大于等于0 才有解 只有 5 2 4 1 3 5 2 4 3 1 7 2 4 1 3 7 2 4 1 5 共6种可能 所以有实数解的方程有12 6 18个 一 无限制条件的排列问题 1 从5种不同的蔬菜种子中选3种分别种在3块不同土质的土地上 共有多少种不同的种法 分析 把5个种子分别标上1 2 3 4 5 用123表示种子1种在第1块土地上 种子2种在第2块土地上 种子3种在第3块土地上 因此3个数的一个排列就是一种种植方法 从5个不同数中取出3个数的一个排列就是一种种植方法 多少个排列就有多少种种法 2 公共汽车上有4位乘客 其中任何两个人都不在同一车站下车 汽车沿途停靠6个站 那么这4位乘客不同的下车方法有多少种 分析 个车站分别标上1 2 3 4 5 6 如1246表示第一位乘客在1号站下 第二位乘客在2号站下 第三位乘客在4号站下 第四位乘客在6号车站下 不同的排列表示不同的下法 有多少个不同的排列就有多少种不同的下法 共有A46 6 5 4 3 360 5 某信号兵用红 黄 蓝3面旗从上到下挂在竖直的旗杆上表示信号 每次可以任挂1面 2面或3面 并且不同的顺序表示不同的信号 一共可以表示多少种不同的信号 例2 用0 1 2 3 4 5可组成多少个无重复数字的1 五位数2 六位偶数3 大于213045的自然数 1 解1 位置分析法 首位是特殊位置 0不能排 有5种排法 其余4个位置有A45种排法 由乘法原理知共有5 A45 5 5 4 3 2 600 解2 间接法 6个数中取5个数的排列中有不满足要求的数如02134等 0 这样的数共有A56 A45 600 2 可分为两类 第一类是个位为0的有A55个 第二类个位不是0 个位有两种排法 首位有4种排法 中间四位有A44种排法 第二类共有2 4 A44 192 由加法原理共有A55 192 312 形如2134 2135 的数有A12 A22形如21054有一个因此满足要求的数共有449个 3 形如3 4 5 这样的数都是满足条件的数共有A13 A55形如23 24 25 这样的数都是满足条件的数共有A13 A44形如214 215 这样的数都是满足条件的数共有A12 A33 解 连续命中的3枪和命中的另一枪被未命中的4枪所隔开 如图 表示没有命中 命中的三枪看作一个元素和另外命中的一枪共两个元素插到五个空档中有A25 5 4 20种排法 2 某人射击8枪 命中4枪 4枪命种恰好3枪连在一起的不同种数有多少 3 一排8个座位 3人去坐 每人两边至少有一个空座的坐法有多少种 4 一排长椅上共有10个座位 现有4人就座 恰有五个连续空位的坐法种数为 用数字作答 480 解法二 可以画一个树状图 知满足要求的拿法有9种 四 其他问题 同室4名学生各写一张贺卡 放在一起 然后各人从中各拿一张 但均不能拿自己写的那张 共有多少种拿法 解法一 第一步第一个同学从中拿一张贺卡 满足要求的拿法有3种 第二步考虑被第一个同学拿走贺卡的那个同学也有3种拿法 第三步 第四步各有一种拿法 由乘法原理共有3 3 1 1 9 1 四位男生 三位女生排队照相 根据下列要求 各有多少不同的排法 七个人排一列 三个女生任何两个都不能相邻排在一起 七个人排一列 四个男生必须连排在一起 男女生相间排列 巩固练习 男女男女男女男共有A44A35 144 插空法 先排四个男生共有A44种排法 X X X X