现代工程数学第1部分(10月9日).pdf

现代工程数学 主讲教师 王钢 Email gwang 2012年10月 1 引言引言 思考 思考 如果一个房间里有如果一个房间里有23个或个或23个以上的人 那么至少有 两个人的生日相同的概率是多大呢 个以上的人 那么至少有 两个人的生日相同的概率是多大呢 2 生日悖论 如果一个房间里有如果一个房间里有23个或个或23个以上的人 那么至少有两个 人的生日相同的概率要大于 个以上的人 那么至少有两个 人的生日相同的概率要大于50 对于超过 对于超过57个人 这种 概率要大于 个人 这种 概率要大于99 这个数学事实与一般直觉相抵触 称得上是一个悖论 这个数学事实与一般直觉相抵触 称得上是一个悖论 计算与此相关的概率被称为生日问题 在这个问题之后的 数学理论已被用于设计著名的密码攻击方法 生日攻击 计算与此相关的概率被称为生日问题 在这个问题之后的 数学理论已被用于设计著名的密码攻击方法 生日攻击 4 5 6 7 引言引言 思考 现代工程数学应包括哪些内容 思考 现代工程数学应包括哪些内容 1 离散化离散化 2 随机化随机化 3 近似化近似化 4 最优化最优化 5 8 组合数学 9 课程简介课程简介 相关课程 使用教材 相关课程 使用教材 数学分析 高等代数 书名 组合数学引论 第 数学分析 高等代数 书名 组合数学引论 第2版 作者 许胤龙 孙淑玲 出版社 中国科学技术大学出版社 本课程针对计算机科学中的一个重要学科 版 作者 许胤龙 孙淑玲 出版社 中国科学技术大学出版社 本课程针对计算机科学中的一个重要学科 组合数学 组合数学是数学的一个分支 它研究事物在结定模式下的配 置 研究这种配置的存在性 所有可能配置的计数和分类以 及配置的各种性质 组合数学在计算机科学中有着极其广泛 的应用 组合学问题求解方法层出不穷 干变万化 应以理解为 基础 善于总结各种技巧 掌握科学的组织和推理方法 组合数学 组合数学是数学的一个分支 它研究事物在结定模式下的配 置 研究这种配置的存在性 所有可能配置的计数和分类以 及配置的各种性质 组合数学在计算机科学中有着极其广泛 的应用 组合学问题求解方法层出不穷 干变万化 应以理解为 基础 善于总结各种技巧 掌握科学的组织和推理方法 组合数学 Richard A Brualdi著 机械工业出版社 组合数学 卢开澄 卢华明编著 清华大学出版社 10 目录 目录 1 引言引言 第第1章 排列与组合章 排列与组合 第第2章 二项式系数章 二项式系数 第第3章 鸽笼原理章 鸽笼原理 第第4章 容斥原理章 容斥原理 第第5章 生成函数章 生成函数 第第6章 递推关系章 递推关系 第第7章 特殊计数序列章 特殊计数序列 第第8章 线性规划章 线性规划 目录目录 11 组合数学的核心组合数学的核心 组合数学可以一般地描述为 组合数学是研究离散结构 的存在 计数 分析和优化等问题的一门科学 12 组合数学研究的中心问题 组合数学研究的中心问题 按照一定的规则来安 排有限多个对象 包括 按照一定的规则来安 排有限多个对象 包括 1 要证明或者否定它的存在 这就是要证明或者否定它的存在 这就是存在性问题存在性问题 3 如果一个组合问题有解 则往往需要给出求其某 一特定解的算法 这就是所谓的 如果一个组合问题有解 则往往需要给出求其某 一特定解的算法 这就是所谓的构造性问题构造性问题 2 如果所要求的安排存在 则可能有多少种可能的 安排方案 如何对安排的方案进行分类 这就是 如果所要求的安排存在 则可能有多少种可能的 安排方案 如何对安排的方案进行分类 这就是 计数问题计数问题 4 如果算法很多 就需要在一定的条件下找出一个 或者几个最优或近乎最优的安排方案 这就是 如果算法很多 就需要在一定的条件下找出一个 或者几个最优或近乎最优的安排方案 这就是优 化问题 优 化问题 从古老的组合游戏幻方 从古老的组合游戏幻方 8 6 5 4 2 163213 5 118 96712 415 1 13 从古老的组合游戏幻方 从古老的组合游戏幻方 816 357 492 163213 510118 96712 415141 问题 哪些n存在幻方 如果有 则构造方法如何 14 为什么研究幻方 台湾黎凯旋的 易数浅谈 中有这样的描述 从日本学习飞机知识的台湾驾驶员 第一堂 课上的就是幻方知识课 因为幻方的构造原 理与飞机上的电子回路设置密切相关 15 最早有关幻方的文字记载是中国古代数学 书 数术拾遗 那里记载了上述源自 洛书 的方图 当时称为 九宫图 我国南宋数学家杨辉称这种图为纵横图 欧洲人称之为魔术方阵或幻方 传说在公元前23世纪大禹治水的时候 在 黄河支流洛水中 浮现出一个 大乌龟 甲上背有9种花点的图案 组成一个幻方 幻方幻方 492 357 816 上图为三阶洛书 16 杨辉与奇数阶幻方的构造 我国南宋时期数学家杨辉于1275年给出了3 10 阶的幻方 这里给出他关于奇数阶幻方的构造方法 这些方法记载于他的 续古摘奇算经 上 比如 对于3阶幻方 方法是 九子斜排 上下对易 左 右相更 四维挺进 具体操作如下图 九子斜排上下对易 左右相更 四维挺进 1 42 753 86 9 9 42 357 86 1 492 357 816 17 构造奇数阶幻方 老外的方法 将1放在最上一行的中间 其后的整数沿着自左下到 右上的这条对角线按照自然顺序放置 同时作修正 在到达顶行时 下一个整数要放在底行 所放位置 就是把底行当作顶行上边一行时该数应该放置的位 置 当到达最右边的一列时 下一个整数要放在最左边 的一列上 所放位置就是把最左边的一列当作最右 边那列的右边的列时该数应该放置的位置 当要放的位置上已经填好了整数 或上一个整数已 经放在了幻方的右上角时 则当前要摆放的整数将 放在紧挨上述位置的下方 18 小结 组合数学经常使用的方法并不高深复杂 要学好组合数学并非易事 既需要一定 的数学修养 也要进行相当的训练 19 第第1章 排列与组合章 排列与组合 本章重点介绍以下的基本计数方法 本章重点介绍以下的基本计数方法 加法法则和乘法法则加法法则和乘法法则 集合的排列集合的排列 多重集合的排列多重集合的排列 集合的组合集合的组合 多重集合的组合多重集合的组合 1 1 1 加法法则 1 1 加法法则和乘法法则加法法则和乘法法则 2 相互独立相互独立的事件的事件 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是有限集合 若 且 时 则有 是有限集合 若 且 时 则有 ij ij SS I I 1 m ii i SSSS U U 11 mm ii ii SSS U U 3 1 1 加法法则例1 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 1 加法法则加法法则 例题例题 例例1 有一所学校给一名物理竞赛优胜 者发奖 奖品有三类 第一类是 有一所学校给一名物理竞赛优胜 者发奖 奖品有三类 第一类是3种不 同版本的法汉词典 第二类是 种不 同版本的法汉词典 第二类是4种不同 类型的物理参考书 第三类是 种不同 类型的物理参考书 第三类是2种不同 的奖杯 这位优胜者只能挑选一样奖 品 那么 这位优胜者挑选奖品的方 法有多少种 种不同 的奖杯 这位优胜者只能挑选一样奖 品 那么 这位优胜者挑选奖品的方 法有多少种 解 解 设设S是所有这些奖品的集合 是所有这些奖品的集合 Si是第是第i类奖品的集合类奖品的集合 i 1 2 3 显然 显然 Si Sj i j 根据加法 根据加法法则法则有有 i i SSSSS 3 123 1 3429 U U 4 1 1 加法法则例2 3 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 1 加法法则加法法则 例题例题 例例2 大于大于0小于小于10的奇偶数 有多少个 的奇偶数 有多少个 例例3 小于小于20可被可被2或或3整除的自然 数有多少个 整除的自然 数有多少个 解 解 设设S是符合条件数的集合 是符合条件数的集合 S1 S2分别是符合条件的 奇数 偶数集合 显然 分别是符合条件的 奇数 偶数集合 显然 S1 S2 根据加法 根据加法法则法则有有 SSS 12 549 5 若若 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 种 种 集合论定义集合论定义 设是有限集合 且 则有 设是有限集合 且 则有 11 mm ii ii SSS 1 m i i SS 1 2 i S im 12 1 2 mii a aaaS im 6 1 1 乘法法则例4 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 2 乘法法则乘法法则 例题例题 例例4 从从A 地到地到B地有地有2条不同的道路 从 条不同的道路 从B地到地到C地有地有4条不同的道路 而从条不同的道路 而从 C地到地到D地有地有3条不同的道路 求从条不同的道路 求从A 地经地经B C两地到达两地到达D地的道路数 地的道路数 解 解 设设S是所求的道路数集合 是所求的道路数集合 S1 S2 S3分别是从分别是从A到 到 B 从 从B到到C 从 从C到到D的道路集合 根据乘法的道路集合 根据乘法法则 法则有有 SSSS 123 2 4 324 7 1 1 乘法法则例5 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 2 乘法法则乘法法则 例题例题 例例5 由数字由数字1 2 3 4 5可以构成多少个 所有数字互不相同的四位偶数 可以构成多少个 所有数字互不相同的四位偶数 解 解 所求的是四位偶数 故个位只能选所求的是四位偶数 故个位只能选2或或4 有两种选 择方法 又由于要求四位数字互不相同 故个位选中后 十位只有四种选择方法 同理 百位 千位分别有三种 两种选择方法 根据乘法 有两种选 择方法 又由于要求四位数字互不相同 故个位选中后 十位只有四种选择方法 同理 百位 千位分别有三种 两种选择方法 根据乘法法则 四位数互不相同的偶数 个数为 法则 四位数互不相同的偶数 个数为 2 4 3 2 48 8 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 9 1 1 乘法法则 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 3 减法法则减法法则 集合论定义集合论定义 设 A 是有限集合 U 的子集 A 的补集 则 A 的元素个数 A 由以下公式给出 AxUxA AUA 例求小于10000的含1的正整数的个数 解 全部4位数有104个 不含1的四位数有94个 含1的4位数为两 个的差 104 94 3439个 10 1 1 乘法法则 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 4 除法法则除法法则 集合论定义集合论定义 如果有限集 S 被分成包含同样多个元素的 k 部分 那么部分的数目 k 由以下公式给 出 例 在一排鸽巢中有740只鸽子 如果每个鸽巢中有5只鸽子 那 么鸽巢的数目为740 5 148 数在一个部分中的元素个 S k 11 1 1 乘法法则 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 5 相等原理相等原理 集合论定义集合论定义 如果在集合 A 和 B 之间存在一一对应 则 A B 例例 n 元集 S 1 n 的子集个数等于由 0 和 1 组成的长度为 n 的串的个数 证明证明 可在 S 的子集的集合与由 0 和 1 组成的长度为 n 的串的集 合之间建立一一对应如下 让 S 的每个子集 A 对应串 a1 an 其中对于每个 i S Ai Ai ai 若 若 0 1 12 1 1 乘法法则 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 6 实例实例 解法解法1 采用加法原理 1 一位数 5 2 二位数 若十位为 5 则个位有 9 种取法 若个位为 5 则十 位有 8 种取法 不能取 0 共有 9 8 17 个二位数 3 三位数 若百位为 5 则十位和个位各有 9 种取法 若十 个 位为 5 则百位有 8 种取法 不能取 0 个 十 位 有 9 种取法 共有 9 9 2 8 9 225 个三位数 4 四位数 若千位为 5 则百位 十位 个位各有 9 种取法 若百 十 个 位为 5 则千位有 8 种取法 不能取 0 其余 各位各有 9 种取法 共有 9 9 9 3 8 9 9 2 673 个四位 数 总共有 1 17 225 2 673 2 916 个数 恰有一位数字是恰有一位数字是 5 的的 10 000 的正整数有多少个 的正整数有多少个 13 1 1 乘法法则 1 1 加法法则和乘法法则加法法则和乘法法则 1 1 6 实例实例 解法解法2 采用乘法原理 将每个数都看作四位数 例如 将 1 看 作 0001 某位数字是 5 其余位有 9 种选择 数字 5可以在个 十 百 千位 所以满足条件的数总共有 4 9 9 9 2916 个 恰有一位数字是恰有一位数字是 5 的的 广义广义二项式系数为 二项式系数为 kk k R x yxyx y k 0 1 如有如有 5 证明 具体证明略 方法是泰勒展开 核心是要保证收敛 性 证明 具体证明略 方法是泰勒展开 核心是要保证收敛 性 所以条件限制所以条件限制 x y 1 1 4 广义二项式定理推论1 1 4 二项式定理二项式定理 六个推论六个推论 推论推论1 10 1 课本 课本p54 定理定理3 1 2 推论推论1 10 2 k k zzz k 0 1 1 有有 nkk k nk zzz k 0 1 1 1 1 有有 证明 证明 00 0 0 1 1 1 1 1 1 1 1 nkk kk k k k kk k nnnk n zzz k k n nnk z k nk z k 6 1 4 广义二项式定理推论2 1 4 二项式定理二项式定理 六个推论六个推论 推论推论1 10 1 推论 推论1 10 2 推论 推论1 10 3 推论 推论1 10 4 推论 推论1 10 5 k k zzz k 0 1 1 有有 nkk k nk zzz k 0 1 1 1 1 有有 kk k zzz 1 0 1 1 1 有有 k k zzz 1 0 1 1 有有 k k k k k zzz k k 1 21 1 1 22 1 11 1 2 有有 证明 证明 当当 1 2时 时 C 0 1 而对于 而对于k 0 有 将上式代入推论 有 将上式代入推论1 10 1即可得证 即可得证 1 1 1 212 1 21 1 2 1 21 1 21 1 1 3 23 2 1 1 2 3 4 23 22 22 4 22 1 22 2 1 1 22 1 2 k k k k k k k k k k k k k kk kk k kk k k k 7 1 4 广义二项式定理推论3 1 4 二项式定理二项式定理 六个推论六个推论 推论推论1 10 1 推论 推论1 10 2 推论 推论1 10 3 推论 推论1 10 4 推论 推论1 10 5 推论 推论1 10 6 k k zzz k 0 1 1 有有 nkk k nk zzz k 0 1 1 1 1 有有 kk k zzz 1 0 1 1 1 有有 k k zzz 1 0 1 1 有有 k k k k k zzz k k 1 21 1 1 22 1 11 1 2 有有 nkk k rzzr r nk rzr z k 0 1 1 0 1 1 即是非 常数 有即是非 常数 有 8 1 4 广义二项式定理推论1 1 4 二项式定理二项式定理 牛顿二项式定理的应用牛顿二项式定理的应用 9 1623 3 62 13 3 1 3 13 10 3 9 12 3 2 1 2 1 2 9 12 1 2 1 9 1 2 1 0 9 1 2 1 9 1 2 2 1 2 1 k k n k x的近似值求 1 3 无重组合推论1 1 5 二项式系数的基本性质二项式系数的基本性质 10 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 得证 另外 也可通过计算得出证明如下 得证 另外 也可通过计算得出证明如下 nn C n nrC n r nrnnrnrr 11 1 3 无重组合推论2 四个基本性质四个基本性质 性质性质1 对称关系 对称关系 C n r C n n r 性质性质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 1 1 1 1 1 1 1 1 1 1 1 1 1 nn nnrnr n C n r rnrrnrr rnrnr nn rnrrnr C nrC nr 12 1 5 二项式系数的基本性质二项式系数的基本性质 1 3 无重组合推论2 Pascal 杨辉 三角形 杨辉 三角形 13 1 5 二项式系数的基本性质二项式系数的基本性质 kn n k n k n k n k n n nn 1 11 11 0 k n 01234 01 111 2121 31331 414641 1 3 无重组合推论3 四个基本性质四个基本性质 性质性质1 对称关系 对称关系 C n r C n n r 性质性质2 递推关系 递推关系 Pascal公式公式 C n r C n 1 r C n 1 r 1 性质性质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 14 1 5 二项式系数的基本性质二项式系数的基本性质 1 3 无重组合推论3 四个基本性质四个基本性质性质性质4 单峰性 单峰性 课本课本p56 1 C n 0 C n 1 C n n 是单峰序列 是单峰序列 2 当当n为偶数时 为偶数时 C n 0 C n 1 C n n 3 当当n为奇数时 为奇数时 C n 0 C n 1 C n n 证明 证明 设设1 k n 则则 15 1 5 二项式系数的基本性质二项式系数的基本性质 若 s0 s1 st st 1 sn 则称 s0 s1 sn是单峰的 例如 1 1 1 2 1 1 3 3 1 都是单峰的 1 2 1 2 1 不是单峰的 定义定义 k kn knk n knk n k n k n 1 1 1 1 1 21 21 2 1 1 21 21 2 1 1 21 21 2 1 k kk k kn kn n k k kk k kn kn n k k kk k kn kn n k n 时 当 时 当 时 当 为奇数若 1 1221 22 2 1 121 2 2 k kk k kn kn n k k kk k kn kn n k n 时 当 时 当 为偶数若 17 先递增后递减 1 5 二项式系数的基本性质二项式系数的基本性质 回到杨辉三角回到杨辉三角 1 5 组合恒等式及其含义1 1 6 组合恒等式及其含义组合恒等式及其含义 18 1 11 k n k n k n kn n k n 0 1 1 21 1 0 0 0 n k k n n k n k kn k n x k n x x k n x 得令 得令 1 6 组合恒等式及其含义组合恒等式及其含义 关于二项式系数的恒等式至今已发现有上千个 这些恒等式 在算法分析中起到非常重要的作用 关于二项式系数的恒等式至今已发现有上千个 这些恒等式 在算法分析中起到非常重要的作用 1 5 组合恒等式及其含义1 1 6 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式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 得证 或通过计算证明 考虑 得证 或通过计算证明 考虑 从n个人中挑选k个人组成一个队 并选择一人为队长 有多少种组合 n nn kn kk k kn n nnk n k k k nnnnkn n k kkkk 1 0 1 1 1 1 1 1 1 2 1 1 1 1 2 1 若 若有 若 若有 20 1 5 组合恒等式及其含义2 1 5 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式2 课本 课本p64等式等式3 1 1 2 n n k nNkC n kn 如有如有 证明 证明 考虑盒子考虑盒子1中有中有n个有区别的球 从中取一个球放入盒子个有区别的球 从中取一个球放入盒子2 中 再取任意多个球放入盒子中 再取任意多个球放入盒子3中 等式左端表示先从盒子中 等式左端表示先从盒子1中 取 中 取k k 1 2 n 个球 再从中取一个放入盒子个球 再从中取一个放入盒子2中 剩下的中 剩下的k 1个 球放入盒子 个 球放入盒子3中 等式右端表示先从盒子中 等式右端表示先从盒子1中取一个放入盒子中取一个放入盒子2中 剩下的 中 剩下的n 1个球是否放入盒子个球是否放入盒子3中均有两种可能 显然两种取法 结果是一样的 得证 或通过 中均有两种可能 显然两种取法 结果是一样的 得证 或通过计算计算证明 证明 111 1 10 1 11 11 11 1 2 nnn kkk nn kk n n nnn kkn kkk k nn nn kk n 21 1 5 组合恒等式及其含义3 1 5 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式3 0 1 0 n k k nNkC n k 如有如有 证明 证明 将等式两边对将等式两边对x微分得 在上式中 令 微分得 在上式中 令x 1得 即 得证 注 如令 得 即 得证 注 如令x 1 即可证明 即可证明恒等式恒等式2 0 11 1 1 1 1 0 1 1 1 0 1 0 n nk k n nk k n k kn k k n xx k n nxkx k n k k n k k 22 1 5 组合恒等式及其含义4 5 1 5 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式5 恒等式 恒等式4 12 0 1 0 n k k nNkC n k 如有如有 22 0 1 2 n n k nNkC n kn n 如有如有 证明 证明 将等式两边对将等式两边对x微分得 将等式两边同乘以 微分得 将等式两边同乘以x后再对后再对x微分得 在上式中 令 微分得 在上式中 令x 1得 得证 注 如令 得 得证 注 如令x 1 即可证明 即可证明恒等式恒等式5 0 11 1 1221 1 22 1 1 1 1 1 1 1 2 n nk k n nk k n nnk k n n k n xx k n nxkx k n nxnxxkx k n kn n k 23 1 5 组合恒等式及其含义6 1 5 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式6 1 0 121 11 n n k nNC n k kn 如有如有 证明 证明 将等式两边对将等式两边对x从从0到到1积分得 即 得证 积分得 即 得证 0 11 00 0 11 11 0 00 1 0 1 1 1 11 211 11 n nk k n nk k nk n k n n k n xx k n xdxx dx k xx n k nk n k nk 24 2 1 32 2 1 2 12 1 2 0 22 2 1 1 2 2 2 1 1 1 1 2 1 1 2 1 1 2 1 1 22 2 0 0 00 0 nn n nn n nn k n nn k n nn k n knk n kk k n kk nn n k n k n k n k n k 解法1解法1 求 n k k n n k k x n k k x n k k n x n x n n k kn n k x k n kn x x k n k x k n k dxx k n n x n x dxx x k n x k n kk 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 解法 2 1 1 2 求 2 1 32 2 1 2 12 1 2 12 1 1 2 1 1 2 1 1 2 1 1 1 1 1 2 12 1 1 1 2 1 1 1 1 1 1 1 1 1 1 22 2 0 0 1 0 0 2 1 0 0 1 2 1 0 2 1 0 1 0 1 1 0 1 nn n nn n nnk n kk k n kk x k n kk dxx k n k nnn x n dxdxx n dx n x nn n n k n k n k k n k k nn n n 恒等式恒等式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的系数即可得证 推论 的系数即可得证 推论 000 00 1 1 1 m nmn m nmn rij rij m nr r rk xxx mnmn xxx rij mn x krk 2 0 2 n r nn rn 28 n n k n n k 2 0 2 n n k n n n kn n k n x x k n x k n xx n k n k n n k k n k k nn 2 2 2 1 1 证法 0 2 0 2 0 2 0 22 即 的系数相等两边的 1 n k n k nn k n kn n k n n n nS kn kn n Bk k n A knBkAnS BASbbBaaA 0 2 0 11 2 证法 组合数的 组合 个有组合 个有 组合合并而成 的组合与的组合由的 设LL2 n n k n n k 2 0 2 0 m k m nNC m kC n kC mn m 如有如有 0 2 n k nNC n kC n kCn n 如有如有 1 5 组合恒等式及其含义8 9 1 5 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式8 恒等式 恒等式9 31 恒等式恒等式10 如如p q n Z且且p q n 0 有 有 恒等式恒等式11 如如p q n Z且且p q n 0 有 有 0 p k C p k C q k C nk pqC n p C n q 0 p k C p k C q k C npqk pqC np p C nq q 1 5 组合恒等式及其含义12 1 5 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式12 课本 课本p64等式等式4 0 0 1 1 n i n kZn kC i kC nk 如且有如且有 证明 证明 利用利用组合分析法组合分析法 在集合 在集合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也成立 由归纳原理 得证 也成立 由归纳原理 得证 0 1 00 1 1 0110 100 1112 12 n i nn ii C i kC nk k kkk iinnnn kkkkkk 32 1 5 组合恒等式及其含义13 1 5 组合恒等式及其含义组合恒等式及其含义 恒等式恒等式13 0 0 1 k j R kZkCj jCkk 如且有如且有 证明 证明 注意 这个恒等式与前面的有一个很不一样的地方 就 是 注意 这个恒等式与前面的有一个很不一样的地方 就 是C j j C k 1 k 是广义的二项式系数 根据广义的二项式 系数的定义 是广义的二项式系数 根据广义的二项式 系数的定义 Pascal公式公式C k C 1 k C 1 k 1 对实数对实数 和整 数 和整 数k同样成立 与恒等式同样成立 与恒等式1类似 反复使用类似 反复使用Pascal公式即可得证 公式即可得证 33 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 34 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 35 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个 得证 或通过计算证明 个 得证 或通过计算证明 nln nl lr lnlrlrrnllr nnr rnrlrnl nnr rlr 36 1 5 组合恒等式及其含义15 1 5 组合恒等式及其含义组合恒等式及其含义 定义 定义 r为奇数称为奇组合 为奇数称为奇组合 r为偶数称为偶组合 为偶数称为偶组合 37 1 2 n EkOk k n k n 恒等式恒等式16 课本课本p63等式等式2 奇组合与偶组合各半 即记集合奇组合与偶组合各半 即记集合 O k 0 k n k是奇数是奇数 E k 0 k n k是偶数是偶数 则 EkOk Ek k Ok k EOk k n k kn k n k n k n k n k n xx k n x 1 1 1 0 1 1 0 令 证法1证法1 1 5 组合恒等式及其含义15 1 5 组合恒等式及其含义组合恒等式及其含义 38 证明证明2 设 S a1 a2 an 考虑 S 的偶组合 a1有两种选择 a1选定后 a2有两种选择 a1 a2 an 1都选定后 an只 有一种选择 若已选了偶数个元素 则不选 an 否则选 an 所 以 S 的偶组合共有 2n 1个 S 的奇组合数目为 2n 2n 1 2n 1 1 5 组合恒等式证明方法 1 5 组合恒等式及其含义组合恒等式及其含义 常用的证明方法常用的证明方法 数学归纳法数学归纳法 二项式系数公式 特别是二项式系数公式 特别是Pascal 公式公式 比较级数展开式中的系数 二项式定理或母函数法 比较级数展开式中的系数 二项式定理或母函数法 积分微分法积分微分法 组合分析法组合分析法 39 1 3 无重组合推论1 1 6 多项式定理多项式定理 40 1 3 无重组合推论1 1 6 多项式定理多项式定理 定义定义多项式系数 多项式系数 41 1212 tt n n nnnn nn LL 其中 其中 t 1 且且 12t nnnn L 多项式系数的多项式系数的Pascal公式公式 121212 11 11 ttt nnn nnnnnnnnn L LLL 12 1 1 t n nnn L 1 3 无重组合推论1 1 6 多项式定理多项式定理 42 多项式定理多项式定理 12 1 1212 12 t t n nnn tt nnnt n xxxx xx nnn 1 6 模型转换方法 1 7 模型转换模型转换 43 1 6 模型转换方法 1 7 模型转换模型转换 问题的分析注意事项问题的分析注意事项 分析对象属性分析对象属性 合理分类合理分类 明确分步明确分步 模型转换模型转换 如排列如排列 组合组合 一一对应一一对应 计数的难易程度计数的难易程度 方式的转换方式的转换 1 1 1 一组 等价 一组 等价 44 1 6 模型转换例1 1 7 模型转换模型转换 例题例题 例例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场比赛进行 场比赛进行 45 1 6 模型转换例2 1 1 7 模型转换模型转换 格路问题格路问题 例例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 Y m 1 n m n m n 1 0 0 X 46 1 6 模型转换例2 2 1 7 模型转换模型转换 格路问题格路问题 另外 一条从另外 一条从 0 0 点到点到 m n 点的路径可分为两类情况 一 种是从 点的路径可分为两类情况 一 种是从 0 0 点到点到 m n 1 点的路径 另一种是从点的路