《排列组合常用几种基本方法》由会员分享，可在线阅读，更多相关《排列组合常用几种基本方法（14页珍藏版）》请在金锄头文库上搜索。
1、 Date1新疆奎屯市第一高级中学 特级教师王新敞 要明确堆的顺序时 必须先分堆后再把堆数当 作元素个数作全排列 若干个不同的元素局部 等分 有 个均等堆 要将选取出每一个堆的组合数的乘积除以m 若干个不同的元素 等分 为 个堆 要将选取 出每一个堆的组合数的乘积除以m 非均分堆问题 只要按比例取出分完再用乘 法原理作积 分组 堆 问题的六个模型 无序不等分 无序等分 无序局部等分 有序不等分 有序等分 有序局部等分 处理问题的原则 1 分组 堆 问题 Date2新疆奎屯市第一高级中学 特级教师王新敞 例1 有四项不同的工程 要发包给三个工程队 要 求每个工程队至少要得到一项工程 共有多少种不
2、同 的发包方式 解 要完成发包这件事 可以分为两个步骤 先将四项工程分为三 堆 有 种分法 再将分好的三 堆 依次给三个工程队 有3 6种给法 共有6 6 36种不同的发包方式 1 分组 堆 问题 Date3新疆奎屯市第一高级中学 特级教师王新敞 例2 7人排成一排 甲 乙两人不相邻 有多少种不同的排法 解 分两步进行 几个元素不能相邻时 先排一般元素 再 让特殊元素插孔 第1步 把除甲乙外的一般人排列 第2步 将甲乙分别插入到不同的间隙或两端中 插孔 解决一些不相邻问题时 可以先排 一般 元素然后插入 特殊 元素 使问题得以解决 2 插空法 Date4新疆奎屯市第一高级中学 特级教师王新敞
3、相邻元素的排列 可以采用 局部到整体 的排 法 即将相邻的元素局部排列当成 一个 元素 然 后再进行整体排列 3 捆绑法 例3 6人排成一排 甲 乙两人必须相邻 有多少种不的排法 解 1 分两步进行 甲 乙 第一步 把甲乙排列 捆绑 第二步 甲乙两个人的梱看作一个元素与其它的排队 几个元素必须相邻时 先 捆绑成一个元素 再与 其它的进行排列 Date5新疆奎屯市第一高级中学 特级教师王新敞 例4 5个人站成一排 甲总站在乙的右侧的有多少 种站法 几个元素顺序一定的排列问题 一般是先排列 再消 去这几个元素的顺序 或者 先让其它元素选取位置排 列 留下来的空位置自然就是顺序一定的了 4 消序法
4、留空法 解法1 将5个人依次站成一排 有 解法2 先让甲乙之外的三人从5个位置选出3个站好 有 种站法 然后再消去甲乙之间的顺序数 甲总站在乙的右侧的有站法总数为 种站法 留下的两个位置自然给甲乙有1种站法 甲总站在乙的右侧的有站法总数为 Date6新疆奎屯市第一高级中学 特级教师王新敞 变式 如下图所示 有5 横8竖构成的方格图 从 A到B只能上行或右行共 有多少条不同的路线 解 如图所示 1 2 3 4 5 6 7 将一条路经抽象为如下的一个 排法 5 1 8 1 11格 其中必有四个 和七个 组成 所以 四个 和七个 一个排序就对应一条路经 所以从A到B共有 条不同的路径 4 消序法 留
5、空法 也可以看作是 1 2 3 4 5 6 7 顺序一定的排列 有 种排法 Date7新疆奎屯市第一高级中学 特级教师王新敞 n个 相同小球放入m m n 个盒子里 要求每个 盒子里至少有一个小球的放法等价于n个相同小球 串成一串从间隙里选m 1个结点剪截成m段 例5 某校准备参加今年高中数学联赛 把16个选手名 额分配到高三年级的1 4 个教学班 每班至少一个名 额 则不同的分配方案共有 种 5 剪截法 隔板法 解 问题等价于把16个相同小球放入4个盒子里 每个盒子至少有一个小球的放法种数问题 将16个小球串成一串 截为4段有 种截断法 对应放到4个盒子里 因此 不同的分配方案共有455种
6、Date8新疆奎屯市第一高级中学 特级教师王新敞 n个 相同小球放入m m n 个盒子里 要求每个 盒子里至少有一个小球的放法等价于n个相同小球 串成一串从间隙里选m 1个结点剪截成m段 变式 某校准备参加今年高中数学联赛 把16个选 手名额分配到高三年级的1 4 个教学班 每班的名额 不少于该班的序号数 则不同的分配方案共有 种 5 剪截法 解 问题等价于先给2班1个 3班2个 4班3个 再把余下的10个相同小球放入4个盒子里 每个盒子 至少有一个小球的放法种数问题 将10个小球串成一串 截为4段有 种截断法 对应放到4个盒子里 因此 不同的分配方案共有84种 Date9新疆奎屯市第一高级中
7、学 特级教师王新敞 编号为1至n的n个小球放入编号为1到 n的n个盒 子里 每个盒子放一个小球 要求小球与盒子的编 号都不同 这种排列称为错位排列 6 错位法 特别当n 2 3 4 5时的错位数各为1 2 9 44 例6 编号为1至6的6个小球放入编号为1至6的6个 盒子里 每个盒子放一个小球 其中恰有2个小球与盒 子的编号相同的放法有 种 解 选取编号相同的两组球和盒子的方法有 种 其余4组球与盒子需错位排列有9种放法 故所求方法有15 9 135种 Date10新疆奎屯市第一高级中学 特级教师王新敞 7 剔除法 从总体中排除不符合条件的方法数 这是一种 间接解题的方法 例7 从集合 0 1
8、 2 3 5 7 11 中任取3个元素分别作为直 线方程Ax By C 0中的A B C 所得的经过坐标 原点的直线有 条 解 所有这样的直线共有 条 其中不过原点的直线有 条 所得的经过坐标原点的直线有210 180 30条 排列组合应用题往往和代数 三角 立体几何 平面解 析几何的某些知识联系 从而增加了问题的综合性 解答这 类应用题时 要注意使用相关知识对答案进行取舍 Date11新疆奎屯市第一高级中学 特级教师王新敞 B B 巩固练习 Date12新疆奎屯市第一高级中学 特级教师王新敞 A 4 5个人排成一排 其中甲 乙不相邻的排法种数是 A 6 B 12 C 72 D 144 C 巩固练习 Date13新疆奎屯市第一高级中学 特级教师王新敞 分堆问题 解决排列 组合问题的一些常用方法 错位法 剪截法 隔板法 捆绑法 剔除法 插孔法 消序法 留空法 小结 Date14新疆奎屯市第一高级中学 特级教师王新敞
