《排列组合题型总结》PPT课件.ppt

排列组合题型总结 在处理排列问题时 ， 所要研究的对象 有两组 ， 一是要被排列的对象 ， 一是位置 ， 在这两组对象中有时候会出现一个或者多 个特殊的对象： 若有一个特殊对象 ， 一般先把特殊的对象 优先进行处理 ， 然后再对其他的没有特殊 要求的对象进行全排列； 【 一 】 特殊对象问题： 如果出现了 两个特殊要求 ， 一般使用 分类 的方法处理 ， 针对其中的一个的位置不同 进行分类来处理 ， 再或者用 间接法 例 1、 有 5人排成一列 ， 其中甲不在第一的 位置 ， 有多少种排法 ？ 例 2、 有 5人排成一列 ， 其中甲不能在第一 ， 乙不能在最后 ， 有多少种排法 ？ 特殊对象问题： 【 二 】 名额分配问题 这种问题处理时 ， 要注意两个特征： 1、 名额之间没有什么不同 2、 名额分配时的具体要求是什么 当问题中要求分配时每人至少一个时 ， 只需要在 所有名额形成空隙中选取比人数少一个的空隙 ， 放入相同的挡板即可 若问题中没有具体分配要求时 ， 可以不上和人数 相同的名额转化成第一组问题来处理 【 二 】 名额分配问题 例 1、 有 10个三好学生的名额分给 3个班 ， 要求每班至少有一个名额 ， 怎么分 ？ 例 2、 有 7个三好学生的名额 ， 分给 3个 班 ， 怎么分 ？ 【 三 】 分组分配问题 这里的分配问题与名额分配的最大区别是： 名额是相同 ， 现在是不同的对象进行分配 例 1、 有 6本不同的书 ， 平均分给甲乙丙三人 ， 有多少种分法 ？ 平均分配 :乘法原理 ， 直接分法 例 2、 有 6本不同的书 ， 平均分为三组 ， 有多少 种分法 ？ 平均分组： 把例 1分成两步：先分成三组；把不 同的三组分给三个不同人 （ 组数的阶乘 ） ， 求乘 积 。 所以 平均分组方法 =直接分法 /组数的阶乘 【 三 】 分组分配问题 例 3、 有 6本不同的书 ， 分甲 1本 ， 乙 2本 ， 丙 3本 ， 有多少种分法 ？ 不平均定向分配： 分步 ， 直接分法 例 4、 有 6本不同的书 ， 分三组 ， 一组 1 本 ， 一组 2本 ， 一组 3本 ， 有多少种分法 ？ 不平均分组 :把例 3理解成两步：先分组 ， 然后再把组定向分给人 （ 只有 1种方法 ） ， 所以答案同问题 3,方法为直接分法 【 三 】 分组分配问题 例 5、 有 6本不同的书 ， 分给三个人 ， 一人 1本 ， 一人 2本 ， 一人 3本 ， 有多少种分法 ？ 不平均的不定向分配： 理解成 2步：先分组 ， 然 后把组不定向的分给人 （ 组数的阶乘 ） ,再求乘 积 。 例 6、 有 9本不同分成三组 ， 一组 5本 ， 另外两组 各 2本 ， 有多少种分法 ？ 混合型分组： 理解成两步：先不平均的分 ， 在 把某部分平均分组 ， 再求两步乘积 。 整理规律即： 先直接分 ， 然后除以平均组数的阶乘 【 三 】 分组分配问题 例 7、 有 9本不同的书 ， 分给甲乙均 2本 ， 丙 5本 ， 有多少种分法 ？ 混合型某部定向分配： 理解成两步 ， 先混合型 分组 ， 然后把组分给人； 其中平均部分的分配 （ 平均组数的阶乘 ） ， 再求乘积 例 8、 有 9本不同的书 ， 分给两人各 2本 ， 另一 人 5本 ， 有多少种分法 ？ 混合型部定向分配： 理解成两步 ， 先混合型分 组 ， 然后把组分给人 （ 不定向 ， 所有组数的阶 乘 ） ， 再求乘积 【 四 】 相邻问题 本组问题有两大类： 相邻的对象相同 ， 相邻的对象 不相同 1、 若相邻对象 不同时 ， 先把相邻的对象当成 一个 ， 和其他没有要求的对象进行全排列 ， 然后 再把相邻的对象进行全排列 ， 这两步求乘积 2、 若相邻对象 相同时 ， 先把其他的对象排好 ， 再把相邻的对象当成一个按要求放在其他对象摆 好而形成的空格中 【 四 】 相邻问题 例 1、 8人排成一列 ， 甲乙丙三人必须相 邻 ， 有多少种排法 ？ 例 2、 一排 8个座位 ， 3人坐 ， 5个空座位 相邻 ， 有多少种坐法 ？ 【 五 】 不 相邻问题 不相邻问题也有两大类： 不相邻的对象相同 ， 不相邻的对象不相同 1、 若不相邻对象不相同时 ， 先把其他的对象 进行排列 ， 再把不相邻的对象放在其他对象形成 空格中进行排列 2、 若不相邻的对象相同时 ， 也先把其他的对 象进行排列 ， 再从其他对象摆好形成的空格中 选 取 相应的空格 ， 最后直接把不相邻的对象放入 （ 1种方法 ， 因为相同 ） 【 五 】 不 相邻问题 例 1、 某人射击训练 ， 8枪命中 3枪 ， 恰 好没有任何 2枪连续命中 ， 有多少种情况 ？ 例 2、 8人排成一列 ， 甲乙丙三人不可相 邻 ， 有多少种排法 ？ 例 3、 8盏灯关掉 3盏 ， 不许关掉相邻的 ， 也不许关掉两端 ， 多少种方法 ？ 例 4、 某人射击训练 ， 8枪命中 3枪 ， 恰 好 2枪连续命中 ， 有多少种情况 ？ 【 六 】 成双成对问题 先按双取出 ， 再从各双分别取出一只 ， 自然不成双 例 1、 从 6双不同鞋子中取出 4只 ， 要求 都不许成双 ， 有多少种方法 ？ 例 2、 从 6双不同鞋子中取出 4只 ， 要求 恰好有一双 ， 有多少种方法 ？ 【 七 】 可（不可）重复使用的对象 问题中有两组对象 ， 解决问题时要以不可 重复使用的对象作为分布的标准 （ 住店 、 投信 、 映射 、 冠亚军等 ） 例 1、 5人住 3家店 ， 有多少种住法 ？ 例 2、 5人参加同一下比赛 ， 最终冠亚季军 名次有多少种 ？ 【 八 】 我不能我问题 在处理换位置 、 交换礼品 、 职务连任等问题 时规则要求往往是自己不允许和自己发生关系 ， 这种问题一般只到 4或 5组对象 。 常用 穷举法 、 或用间接法 ， 或用分步法 （ 注意第二步的处理技 巧 ） 例 1、 4人写 4张卡片 ， 自己不许拿自己的卡片 ， 有多少中拿法 ？ 例 2、 5人换位置 ， 有多少种不同的换法 ？ （ 44 种 ） 【 九 】 至多至少问题 常用分类的方法或者间接法 例 1、 从 5个男生和 4个女生 ， 选出 4人参 加比赛 ， 要求至少要有 2名女生的选法有 多少种 ？ 【 十 】 交叉功能问题 抓住一个特点进行分类 ， 千万不要分类 过多 例 1、 10名翻译 ， 有 6人会英语 ， 7人会 德语 ， 现需要英语 、 德语翻译各 3人 ， 共 多少中选派方案 ？ 【 十一 】 相对顺序固定问题 相对顺序固定问题 ， 常用两种方法： （ 1） 一般要先处理掉没有相对顺序要求的 元素 ， 再把剩下的有相对顺序要求的元 素按照要求摆放 ， （ 2） 先随意地进行排列 ， 再除以随意摆放 过程中 相对顺序固定部分的顺序 【 十一 】 相对顺序固定问题 例 1、 书架上 6本不同的书 ， 现在要放上去 3本 ， 但要保持原来 6本的相对顺序不变 ， 有多少种放 法 ？ 例 2、 用 1、 2、 3、 4、 5、 6排成所有五位数 中 ， 个位数小于十位数 ， 而且十位数小于百位 数的有多少个 ？ 例 3、 用 1、 2、 3、 4、 5、 6排成所有五位数 中 ， 个位数小于十位数 ， 而且十位数大于百位 数的有多少个 ？ 【 十二 】 集合关系、子集个数问题 例 1、 a,b,c,d的所有子集多少个 ？ 例 2、 a,b是 A的子集 ， 而且 A又是 a,b,c,d,e的真子集 ， A的可能有多少种 ？ 【 十三 】 涂色问题 可以采取用到了几种颜色进行分类：在颜 色数少于空格数时 ， 要分步 ， 先选出重复使用的颜色 ， 再确定重复使用 颜色的位置 u 平面几何 、 立体几何问题 u 穷举法解决的问题