第 6 章 计数
# 第 6 章 计数
组合数学是研究物体安排的科学
- 枚举是指物体安排的计数
# 6.1 计数的基础
# 6.1.1 引言
# 6.1.2 基本的计数原则
计数的乘积法则
- 假定一个过程可以被分解为两个任务
- 如果完成第一个任务有
种方式 - 完成第一个任务之后有
种方式完成第二个任务
- 如果完成第一个任务有
- 那么完成这个过程有
种方式
集合的乘积法则
- 有限集合的笛卡尔积大小是各个集合大小的乘积
计数的求和法则
- 如果完成第一项任务有
种方式, 完成第二项任务有 种方式 - 并且这些任务不能同时执行
- 则完成第一项或第二项任务有
种方式
集合的求和法则
- 两两互斥的并集的大小是各个集合大小之和
# 6.1.3 比较复杂的计数问题
# 6.1.4 减法法则(两个集合的容斥原理)
减法法则
- 如果一个任务或者可以通过
种方法执行, 或者可以通过 种另一类方法执行 - 那么执行这个任务的方法数是
减去两类方法中相同的方法
减法法则也被称为集合的容斥原理
# 6.1.5 除法法则
除法法则
- 如果一个任务能由一个可以用
种方式完成的过程实现 - 而对于每种完成任务的方式
, 在 种方式中正好有 种与之等价
- 而对于每种完成任务的方式
- 那么完成这个任务的方法数为
可以按照 $d$ 对 $1$ 的函数进行理解
集合的除法法则
- 如果一个有限集
是 个 有 个元素的 互斥集合 的并集 - 则
# 6.1.6 树图
树图
- 树图是指由
- 根
- 从根出发的分支
- 从分支的某些端点出发的其他分支
- 构成的图
树叶
- 树叶是某些分支的端点, 从这些端点不再进一步的分支
用树图求解计数问题时, 到达一片树叶所做的选择个数可能是不同的
示例: 5 胜 3
# 6.2 鸽巢原理
#
鸽巢原理
- 如果
k+1
或更多的物体放入k
个盒子,那么至少有一个盒子包含了2
个或更多的物体
# 6.2.2 广义鸽巢原理
#
广义鸽巢原理
- 如果
个物体放入 个盒子, 那么至少有一个盒子包含了至少 个物体
应用
- 把一些物体分到
个盒子中, 使得某个盒子至少含有 r
个物体- 则这些物体的最少个数为
- 则这些物体的最少个数为
# 6.2.3 鸽巢定理的几个简单应用
#
定理 3
- 每个由
个不同的实数构成的序列都包含一个长为 的严格递增子序列或严格递减子序列
子序列的定义
- 假定
是实数序列 - 它的一个子序列是形如
的序列 - 其中
- 其中
- 即一个子序列是从初始序列得到的序列, 按照原来的顺序选取初始序列的某些项, 也许要排除其他的项
- 它的一个子序列是形如
#
拉姆齐理论
- 拉姆齐数
均是大于等于 的正整数 - 其表示
- 假设晚会上每两个人都是朋友或者是敌人, 那么在一个晚会上, 使得
- 或者有
个人两两都是朋友 - 或者有
个人两两都是敌人
- 或者有
- 所需要的最少人数
- 假设晚会上每两个人都是朋友或者是敌人, 那么在一个晚会上, 使得
- 拉姆齐数的下界
通常用于处理集合元素的子集分配问题
# 6.3 排列与组合
# 6.3.1 引言
# 6.3.2 排列
笔记
- 对于一个集合中
个元素的有序安排称为 排列
#
定理 1
- 如果
和 都是整数, 且 , 则具有 个元素的 排列是
# 6.2.3 组合
笔记
- 集合元素的一个
组合是从这个集合无序选取 个元素 - 一个
组合是这个集合的一个 个元素的子集 - 具有
个不同元素的集合的 组合数记为 - 也记作
- 称为二项式系数
- 也记作
- 一个
#
定理 2
- 设
是正整数, 是满足 的整数, 元素集合的 组合数等于
推论
#
恒等式的组合证明
- 双计数证明
- 在证明中使用计数的论述
- 说明一个恒等式的两边通过不同的方法计数了同样的元素
- 双射证明
- 证明基于等式两边的对象集合存在一个双射函数
- 双计数证明和双射证明也称为恒等式的组合证明
# 6.4 二项式系数和恒等式
# 6.4.1 二项式定理
#
二项式定理
- 设
和 是变量, 是非负整数, 则
相关推论
# 6.4.2 帕斯卡恒等式和三角形
#
帕斯卡恒等式
- 设
和 是满足 的正整数, 那么有 - 证明可以通过组合证明的方法进行
帕斯卡三角形
- 对于所有的整数
, 可以用帕斯卡恒等式和初始条件 递归的定义二项式系数 - 由此便可产生帕斯卡三角形
图示
# 6.4.3 其他的二顶式系数恒等式
#
#
定理 4
- 设
和 是非负整数, , 那么 - 证明可以通过组合证明的方法进行
- 左边相当于是计数了长度为
的比特串包含了 个 - 右边累加的对象, 相当于是计数了具有
个 的比特串中, 最后 1 个 出现在第 位的所有可能的情况 - 这样, 前
位相当于包含了 个
- 这样, 前
- 左边相当于是计数了长度为
# 6.5 排列与组合的推广
# 6.5.1 引言
# 6.5.2 有重复的排列
#
定理 1
具有
# 6.5.3 有重复的组合
#
定理2
个元素的集合中允许重复的 组合有 个 证明
- 当允许重复时,
元素集合的每个 组合可以用 条竖线和 颗星的列表来表示 条竖线用来标记 不同的单元 - 每个单元中的星数表示选择该元素的个数
- 相当于从
个位置中选择 个位置用来存放星或者选择 个位置用来存放竖线
- 当允许重复时,
- 也可借助 生成函数 进行求解
# 6.5.4 具有不可区别物体的集合的排列
#
定理 653
- 设类型 1 的相同的物体数有
个, 类型 2 的相同物体数有 个, ..., 类型 的相同物体数有 个, 那么 个物体不同的排列数是
证明
- 除了书上的方法, 也可以应用 除法法则 进行理解
# 6.5.5 把物体放入盒子
许多计数问题都可以通过枚举把不同物体放入不同盒子的方式数来解决
- 其中物体和盒子可以是可辨别的, 也可以是不可辨别的
- 组合起来有 4 种不用的情况
可辨别的物体与可辨别的盒子
- 把
个不同的物体分配到 个不同的盒子使得 个物体放入盒子 的方式数等于 - 与 定理 653 的情况相同, 一个是选位置, 一个是选元素
不可辨别的物体与可辨别的盒子
- 将
个不可辨别的物体放入 个可辨别的盒子 - 等价于
个元素的集合中允许重复的 组合数 - 相当于
个隔板和 个星号 - 等于
- 等价于
#
可辨别的物体与不可辨别的盒子
- 设
表示将 个可辨别的物体放入 个不可辨别的盒子的方式数 - 其中不允许有空的盒子
为第二类斯特林数
- 利用容斥原理可以证明
- 将
个不可辨别的物体放入 个可辨别的盒子的方法数等于
🔲 待做事项
需要添加链接
不可辨别的物体与不可辨别的盒子
- 将
个不可辨别的物体放入 个不可辨别的盒子, 等价于将 写成最多 个非递增正整数的和 - 每种放入方式相当于正整数
的一个划分
- 每种放入方式相当于正整数
划分
- 如果
, 其中 都是正整数, 且 - 则说
是将正整数 划分为 个正整数的一个划分
# 6.6 生成排列和组合
# 6.6.1 引言
# 6.6.2 生成排列
笔记
- 任何
元素集合可以与集合 建立一一对应 - 生成任何
元素集合的排列等价于生成 个最小正整数的排列
- 生成任何
字典顺序
- 如果对于某个
, 并且 , 那么排列 在排列 的前边
生成排列的算法
- 生成
的排列的算法基础是从一个给定的排列 按照字典顺序构造下一个排列的过程 生成排列的算法的伪代码
# 6.6.3 生成组合
生成一个有穷集的所有组合
- 一个组合即是集合的一个子集, 所以可以利用集合
与 位比特串之间的对应关系 生成所有组合的算法的伪代码
生成有 n 个元素集合的 r 组合的算法
- 生成
的 组合的算法基础是从一个给定的 组合 按照字典顺序构造下一个组合的过程 生成 r 组合算法的伪代码
编辑 (opens new window)