第 8 章 高级计数技术
# 第 8 章 高级计数技术
主要内容
- 递推关系
- 动态规划
- 分而治之
- 生成函数
- 容斥原理
# 8.1 递推关系的应用
# 8.1.1 引言
递推关系
- 递推关系的定义
- 某些计数问题可以通过找到序列的项之间的关系,即递推关系来求解
# 8.1.2 用递推关系构造数学模型
实例
- 兔子和斐波那契数
- 汉诺塔
- 编码字的枚举
- 编码字指十进制数字串包含偶数个 0
- 卡塔兰数
指对 个数 的乘积中加括号来规定乘法次序的方式数
# 8.1.3 算法与递推关系
动态规划
- 遵循动态规划范式的算法是将问题递归地分解为更简单的重叠子问题,通过子问题的解决来解决原问题
- 借助递推关系从子问题的解中求出全局问题的解
动态规划之所以这样命名是因为其最初是设计用来解决调度问题的
讲座调度问题
- 保存每一次计算值的过程称为 记忆,对于提高递归算法的效率是很重要的技术
🔲 待做事项
- CLRS 中关于这个问题阐述的更加清晰
- 从 CLRS 的笔记中添加引用
# 8.2 求解线性递推关系
# 8.2.1 引言
# 8.2.2 求解常系数线性齐次递推关系
#
常系数线性齐次递推关系的定义
- 这个递推关系还需要
个初始条件 常系数线性齐次的具体含义
- 参考 (opens new window)
- 常系数是指各项的系数为常数
- 线性指定了指数为 1
- 齐次指的是各项的指数相同
- 表明没有常数项
#
求解常系数线性齐次递推关系
- 各项系数由初始条件来确定
# 8.2.3 求解常系数线性非齐次递推关系
常系数线性非齐次递推关系
- 形如下式的递推关系叫做常系数线性非齐次递推关系
- 如下式的递推关系叫做相伴的齐次递推关系
#
一般形式的常系数线性非齐次递推关系的求解方法
- 由一个特解和相伴的线性非齐次递推关系的解组成
#
特殊形式的常系数线性非齐次递推关系的求解方法
- 其中
是 的多项式与一个常数 的 次幂之积 - 需要注意
是特征方程根时的特殊情况
- 需要注意
# 8.3 分治算法和递推关系
# 8.3.1 引言
分治算法
- 将一个问题划分成较小规模的同一问题的一个或多个实例,然后用这些小问题的解来处理这个问题以找到初始问题的解
# 8.3.2 分治递推关系
分治递推关系
- 把规模为
的问题化分为 个子问题,其中每个子问题的规模是 表示由子问题的解得到原问题的解所需要的额外运算 表示求解规模为 的问题时所需要的总的运算数
#
额外运算为常数时分治递推关系
- 证明可以分为
和 两种情况进行 - 对递推式进行展开,直至常数项
#
主定理 -- 额外运算为非常数时的分治递推关系
- 与 CLRS 中的描述有些许差别
- 其中
和 的比较等价于 与 的比较
- 其中
🔲 待做事项
- 补上链接到 CLRS 中的链接
实例
- 整数的快速乘法
- 快速矩阵乘法
- CLRS 中有详细描述
- 最近点对问题
# 8.4 生成函数
# 8.4.1 引言
#
生成函数的定义
-
- 把序列的项作为一个形式幂级数中变量
的幂的系数 - 此生成函数也叫做普通生成函数
的幂只在生成函数中作为占位符使用 - 所以其取值对于使用生成函数的目的没有什么影响
重点是各次幂的系数,可以借助此求解各类计数问题
- 把序列的项作为一个形式幂级数中变量
# 8.4.2 关于幂级数的有用事实
#
两个生成函数的相加和相乘
#
广义二项式系数
-
- 与一般二项式系数定义不同的是
不是整数,且其可以小于 - 此公式可用于求解当元素允许重复时
元素集合的 组合数 - P476页例 1
- 有重复的组合
- 此公式可用于求解当元素允许重复时
- 与一般二项式系数定义不同的是
常用的生成函数
# 8.4.3 计数问题与生成函数
使用方法
- 赋予
的各次幂实际的含义 - 比如分配饼干时,
的各次幂可以表示饼干的数量 - 硬币找零时,表示面额
- 允许重复的
元素的 组合中表示选出的元素数量
- 比如分配饼干时,
- 每个元素都对生成函数的展开式贡献了因子
- 比如
的形式 - 将各个元素贡献的因子相乘,即可得到生成函数的展开式
- 每个元素的因子形式,要看其对于幂级数系数的贡献
- 注意分次序和不分次序,分析方法不同
- 不分次序时,以元素为单位进行考虑
- 分次序时,则以选择的次序为单位考虑
- 比如
- 借助常用的生成函数,将幂级数表示为收敛的形式
- 最后借助广义二项式定理进行展开,即可得到各项的次数
# 8.4.4 使用生成函数求解递推关系
使用方法
- 借助递推关系求出序列
的生成函数的封闭形式 - 需要借助求和公式的下标变换
- 再将生成函数展开,即可得到序列的求和公式
# 8.4.5 使用生成函数证明恒等式
一般从系数相等入手进行求解
- 证明等式的两边均是生成函数某一项的系数
# 8.5 容斥
# 8.5.1 引言
容斥原理用于求解多个有穷集的并集
# 8.5.2 容斥原理
#
容斥原理
-
- 公式的可以由
值较小的情形推出 - 公式的证明可以通过证明并集中的每个元素在等式右边恰好被计数 1 次
- 对于
个元素的集合中的每一个非空子集的交,在这个公式中都存在一项计数了它的元素 - 因为这个公式共有
项
- 因为这个公式共有
- 公式的可以由
# 8.6 容斥原理的应用
# 8.6.1 引言
# 8.6.2 容斥原理的另一种形式
容斥原理的变形
- 可以用于求解一个集合中不具有
个性质 中任何一条性质的元素数 - 类似于求补
# 8.6.3 Eratosthenes 筛
可以求出不超过一个给定正整数的素数的个数
- 原理是 定理 432
# 8.6.4 映上函数的个数
#
求解映上函数的个数
-
- 相当于是从陪域中依次剔除各个元素
- 相当于陪域中至少有一个元素不在值域中
- 与第二类斯特林数存在一定的关系
- 即为
- 相当于将
个元素分配到 个不可辨别的盒子,使得每个盒子都不为空 - 然后再将这些盒子按照
进行编号
- 相当于将
- 即为
# 8.6.5 错位排列
错位排列是指没有一个物体在它的初始位置上排列
#
n 元素集合的错位排列
- 由恒等式
- 可得
- 此数值即为错位排列的概率
- 可得
编辑 (opens new window)