组合数学课件_lcq.ppt

组合数学 简介 相关课程 使用教材 数学分析 高等代数 离散数学 书名 组合数学 第三版 作者 孙淑玲出版社 中国科学技术大学出版社 本课程针对计算机科学中的一个重要学科 组合数学 组合数学是数学的一个分支 它研究事物在结定模式下的配置 研究这种配置的存在性 所有可能配置的计数和分类以及配置的各种性质 组合数学在计算机科学中有着极其广泛的应用 组合学问题求解方法层出不穷 干变万化 应以理解为基础 善于总结各种技巧 掌握科学的组织和推理方法 目录 1 引言第1章排列与组合1 1加法法则和乘法法则1 2排列1 3组合1 4二项式定理1 5组合恒等式及其含义1 6模型转换本章小结习题第2章鸽笼原理2 1鸽笼原理2 2鸽笼原理的推广2 3Ramsey定理本章小结 习题第3章容斥原理3 1容斥原理3 2重集r 组合3 3错排问题3 4有限制排列3 5 一般有限制排列3 6 广义容斥原理本章小结习题第4章母函数4 1母函数的基本概念4 2母函数的基本运算4 3在排列组合中的应用4 4在组合恒等式中的应用 目录 基本概念 广义的组合数学就是离散数学 离散数学是狭义的组合数学和图论 代数结构 数理逻辑等的总称 组合数学是一门研究离散对象的科学 随着计算机科学的日益发展 组合数学的重要性也日渐凸显 因为计算机科学的核心内容是使用算法处理离散数据 基本概念 狭义的组合数学主要研究满足一定条件的组态 也称组合模型 的存在 计数以及构造等方面的问题 组合数学的主要内容有组合计数 组合设计 组合矩阵 组合优化等 组合数学研究的中心问题是按照一定的规则来安排有限多个对象 如果人们想把有限多个对象按照它们所应满足的条件来进行安排 当符合要求的安排并非显然存在或显然不存在时 首要的问题就是要证明或者否定它的存在 这就是存在性问题 如果所要求的安排存在 则可能有多种不同的安排 这又经常给人们提出这样的问题 有多少种可能的安排方案 如何对安排的方案进行分类 这就是计数问题 如果一个组合问题有解 则往往需要给出求其某一特定解的算法 这就是所谓的构造性问题 如果算法很多 就需要在一定的条件下找出一个或者几个最优或近乎最优的安排方案 这就是优化问题 组合数学中的著名问题 计算一些物品在特定条件下分组的方法数目 这些是关于排列 组合和整数分拆的 地图着色问题 对世界地图着色 每一个国家使用一种颜色 如果要求相邻国家的颜色相异 是否总共只需四种颜色 这是图论的问题 船夫过河问题 船夫要把一匹狼 一只羊和一棵白菜运过河 只要船夫不在场 羊就会吃白菜 狼就会吃羊 船夫的船每次只能运送一种东西 怎样把所有东西都运过河 这是线性规划的问题 组合数学中的著名问题 中国邮差问题 由中国组合数学家管梅谷教授提出 邮递员要穿过城市的每一条路至少一次 怎样行走走过的路程最短 这不是一个NP完全问题 存在多项式复杂度算法 先求出度为奇数的点 用匹配算法算出这些点间的连接方式 然后再用欧拉路径算法求解 这也是图论的问题 任务分配问题 也称婚配问题 有一些员工要完成一些任务 各个员工完成不同任务所花费的时间都不同 每个员工只分配一项任务 每项任务只被分配给一个员工 怎样分配员工与任务以使所花费的时间最少 这是线性规划的问题 如何构作幻方 第1章排列与组合 本章重点介绍以下的基本计数方法 加法法则和乘法法则排列组合二项式定理的应用组合恒等式 相互独立的事件A B分别有k和l种方法产生 则产生A或B的方法数为k l种 1 1加法法则 1 1加法法则和乘法法则 1 1 1加法法则 加法法则 集合论定义 若 A k B l 且A B 则 A B k l 设S是有限集合 若 且时 则有 1 1加法法则例1 1 1加法法则和乘法法则 1 1 1加法法则 例题 例1 有一所学校给一名物理竞赛优胜者发奖 奖品有三类 第一类是三种不同版本的法汉词典 第二类是四种不同类型的物理参考书 第三类是二种不同的奖杯 这位优胜者只能挑选一样奖品 那么 这位优胜者挑选奖品的方法有多少种 解 设S是所有这些奖品的集合 Si是第i类奖品的集合 i 1 2 3 显然 Si Sj i j 根据加法法则有 1 1加法法则例2 3 1 1加法法则和乘法法则 1 1 1加法法则 例题 例2 大于0小于10的奇偶数有多少个 例3 小于20可被2或3整除的自然数有多少个 解 设S是符合条件数的集合 S1 S2分别是符合条件的奇数 偶数集合 显然 S1 S2 根据加法法则有 若 A k B l A B a b a A b B 则 A B k l 1 1乘法法则 1 1加法法则和乘法法则 1 1 2乘法法则 乘法法则 相互独立的事件A B分别有k和l种方法产生 则选取A以后再选取B的方法数为k l种 集合论定义 设是有限集合 且 则有 1 1乘法法则例4 1 1加法法则和乘法法则 1 1 2乘法法则 例题 例4 从A地到B地有二条不同的道路 从B地到C地有四条不同的道路 而从C地到D地有三条不同的道路 求从A地经B C两地到达D地的道路数 解 设S是所求的道路数集合 S1 S2 S3分别是从A到B 从B到C 从C到D的道路集合 根据乘法法则有 1 1乘法法则例5 1 1加法法则和乘法法则 1 1 2乘法法则 例题 例5 由数字1 2 3 4 5可以构成多少个所有数字互不相同的四位偶数 解 所求的是四位偶数 故个位只能选2或4 有两种选择方法 又由于要求四位数字互不相同 故个位选中后 十位只有四种选择方法 同理 百位 千位分别有三种 两种选择方法 根据乘法法则 四位数互不相同的偶数个数为2 4 3 2 48 1 1乘法法则例6 1 1加法法则和乘法法则 1 1 2乘法法则 例题 例6 求出从8个计算机系的学生 9个数学系的学生和10个经济系的学生中选出两个不同专业的学生的方法数 解 由乘法法则有选一个计算机系和一个数学系的方法数为8 9 72选一个数学系和一个经济系的方法数为9 10 90选一个经济系和一个计算机系的方法数为10 8 80由加法法则 符合要求的方法数为72 90 80 242 1 1重集的概念 1 1加法法则和乘法法则 1 1 3计数问题的分类 有序安排或有序选择 允许重复 不允许重复无序安排或无序选择 允许重复 不允许重复 标准集的特性 确定 无序 相异等 重集 B k1 b1 k2 b2 kn bn 其中 bi为n个互不相同的元素 称ki为bi的重数 i 1 2 n n 1 2 ki 1 2 重集的概念 1 2线排列 1 2排列 定义1 1 1 2 1线排列 集合论定义 定理1 1 从n个不同元素中 取r个 0 r n 按一定顺序排列起来 其排列数P n r 设A an 从A中选择r个 0 r n 元素排列起来 A的r 有序子集 A的r 排列 如n r Z且n r 0 P n r n n r 如n r 称全排列P n n n 如n r P n r 0 如r 0 P n r 1 证明 构造集合A的r 排列时 可以从A的n各元素中任选一个作为排列的第一项 有n种选法 第一项选定后从剩下的n 1个元素中选排列的第二项有n 1种选法 由此类推 第r项有n r 1种选法 根据乘法法则有 1 2线排列推论1 1 2排列 1 2 1线排列 两个推论 推论1 1 1 如n r N且n r 2 则P n r n P n 1 r 1 证明 在集合A的n个元素中 任一个元素都可以排在它的r 排列首位 故首位有n种取法 首位取定后 其他位置的元素正好是从A的另n 1个元素中取r 1个的排列 因此有P n 1 r 1 种取法 由乘法法则有P n r n P n 1 r 1 证毕 1 2线排列推论2 1 2排列 1 2 1线排列 两个推论 推论1 1 1 如n r N且n r 2 则P n r n P n 1 r 1 推论1 1 2 如n r N且n r 2 则P n r r P n 1 r 1 P n 1 r 证明 当r 2时 把集合A的r 排列分为两大类 一类包含A中的某个固定元素 不妨设为a1 另一类不包含a1 第一类排列相当于先从A a1 中取r 1个元素进行排列 有P n 1 r 1 种取法 再将a1放入每一个上述排列中 对任一排列 a1都有r种放法 由乘法法则 第一类排列共有r P n 1 r 1 个 第二类排列实质上是A a1 的r 排列 共有P n 1 r 个 再由加法法则有P n r r P n 1 r 1 P n 1 r 证毕 1 2线排列例1 1 2排列 1 2 1线排列 例题 例1 由数字1 2 3 4 5可以构成多少个所有数字互不相同的四位数 解 由于所有的四位数字互不相同 故每一个四位数就是集合 1 2 3 4 5 的一个4 排列 因而所求的四位数个数为 1 2线排列例2 1 2排列 1 2 1线排列 例题 例2 将具有9个字母的单词FRAGMENTS进行排列 要求字母A总是紧跟在字母R的右边 问有多少种这样的排法 如果再要求字母M和N必须相邻呢 解 由于A总是R的右边 故这样的排列相当于是8个元素的集合 F RA G M E N T S 的一个全排列 个数为如果再要求M和N必须相邻 可先把M和N看成一个整体 M N 进行7个元素的集合 F RA G E T S 的全排列 在每一个排列中再进行 M N 的全排列 由乘法法则 排列个数为 1 2线排列例3 1 2排列 1 2 1线排列 例题 例3 有多少个5位数 每位数字都不相同 不能取0 且数字7和9不能相邻 解 由于所有的5位数字互不相同 且不能取0 故每一个5位数就是集合 1 2 9 的一个5 排列 其排列数为P 9 5 其中7和9相邻的排列数为 c 7 3 4 2 4 2 P 7 3 满足题目要求的5位数个数为 1 2圆排列 1 2排列 定义1 2 1 2 2圆排列 定理1 2 设A an 从A中取r个 0 r n 元素按某种顺序 如逆时针 排成一个圆圈 称为圆排列 循环排列 设A an A的r圆排列个数为P n r r 证明 由于把一个圆排列旋转所得到另一个圆排列视为相同的圆排列 因此线排列a1a2 ar a2a3 ara1 ara1a2 ar 1在圆排列中是一个 即一个圆排列可产生r个不同的线排列 同理 r个不同的线排列对应一个圆排列 而总共有P n r 个线排列 故圆排列的个数为P n r r n r n r 证毕 1 2圆排列例4 1 2排列 例题 1 2 2圆排列 例4 有8人围圆桌就餐 问有多少种就座方式 如果有两人不愿坐在一起 又有多少种就座方式 解 由上述定理知8人围圆桌就餐 有8 8 7 5040种就座方式 又有两人不愿坐在一起 不妨设此二人为A B 当A B坐在一起时 相当于7人围圆桌就餐 有7 7 6 种就座方式 而A B坐在一起时 又有两种情况 或者A在B的左面 或者A在B的右面 因此A B坐在一起时 共有2 6 种就座方式 因此如果有两人不愿坐在一起 就座方式为7 2 6 5 6 3600 1 2圆排列例5 1 2排列 例题 1 2 2圆排列 例5 4男4女围圆桌交替就座有多少种就座方式 解 显然 这是一个圆排列问题 首先让4个男的围圆桌就座 有4 4 3 种就座方式 因为要求男女围圆桌交替就座 在男的坐定后 两两之间均需留有一个空位 女的就座相当于一个4元素集合的全排列 就座方式数为4 由乘法法则知 就座方式数为3 4 144 1 2重排列 1 2排列 定义1 3 1 2 3重排列 集合论定义 定理1 3 从n个不同元素中 可重复选取r个按一定顺序排列起来 称为重排列 从重集B k1 b1 k2 b2 kn bn 中选取r个按一定顺序排列起来 重集B b1 b2 bn 的r 排列的个数为nr 证明 构造B的r 排列如下 选择第一项时可从n个元素中任选一个 有n种选法 选择第二项时由于可以重复选取 仍有n种选法 同理 选择第r项时仍有n种选法 根据乘法法则 可得出r 排列的个数为nr 证毕 1 2重排列例6 1 2排列 例题 1 2 3重排列 例6 由数字1 2 3 4 5 6这六个数字能组成多少个五位数 又可组成多少大于34500的五位数 解 一个五位数的各位数字可重复出现 是一个典型的重排列问题 相当于重集B 1 2 6 的5 排列 所求的五位数个数为65 7776 大于34500的五位数可由下面三种情况组成 万位选4 5 6中的一个 其余4位相当于重集B的4 排列 由乘法法则知 共有3 64个五位数 万位是3 千位5 6中的一个 其余3位相当于重集B的3 排列 由乘法法则知 共有2 63个五位数 万位是3 千位4中的一个 百位选5 6中的一个 其余2位相当于重集B的2 排列 由乘法法则知 共有2 62个五位数 由加法法则知 大于34500的五位数个数为3 64 2 63 2 62 4392 1 2重排列计数 1 2排列 1 2 3重排列 定理1 4 重集B n1 b1 n2 b2 nk bk 的全排列个数为 证明 将B中的ni个bi看作不同的ni个元素 赋予上标1 2 ni 即 如此 重集B就变成具有n1 n2 nk n个不同的元素集合显然 集合A的全排列个数为n 又由于ni个bi赋予上标的方法有ni 种 于是对重集B的任一个全排列 都可以产生集合A的n1 n2 nk 个排列 由乘法法则 故重集B的全排列个数为证毕 注 利用组合数的计数方法同样可以得出证明 1 2重排列例7 1 2排列 1 2 3重排列 例题 例6 有四面红旗 三面蓝旗 二面黄旗 五面绿旗可以组成多少种由14面旗子组成的一排彩旗 解 这是一个重排列问题 是求重集 4 红旗 3 蓝旗 2 黄旗 5 绿旗 的全排列个数 根据定理 一排彩旗的种数为 1 2重排列例8 1 2排列 1 2 3重排列 例题 例8 用字母A B C组成五个字母的符号 要求在每个符号里 A至多出现2次 B至多出现1次 C至多出现3次 求此类符号的个数 解 这也是一个重排列问题 根据分析 符合题意的符号个数相当于求重集M 2 A 1 B 3 C 的5 排列个数 可分为三种情况 需要分别求M A M B 和M C 的全排列个数 根据加法法则 此类符号个数为 1 2项链排列 1 2排列 定义1 4 1 2 4项链排列 对圆排列 通过转动 平移 翻转 可重合的 即可看作项链排列 如n个不同元素的r 项链排列个数为P n r 2 r 具体参照P lya定理 1 3无重组合 1 3组合 定义1 5 1 3 1 无重 组合 集合论定义 定理1 5 设A an 从A中选择r个 0 r n 元素组合起来 A的r 无序子集 A的r 组合 如r n 有C n r P n r r n r n r 如n r 0 C n r 1 如n r C n r 0 从n个不同元素中 取r个 0 r n 不考虑顺序组合起来 其组合数C n r 或 证明 从n个不同元素中取r个元素的组合数为C n r 而r个元素可组成r 个r 排列 即一个r 组合对应r 个r 排列 于是C n r 个r 组合对应r C n r 个r 排列 这是从n个不同元素中取r个元素的r 排列数P n r 因此有 1 3无重组合推论1 1 3组合 1 3 1 无重 组合 三个推论 推论1 5 1 C n r C n n r 证明 实际上 从n个不同元素中选出r个元素的同时 就有n r个元素没有被选出 因此选出r个元素的方式数等于选出n r个元素的方式数 即C n r C n n r 得证 另外 也可通过计算得出证明如下 1 3无重组合推论2 1 3组合 1 3 1 无重 组合 三个推论 推论1 5 1 C n r C n n r 推论1 5 2 Pascal公式 C n r C n 1 r C n 1 r 1 证明 利用组合分析法 在集合A的n个不同元素中固定一个元素 不妨设为a1 从n个元素中选出r个元素的组合由下面两种情况组成 r个元素中包含a1 相当于从除去a1的n 1个元素中选出r 1个元素的组合 再加上a1而得到 组合数为C n 1 r 1 r个元素中不包含a1 相当于从除去a1的n 1个元素中选出r个元素的组合而得到 组合数为C n 1 r 由加法法则即得C n r C n 1 r C n 1 r 1 另外 也可通过计算得出证明如下 1 3无重组合推论3 1 3组合 1 3 1 无重 组合 三个推论 推论1 5 1 C n r C n n r 推论1 5 2 Pascal公式 C n r C n 1 r C n 1 r 1 推论1 5 3 C n r C n 1 r 1 C n 2 r 1 C r 1 r 1 证明 反复利用Pascal公式 即可证明 或利用组合分析法 在集合A an 的n个不同元素选出r个元素的组合可分为以下多种情况 如r个元素中包含a1 相当于从除去a1的n 1个元素中选出r 1个元素的组合 再加上a1而得到 组合数为C n 1 r 1 如r个元素中不包含a1但包含a2 相当于从除去a1 a2的n 2个元素中选出r 1个元素的组合 再加上a2而得到 组合数为C n 2 r 1 同理如r个元素中不包含a1 a2 an r 但包含an r 1 相当于从剩下的r 1个元素中选出r 1个元素的组合 再加上an r 1而得到 组合数为C r 1 r 1 由加法法则得C n r C n 1 r 1 C n 2 r 1 C r 1 r 1 1 3无重组合例1 1 3组合 1 3 1 无重 组合 例题 例1 有5本日文书 7本英文书 10本中文书 从中取两本不同文字的书 问有多少种方案 若取两本相同文字的书 问有多少种方案 任取两本书 有多少种方案 解 从三种文字的书中取两种共有C 3 2 3种取法 根据乘法法则有 日英各一本的方法数为5 7 35 中英各一本的方法数为10 7 70 中日各一本的方法数为10 5 50 由加法法则得35 70 50 155取两本相同文字的 有两本中文 两本英文或两本日文三种方式 由加法法则得C 5 2 C 7 2 C 10 2 76任取两本书 相当于从5 7 10 22本书中取两本的组合 即C 22 2 231 1 3无重组合例2 1 3组合 1 3 1 无重 组合 例题 例2 从1 300之间任取3个不同的数 使得这3个数的和正好被3除尽 问共有几种方案 解 所有的整数可分为以下3个分类 模3余0 模3余1和模3余2 故1 300的300个数可以分为3个集合 A 1 4 298 B 2 5 299 C 3 6 300 任取3个数其和正好被3整除的情况如下 三个数同属于集合A 有C 100 3 种方案 三个数同属于集合B 有C 100 3 种方案 三个数同属于集合C 有C 100 3 种方案 三个数分别属于集合A B C 由乘法法则有1003种方案 由加法法则得 所求的方案数为3 C 100 3 1003 1485100 1 3无重组合例3 1 3组合 1 3 1 无重 组合 例题 例3 某车站有1到6个入口处 每个入口处每次只能进一个人 问一小组9个人进站的方案数有多少 解I 按照从入口1到入口6的顺序可得到9个人一个排列 再把两个入口间设上一个标志 加上这5个标志相当于每一个排列有14个元素 其中5个标志没有区别 但其位置将区分各入口的进站人数 相当于14个元素集合的5 组合 故进站方案数为9 C 14 5 726485760解II 同上分析 问题转化为重集 1 p1 1 p2 1 p9 5 标志 的全排列 pi代表9个人 i 1 9 故进站方案数为14 5 726485760解III 考虑9个人选择方案 第1个人有6种选择 第2个人除了选择入口 还要考虑在第1个人的前面或后面 故有7种选择 同理 第9个人有14种选择 根据乘法法则 故进站方案数为6 7 14 726485760 1 3无重组合例4 1 3组合 1 3 1 无重 组合 例题 例4 求5位数中至少出现一个6 而被3整除的数的个数 解 10进制数被3整除的充要条件是各位数的和能被3整除 据此可进行如下讨论 从左往右计 如最后一个6出现在个位 则十百千位各有10种选择 万位有3种可能 根据乘法法则 总个数为3 103 如最后一个6出现在十位 则个位有9种选择 百千位各有10种选择 万位有3种可能 根据乘法法则 总个数为3 102 9 如最后一个6出现在百位 则个十位各有9种选择 千位有10种选择 万位有3种可能 根据乘法法则 总个数为3 10 92 如最后一个6出现在千位 则个十百位各有9种选择 万位有3种可能 根据乘法法则 总个数为3 93 如最后一个6出现在万位 则个十百位各有9种选择 千位有3种可能 根据乘法法则 总个数为3 93 根据加法法则 符合条件的整数个数为3 103 3 102 9 3 10 92 3 93 3 93 12504 1 3无重组合例5 1 3组合 1 3 1 无重 组合 例题 例5 求1000 的末尾有几个零 解 此问题在于求将1000 分解为素数的乘积时 2和5的幂是多少 末尾零的个数应该等于2和5的幂中较小的那个数 1 1000中5的倍数的数共200个 其中有40个52的倍数 这40个数中有8个53的倍数 而这8个数中又有1个54的倍数 故1000 分解为素数的乘积时 5的幂应该是200 40 8 1 249显然 2的幂必然大于249 因此1000 的末尾有249个零 1 3无重组合例6 1 3组合 1 3 1 无重 组合 例题 例6 求能除尽1400的正整数数目 1除外 其中包含多少个奇数 解 1400 23527 故除尽1400的正整数分解为素数的乘积的形式应该为2l5m7n 其中0 l 3 0 m 2 0 n 1 但应排除l m n 0的情况 故满足条件的数目为 3 1 2 1 1 1 1 23其中包含的奇数为 1 2 1 1 1 1 5 1 3重复组合 1 3组合 定义1 6 1 3 2重复组合 集合论定义 定理1 6 从n个不同元素中 可重复选取r个不考虑顺序组合起来 其组合数F n r 从重集B k1 b1 k2 b2 kn bn 中取r个元素不考虑顺序的组合 重集B b1 b2 bn 的r 组合数F n r C n r 1 r 证明 设n个元素b1 b2 bn和自然数1 2 n一一对应 于是任何组合皆可看作是一个r个数的组合 c1 c2 cr 由于是组合 不妨认为各ci是按照大小顺序排列的 相同的ci连续排在一起 不妨设c1 c2 cr 又令di ci i 1 i 1 2 r 即d1 c1 d2 c2 1 dr cr r 1 因1 ci n 故1 di n r 1 得到一个集合 1 2 n r 1 的r 组合 d1 d2 dr d1 d2 dr 显然有一种 c1 c2 cr 的取法 就有一种 d1 d2 dr 的取法 反之亦然 这两种取法是一一对应的 从而这两种取法是等价的 如此 从n个不同元素中可重复选取r个的组合数 和从n r 1个不同元素中不重复选取r个的组合数是相同的 故F n r C n r 1 r 1 3重复组合例7 1 3组合 定理1 7 1 3 2重复组合 例题 r个无区别的球放入n个有标志的盒子里 每盒的球数可多于1个 则共有F n r 种方案 例7 试问 x y z 4的展开式有多少项 证明 这是一个允许重复组合的典型问题 实质上定理1 6的另一种说法 由于每盒的球数不受限制 相当于重集 a1 a2 an 的r 组合 解 x y z 4展开式每一项都是4次方的 相当于从3个不同元素中可以重复的选择4个 或者相当于将4个无区别的球放到3个有标志的盒子里 故展开项个数为F 3 4 C 3 4 1 4 15 1 3重复组合例8 9 1 3组合 例题 1 3 2重复组合 例8 某餐厅有7种不同的菜 为了招待朋友 一个顾客需要买14个菜 问有多少种买法 例9 求n个无区别的球放入r个有标志的盒子里 n r 而无一空盒的方案数 解 这个问题相当于重集 1 2 7 的14 组合 根据定理1 6知买菜的方法数为F 7 14 C 7 14 1 14 4845 解 由于每个盒子不能为空 故每个盒子里可先放一个球 这样还剩n r个球 再将这n r个球防到r个盒子里 由于这时每盒的球数不受限制 相当于重集 a1 a2 ar 的n r 组合 根据定理1 6知 其组合数为F r n r C r n r 1 n r C n 1 r 1 1 3重复组合例10 1 3组合 例题 1 3 2重复组合 例10 在由数0 1 9组成的r位整数所组成的集合中 如果将一个整数重新排列得到另一个整数 则称这两个整数是等价的 那么 有多少不等价的整数 如果0和9最多只能出现一次 又有多少不等价的整数 解 分析题意知 一个r位整数只和所取的数字有关 与其顺序无关 因而是个组合问题 又每一整数的每一位可从0 1 9中任取 故不等价的r位整数相当于重集 0 1 9 的r 组合 根据定理1 6知 其组合数为F 10 r C 10 r 1 r C 9 r r 0和9最多只出现一次 可分为三种情况 均不出现时相当于重集B 1 2 8 的r 组合 组合数为F 8 r C r 7 r 只出现其一 若0出现 相当于B的r 1 组合 然后加入0 组合数为F 8 r 1 C r 6 r 1 同理9出现的组合数为C r 6 r 1 均出现一次 相当于B的r 2 组合 然后加入0 9 组合数为F 8 r 2 C r 5 r 2 由加法法则知 符合题意的整数个数为C r 7 r 2 C r 6 r 1 C r 5 r 2 1 3重复组合例11 1 3组合 例题 1 3 2重复组合 例11 求方程x1 x2 xn r的非负整数解的个数 其中n r为正整数 解 设重集B b1 b2 bn B的任一个r 组合都具有形式 x1 b1 x2 b2 xn bn 其中xi i 1 2 n 是非负整数且满足方程x1 x2 xn r 反之 每一个满足方程x1 x2 xn r的非负整数解x1 x2 xn都对应重集B的一个r 组合 因此 方程x1 x2 xn r的非负整数解的个数就等于重集B的r 组合数F n r 1 3不相邻组合 1 3组合 3 1 3组合 定义1 7 1 3 3不相邻组合 定理1 8 从序列A 1 2 n 个中选取r个 其中不存在i i 1两个相邻的数同时出现于一个组合的组合 从序列A 1 2 n 个中选取r个作不相邻的组合 其组合数为C n r 1 r 证明 设 d1 d2 dr 是所求的一个不相邻组合 不妨设d1 d2 dr 令ci di i 1 i 1 2 r 即c1 d1 c2 d2 1 cr dr r 1 因1 di n 故1 ci n r 1 得到一个集合 1 2 n r 1 的r 组合 显然有一种 d1 d2 dr 的取法 就有一种 c1 c2 cr 的取法 反之亦然 集合 1 2 n r 1 的一个r 组合 c1 c2 cr 不妨设c1 c2 cr 令di ci i 1 i 1 2 r 即d1 c1 d2 c2 1 dr cr r 1 因1 ci n r 1 故1 di n 得到一个集合 1 2 n 的不相邻组合 d1 d2 dr 显然有一种 c1 c2 cr 的取法 就有一种 d1 d2 dr 的取法 故这两种取法是一一对应的 从而这两种取法是等价的 从n个不同元素中可选取r个的不相邻组合数 和从n r 1个不同元素中选取r个的组合数是相同的 即C n r 1 r 1 4二项式定理 1 4二项式定理 定理1 9 证明 因为 x y n x y x y x y 等式右端有n个因子 项xkyn k是从这n个因子中选取k个因子 k 0 1 n 在这k个 x y 里都取x 而从剩下的n k个因子 x y 中选取y作乘积得到 因此xkyn k的系数为上述选法的个数C n r 故有证毕 注 可用数学归纳法证明 证明略 C n k 又称二项式系数 1 4二项式定理推论1 1 4二项式定理 四个推论 推论1 9 1 推论1 9 2 推论1 9 3 证明 在推论1 9 2中令x 1 即可得证 利用组合分析 等式左端相当于从A an 中任意选择k 0 k n 个元素的所有可能数目 即对n个元素 每一个都有被选择和不被选择的可能 总的可能数为2n 另外 该等式还表明A的所有子集个数为2n 1 4二项式定理推论2 1 4二项式定理 四个推论 推论1 9 1 推论1 9 2 推论1 9 3 推论1 9 4 证明 在推论1 9 2中令x 1 即可得证 另外 该等式还表明A an 的偶数子集个数和奇数子集个数相等 1 4广义二项式定理 1 4二项式定理 定理1 10 定义1 8 广义二项式系数为 牛顿二项式定理 1 4广义二项式定理推论1 1 4二项式定理 六个推论 推论1 10 1 推论1 10 2 证明 1 4广义二项式定理推论2 1 4二项式定理 六个推论 推论1 10 1 推论1 10 2 推论1 10 3 推论1 10 4 推论1 10 5 证明 当 1 2时 C 0 1 而对于k 0 有将上式代入推论1 10 1即可得证 1 4广义二项式定理推论3 1 4二项式定理 六个推论 推论1 10 1 推论1 10 2 推论1 10 3 推论1 10 4 推论1 10 5 推论1 10 6 1 5组合恒等式及其含义1 1 5组合恒等式及其含义 恒等式1 如n k N 有C n k n k C n 1 k 1 证明 从n个元素中取k个的组合可先从n个元素中取1个 再从剩下的n 1个元素中选择k 1个 组合数为C n 1 k 1 选出的k个元素都有可能被第一次选中 因是组合 故重复度为k 得证 或通过计算证明 1 5组合恒等式及其含义2 1 5组合恒等式及其含义 恒等式2 证明 考虑盒子1中有n个有区别的球 从中取一个球放入盒子2中 再取任意多个球放入盒子3中 等式左端表示先从盒子1中取k k 1 2 n 个球 再从中取一个放入盒子2中 剩下的k 1个球放入盒子3中 等式右端表示先从盒子1中取一个放入盒子2中 剩下的n 1个球是否放入盒子3中均有两种可能 显然两种取法结果是一样的 得证 或通过计算证明 1 5组合恒等式及其含义3 1 5组合恒等式及其含义 恒等式3 证明 将等式两边对x微分得在上式中 令x 1得即得证 注 如令x 1 即可证明恒等式2 1 5组合恒等式及其含义4 5 1 5组合恒等式及其含义 恒等式5 恒等式4 证明 将等式两边对x微分得将等式两边同乘以x后再对x微分得在上式中 令x 1得得证 注 如令x 1 即可证明恒等式5 1 5组合恒等式及其含义6 1 5组合恒等式及其含义 恒等式6 证明 将等式两边对x从0到1积分得即得证 恒等式7 Vandermonde恒等式 如n m N且r min m n 有C m n r C m 0 C n r C m 1 C n r 1 C m r C n 0 1 5组合恒等式及其含义7 1 5组合恒等式及其含义 证明 设A am B bn 且A B 则A B C有m n个元素 C的r 组合个数为C m n r 而C的每个r 组合无非是先从A中取k个元素 再从B中取出r k个元素组成 k 0 1 r 由乘法法则共有C m k C n r k 种取法 再由加法法则即可得证 或通过比较系数法证明 比较等式两边xr的系数即可得证 1 5组合恒等式及其含义8 9 1 5组合恒等式及其含义 恒等式8 恒等式9 恒等式7 Vandermonde恒等式 如n m N且r min m n 有C m n r C m 0 C n r C m 1 C n r 1 C m r C n 0 1 5组合恒等式及其含义10 11 1 5组合恒等式及其含义 恒等式10 如p q n Z且p q n 0 有 恒等式11 如p q n Z且p q n 0 有 1 5组合恒等式及其含义12 1 5组合恒等式及其含义 恒等式12 证明 利用组合分析法 在集合A an 1 的n 1个不同元素选出k 1个元素的组合可分为以下多种情况 如k 1个元素中包含a1 相当于从除去a1的n个元素中选出k个元素的组合 组合数为C n k 如不包含a1但包含a2 相当于从除去a1 a2的n 1个元素中选出k个元素的组合 再加上a2而得到 组合数为C n 1 k 同理如不包含a1 a2 an k 1 但包含an k 2 相当于从剩下的k个元素中选出k个元素的组合 再加上an k 2而得到 组合数为C k k 注意 i k时 C k k 0 由加法法则得或对固定的k 对n使用归纳法 当n 0时 有可见 当n 0时 等式成立 如对任意n等式成立 则有可见等式对n 1也成立 由归纳原理 得证 1 5组合恒等式及其含义13 1 5组合恒等式及其含义 恒等式13 证明 注意 这个恒等式与前面的有一个很不一样的地方 就是C j j C k 1 k 是广义的二项式系数 根据广义的二项式系数的定义 Pascal公式C k C 1 k C 1 k 1 对实数 和整数k同样成立 与恒等式1类似 反复使用Pascal公式即可得证 1 5组合恒等式及其含义14 1 1 5组合恒等式及其含义 恒等式14 如n r N 有C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 证明I 反复利用Pascal公式 即可证明 或利用组合分析法 在集合A an r 1 的n r 1个不同元素选出r个元素的组合可分为以下多种情况 如r个元素中不包含a1 相当于从除去a1的n r个元素中选出r个元素的组合 组合数为C n r r 如r个元素中包含a1但不包含a2 相当于从除去a1 a2的n r 1个元素中选出r 1个元素的组合 再加上a1而得到 组合数为C n r 1 r 1 同理如r个元素中包含a1 a2 ar 1 但不包含ar 相当于从剩下的n 1个元素中选出1个元素的组合 再加上a1 a2 ar 1而得到 组合数为C n 1 1 如r个元素中包含a1 a2 ar 相当于从剩下的n个元素中选出0个元素的组合 组合数为C n 0 由加法法则得C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 1 5组合恒等式及其含义14 2 1 5组合恒等式及其含义 恒等式14 如n r N 有C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 证明II 等式的左端可看作是在集合A an 2 的n 2个不同元素允许重复的选出r个元素的组合 可分为以下多种情况 如r个元素中不包含a1 相当于从除去a1的n 1个元素中允许重复的选出r个元素的组合 组合数为C n r r 如r个元素中只包含一个a1 相当于从除去a1的n 1个元素中允许重复的选出r 1个元素的组合 再加上a1而得到 组合数为C n r 1 r 1 如r个元素中包含两个a1 相当于从除去a1的n 1个元素中允许重复的选出r 2个元素的组合 再加上两个a1而得到 组合数为C n r 2 r 2 同理如r个元素中包含r个a1 其组合数为C n 0 由加法法则得C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 1 5组合恒等式及其含义15 1 5组合恒等式及其含义 恒等式15 如n l r N l r 有C n l C l r C n r C n r l r 证明 等式的左端可看作是先从n个元素中取l个的组合 从所得的l个元素中再选择r个组合 由此形成了三个组合 所得的全部结果相当于直接从n个元素中取r个的组合 再从剩下的n r个元素中选择l r个 得证 或通过计算证明 1 5组合恒等式证明方法 1 5组合恒等式及其含义 常用的证明方法 数学归纳法二项式系数公式 特别是Pascal公式比较级数展开式中的系数 二项式定理或母函数法 积分微分法组合分析法 1 6模型转换方法 1 6模型转换 问题的分析注意事项 分析对象属性合理分类明确分步模型转换 如排列 组合 一一对应 计数的难易程度方式的转换1 11 一组 等价 1 6模型转换例1 1 6模型转换 例题 例1 在100名选手之间进行淘汰赛 即一场的比赛结果 失败者退出比赛 最后产生一名冠军 问要举行几场比赛 证明 第1轮要进行50场比赛 留下50名选手 第2轮要进行25场比赛 留下25名选手 第3轮要进行25场比赛 1名轮空 留下13名选手 第4轮要进行6场比赛 1名轮空 留下7名选手 第5轮要进行3场比赛 1名轮空 留下4名选手 第6轮要进行2场比赛 留下2名选手 最后一场决赛 产生1名冠军 根据加法法则 共需要进行50 25 12 6 3 2 1 99场比赛 其实 最后产生1名冠军需要淘汰99人 一场比赛淘汰1人 两者一一对应 需要99场比赛进行 1 6模型转换例2 1 1 6模型转换 格路问题 例2 简单格路问题从 0 0 点出发沿X轴或Y轴的正方向每步走一个单位 最终走到 m n 点 有多少条路径 解 设从 0 0 点水平方向向前进一步为x 垂直方向向上进一步为y 于是从 0 0 点到 m n 点 水平方向走m步 垂直方向走n步 一条从 0 0 点到 m n 点的路径与重集 m x n y 的一个全排列一一对应 故所求路径数为 m n m n C m n m 另外 垂直方向需要走n步 相当于在X轴0 1 m共m 1个端点处重复的选择n个位置向上走 与一条从 0 0 点到 m n 点的路径一一对应 故所求路径数为F m 1 n C m n n 1 6模型转换例2 2 1 6模型转换 格路问题 另外 一条从 0 0 点到 m n 点的路径可分为两类情况 一种是从 0 0 点到 m n 1 点的路径 另一种是从 0 0 点到 m 1 n 1 点的路径 根据上述结论 有C m n n C m n 1 m C m n 1 m 1 这是Pascal公式的另一种形式 例2 简单格路问题从 0 0 点出发沿X轴或Y轴的正方向每步走一个单位 最终走到 m n 点 有多少条路径 1 6模型转换例3 1 6模型转换 格路问题 证明 这是上一小节的组合恒等式 等式左端表示从 0 0 点到 n 1 r 点的路径数 右端第1项表示从 0 0 点到 n r 点的路径数 右端第2项表示从 0 0 点到 n r 1 点的路径数 右端最后1项表示从 0 0 点到 n 0 点的路径数 这说明从 0 0 点到 n 1 r 点的路径根据是否经过 n i 到 n 1 i i 0 1 r 可分为r 1类 根据加法法则即可得证 例3 如n r N 有C n r 1 r C n r r C n r 1 r 1 C n 1 1 C n 0 1 6模型转换例4 1 6模型转换 格路问题 例4 如n N 有C n 0 C n 1 C n n 2n 组合含义 这是推论1 9 3 等式左端第1项表示从 0 0 点到P 0 n 点的路径数 第2项表示从 0 0 点到P1 1 n 1 点的路径数 左端最后1项表示从 0 0 点到Q n 0 点的路径数 这说明从 0 0 点到PQ上各格子点的路径总和为2n 也说明2n个人从 0 0 点出发 每到一个十字路口便分成两组 直至到达PQ线为止 能保证每个人所走的路径不同 1 6模型转换例5 1 6模型转换 格路问题 例5 Vandermonde恒等式如n m N r min m n 有C m n r C m 0 C n r C m 1 C n r 1 C m r C n 0 证明 等式左端表示从 0 0 点到 m n r r 点的路径数 从 0 0 点到 m n r r 点的每一条路径均穿过PQ线上的格子点 m l l l 0 1 r 从 0 0 点到 m l l 点的路径数为C m l 再从 m l l 点到 m n r r 点的路径数为C n r l 由乘法法则 从 0 0 点出发经过 m l l 点到 m n r r 点的路径数为C m l C n r l 再由加法法则 即可得证 1 6模型转换例6 1 1 6模型转换 格路问题 例6 从 0 0 点到 m n 点 m n 的 要求中间经过的每一个格子点 a b 恒满足a b关系 问有多少条路径 解 从 0 0 点到 m n 点的路径数为C m n m 但需要排除碰到或穿过y x格子点的路径数 即去掉a b的情况 第一步必须从 0 0 点到 1 0 点 因此问题等价于求从 1 0 点到 m n 点的路径数 因为m n 故从 0 1 点到 m n 点的路径必然穿过y x上的格子点 下面建立从 0 1 点到 m n 点的每一条路径 与从 1 0 点到 m n 点但经过y x上的格子点的路径时一一对应的 1 6模型转换例6 2 1 6模型转换 格路问题 若从 0 1 点到 m n 点的路径与y x的交点从左往右数最后一个是P 作从 1 0 点到P点关于y x的与上述 0 1 点到P点的路径对称的一条路径 于是从 0 1 点到 m n 点的一条路径 就有一条从 1 0 点到 m n 点但经过y x上的格子点的路径与之对应 反之 一条从 1 0 点到 m n 点但经过y x上的格子点的路径 必存在一条从 0 1 点到 m n 点的一条路径与之对应 故所求的路径数为C m n 1 n C m n 1 n 1 m n m n 1 m n 例6 从 0 0 点到 m n 点 m n 的 要求中间经过的每一个格子点 a b 恒满足a b关系 问有多少条路径 第1章小结 本章小结 本章讨论了基本的组态 满足一定条件的优先集合的安排 的计数问题 主要用加法法则和乘法法则解决最基本的几种组合模型 包括排列 线排列 圆排列 重排列 项链排列 组合 无重组合 重复组合 的计数问题 并介绍了二项式系数 广义二项式系数 多项式系数 及证明的组合恒等式的几种不同证明方法 重点是要掌握如何使用基本的组合模型来证明组合恒等式 要特别注意如何利用合理分类和组合模型的转换进行组合计数 第1章习题 习题 P221 6 8 10 11 14 16 20 22 第2章鸽笼原理 回顾前一章 计数 本章重点介绍鸽笼原理及其在排列组合中的 存在性 应用 例子 意义鸽笼原理 排列组合组合恒等式 2 1鸽笼原理定理 2 1鸽笼原理 定理2 1 鸽笼原理 抽屉原理 若把n 1个物体放到n n 1 个盒子中去 则至少有一个盒子放有至少2个物体 证明 用反证法证明 如果n个盒子中每个盒子至多放入一个物体 则放入n个盒子中的物体总数至多为n个 这与假设有n 1个物体矛盾 从而定理得证 注 鸽笼原理只指出了至少存在这样的盒子 并没有给出 确定哪一个盒子有此性质的方法 因此 它只能用来解决存在性问题 4 4 0 0 3 1 0 2 2 0 2 1 1 2 1鸽笼原理例1 2 3 2 1鸽笼原理 例题 例1 一年有365天 今有366个人 则其中至少有两个人生日相同 证明 此例中把 天 当作盒子 相当于365个盒子放入366个物体 得证 例2 抽屉里有10双相同的手套 从中取11只出来 其中至少有两只是完整配对的 证明 此例中把 每双手套 当作盒子 相当于10个盒子放11个物体 得证 例3 一个教师每周上7次