《排列组合公式》PPT课件.ppt

《《排列组合公式》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《排列组合公式》PPT课件.ppt（110页珍藏版）》请在金锄头文库上搜索。

1、排列组合公式 排列组合公式非降路径问题组合恒等式 排列与组合 从五个候选人中选出两个代表把5本不同的书安排在书架上从五个候选人中选出两个代表时 有10种可能的结果 把5本不同的书安排在书架上有120种方法选出 组合 安排 排列 一 排列组合公式 排列问题 从某个集合中有序地选取若干个元素的问题组合问题 从某个集合中无序地选取若干个元素的问题注意 可以重复不能重复 排列 无重排列可重排列从 1 2 9 中选取数字构成四位数 使得每位数字都不同 有多少个 从 1 2 9 中选取数字构成四位数 使得不同数位上的数字可以相同 有多少个 1 无重排列 n个元素的r 无重排列数 排列的长度r计算 一般情形

2、 乘法原理r n时 n个元素的全排列r 0时r n时 2 可重排列 n个元素的r 可重排列数计算 乘法原理 例题 在1和10 000 000 000之间的一百亿个数中 有多少个数含有数码1 又有多少个数不含数码1 不含1 910含1 1010 910 1 例题 一个二元序列是由一些0和1所组成的序列 n码二元序列指该序列中数码的个数为n 试问 含有偶数个0的n码二元序列的个数是多少 2n 1考虑n码四元序列 即以0 1 2和3为其数码的序列 则含0和1的总个数为偶数的序列有多少个 4n 2 例题 求n码四元序列中含有偶数个0的个数 放球问题 设n r 把r个不同的球放入n个不同的盒子 这里每一

3、盒最多只能装一物 允许空盒 放球的方法数为多少 第一个球有n种选法 第二个球有n 1种 等等 乘法原理P n r 放球问题 把r个不同的球放入n个不同的盒子 一个盒中可以放多个球 也允许空盒 放球的方法数为多少 第一个球有n种选法 第二个球有n种 等等 乘法原理nr这里n和r的大小没有限制 例子 将3封信向2个信箱投寄 有多少种投寄方法 23 8无序占位模型 不考虑盒子中的排列次序 放球问题 把r个不同的球放入n个不同的盒子 一个盒中可以放多个球 也允许空盒 考虑每个盒子中球的次序 放球的方法数为多少 有序占位模型有n种方法放第一个球 第一个球放入一个盒后 可以把这个球当成是一个添加的隔板 它

4、把该盒分成两个盒 因此放第二个球有n 1种方法 等等n n 1 n 2 n r 1 n rF n r r 例子 某车站有6个进站口 今有9人进站 有多少种不同的进站方法 6 9 6 7 14七部汽车通过五间收费亭的方式数 今欲在五根旗杆上悬挂七面不同的旗子 全部旗都得展示出来 但并非所有的旗杆都得使用 问有多少种安排的方法 放球问题 另解 把这样一个方法设想为r个不同的球和n 1个相同的盒间板的一个有序安排 组合 无重组合可重组合从 a b c 中选取2个不同元素 选法数是多少 从 a b c 中选取5个元素 元素可以相同 选法数是多少 3 无重组合 Combination n个元素的r 无重

5、组合数无重组合数与无重排列数的关系计算r 0时r n时r n时 组合数的推广 几个记号 下阶乘函数 上阶乘函数 计算 例题 如果一个凸十边形无三条对角线在这个十边形的内部交于一点 问这些对角线被它们的交点分成多少条线段 多边形 例题 对角线的条数为C 10 2 10 45 10 35任选两条对角线 可能相交在多边形内部 可能交点为多边形的顶点 可能无交点 交点在多边形外 任选四个顶点 对应一个交点 每个对角线分成两段每个对角线是一段35 C 10 4 2 455 例题 C 5 2 5 C 5 4 2 15 C 10 2 10 C 10 4 2 455 C 4 2 4 C 4 4 2 4 4 可

6、重组合 n个元素的r 可重组合例子计算一一对应的思想 推论 方程x1 x2 xn r的非负整数解的个数 n r时 此方程的正整数解的个数n元集合的r 可重组合数 要求每个元素至少出现一次 正整数r的n 长有序分拆的个数求x1 x2 x3 x4 20的整数解的数目 其中x1 3 x2 1 x3 0 x4 5 例题 从为数众多的一分币 二分币 一角币和二角币中 可以有多少种方法选出六枚来 F 4 6 C 4 6 1 6 C 9 6 84 例题 某糕点厂将8种糕点装盒 若每盒有一打糕点 求市场上能买到多少种该厂出品的盒装糕点 某糕点厂将8种糕点装盒 若每盒有一打糕点 且要求每种糕点至少放一块 求市场

7、上能买到多少种该厂出品的盒装糕点 例题 摇三个不同的骰子的时候 可能的结果的个数是多少 63 216 如果这三个骰子是没有区别的 则可能结果的个数是多少 从1 2 3 4 5 6这六个数中允许重复地选出三个数 F 6 3 C 6 3 1 3 56将r个骰子掷一次 总共可以掷出多少种不同结果 F 6 r C 6 r 1 r C r 5 r C r 5 5 有约束条件的排列 引例 用两面红旗 三面黄旗依次悬挂在一根旗杆上 问可以组成多少种不同的标志 5 有约束条件的排列 设有k个元素a1 a2 ak 由它们组成一个n 长的排列 其中对1 i k ai出现的次数为ni n1 n2 nk n 求排列的

8、总数 求解方法1求解方法2 例题 五条短划和八个点可以安排成多少种不同的方式 如果只用这十三个短划和点中的七个 则有多少种不同的方式 例题 证明对任意正整数k k 能被 k k 1 整除 提示 k 个物体 其中k个物体属于第一类 k个物体属于第二类 k个物体属于第 k 1 类 推论 多项式 x1 x2 xn r的展开式中有项 其中项的系数为 例题 数1400有多少个正因数 1400 23 52 7 3 1 2 1 1 1 24 放球问题 设n r 把r个相同的球放入n个不同的盒子使得每盒至多装一个球 方法数 选盒子即可C n r 放球问题 把r个相同的球放入n个不同的盒子 每盒可以装任意多个球

9、 方法数 放这r个球 等价于从n个盒中选出r个来装这r个球而允许诸盒重复选取 F n r C n r 1 r 放球问题 把r个相同的球放入n个不同的盒子 每盒可以装任意多个球 方法数 另解 把分配这r个球入n个盒子设想为这r个球和n 1个隔板的一个排列 球是相同的 隔板也是相同的 C n r 1 r 放球问题 设r n 把r个相同的球放入n个不同的盒子中 盒子中可以放入任意多个球 但不允许空盒 方法数 现在每个盒中放入一个球 再放剩下的r n个球C r n n 1 r n C r 1 r n C r 1 n 1 放球问题 设r n 把r个相同的球放入n个不同的盒子中 要求每一盒至少包含q个球

10、方法数 现在每个盒中放入q个球 再放剩下的r qn个球C r qn n 1 r qn C n nq r 1 r nq C n nq r 1 n 1 放球问题 例题 今有五封不同的信要经由一个讯道传送 又有总共15个空白要插在这些信之间而使得每两封信之间至少有三个空白 有多少种方法安排这些信和空白 信的安排5 对一种信的安排 有4个信件位置 安排15个空白 要求每个信件位置至少有三个空白 5 C 4 4 3 15 1 4 1 5 C 6 3 放球问题 有n个球 其中第一种颜色n1个 第二种颜色n2个 第k种颜色nk个 将这n个球放入n个不同的盒中 每一个盒装一个球 问分配方案数 等价于这n个球的

11、排列数 另解 选盒子装每种颜色的球 放球问题 有r个球 其中第一种颜色n1个 第二种颜色n2个 第k种颜色nk个 将这r个球放入n个不同的盒中 每一个盒装一个球 r n 问分配方案数 方法一 先选盒子 再分配球 方法二 针对每种颜色的球选盒子 多重集合 通常的 集合 具有无重性 在多重集中 同一个元素可以出现多次 1 2 3 是一个集合 而 1 1 1 2 2 3 不是一个集合 而是一个多重集 简记为 3 1 2 2 1 3 计算多重集的势时 出现多次的元素则需要按出现的次数计算 上面多重集的势为6 可重组合与可重排列可以看作是多重集的组合与排列问题 可重排列与可重组合 n个元素 a1 a2

12、an 的r 无重组合 排列 可以看做多重集 1 a1 1 a2 1 an 的r 组合 排列 n个元素 a1 a2 an 的r 可重组合 排列 可以看做多重集 a1 a2 an 的r 组合 排列 有限制的排列问题可以看做多重集 n1 a1 n2 a2 nk ak 的全排列 分组与分堆 区分 固定分组 将12本 不同的 书平均分给A B C D四个学生 每人三本 有多少种分法 将12本书分给四个学生 使得A B各得四本 C D各得2本 有多少种分法 将12本书分给四个学生 A得5本 B得4本 C得2本 D得1本 有多少种分法 区分 分堆 将12本书平均分成四堆有多少种分法 将12本书分成四堆 有两

13、堆各4本 另外两堆各2本 有多少种分法 将12本书分成四堆 其本数分别为5 4 2 1 有多少种分法 区分 不固定分组 将12本书平均分给A B C D四个学生 使得每人各得三本 有多少种分法 将12本书分给A B C D四个学生 使得有两个学生各得4本 有两个学生各得2本 有多少种分法 将12本书分给A B C D四个学生 使得有1人得5本 有一人得4本 有1人得两本 有1人得1本 有多少种分法 分组与分堆 固定分组 无序分组 分堆不定分组固定分组与分堆的区别是讲不讲组间的次序 只在各组元素个数相等时有区别固定分组与不定分组的区别是每个组的元素个数是不是确定 只在各组元素个数不等时才有区别

14、区分 一 将12本书分给四个学生 使得A B各得四本 C D各得2本 有多少种分法 将12本书分成四堆 有两堆各4本 另外两堆各2本 有多少种分法 将12本书分给A B C D四个学生 使得有两个学生各得4本 有两个学生各得2本 有多少种分法 区分 二 将12本书分给四个学生 A得5本 B得4本 C得2本 D得1本 有多少种分法 将12本书分成四堆 其本数分别为5 4 2 1 有多少种分法 将12本书分给A B C D四个学生 使得有1人得5本 有一人得4本 有1人得两本 有1人得1本 有多少种分法 区分 三 将12本书平均分给A B C D四个学生 每人三本 有多少种分法 将12本书平均分成

15、四堆有多少种分法 将12本书平均分给A B C D四个学生 使得每人各得三本 有多少种分法 限距组合 引例 书架上有1 24共24卷百科全书 从其中选5卷使得任何两卷都不相继 这样的选法有多少种 6 限距组合 设A 1 2 n 它的任一r 无重组合均可以依自然顺序排出a1 a2 ar 其中a1 a2 ar 设k是非负整数 用f k n r 表示A的一切满足条件ai 1 ai k 1 1 i r 1 的r 无重组合数 求f k n r 求解思想 一一对应k 0时 例题 书架上有1 24共24卷百科全书 从其中选5卷使得任何两卷都不相继 这样的选法有多少种 7 圆排列 n个元素的r 无重圆排列数圆

16、排列与线排列的区别计算 例题 例1 把20个不同的钉子钉在鼓表面一周 订钉子的方式有种 例2 把20个不同的珍珠串成项链 串项链的方式有种 项链问题 例从1到300间取出3个不同的数 使它们的和被3整除 有多少种取法 提示 将1到300这300个整数按照除以3的余数分成3组 考虑选出的3个数属于哪些组 例下图中有多少个矩形 映射的个数 n元集X到m元集A的映射的个数将X看作物件的集合 A看作盒子的集合 则一个映射表示把物件放入盒子的一种安排 要求 1 每个物体都要放入某个盒子 2 一个物体不得放入两个盒子 3 允许多个物体放入同一盒子 4 可以剩有空盒子 若将X看作有标号的位置的集合 A看作排在这些位置的字母的组合 则一个映射对应一个长为n的字 则 1 字长必须为n 2 一个位置只能放一个字母 3 多个位置可以重复出现同一字母 4 有些字母有可能不出现 例题 n元集合X到m元集合A的映射的个数 将n个物体放在m个的盒子中的不同放法 n元集合X到m元集合A的单射的个数 把n个物体放入m个盒子 每个盒子至多放一个物体的安排有多少种 3个物体分放到4个不同的盒子中 要求每个盒子至多放一个物体