组合数学笔记(四)
组合数学
第8章 特殊计数序列
8.1 Catalan 数
定义
Catalan 数列是序列
是第
凸
由
另一个递推:
应用
- 括号化问题
- 出栈次序问题
个结点构成得二叉树数
定理
8.1.1
考虑由
其部分和总满足:
的序列的个数等于第
可解决的问题
- 买票找零问题
- 走方格问题
拟 Catalan 数
定义一个新数列:
其中,
得到:
将 Catalan 数的递推关系代入得到拟 Catalan 数的递推
关系:
初值为:
8.2 差分序列
定义
设
称为
递归定义
对
对
对
对
差分表
设序列
- 序列
的差分表由第 行确定
定理
8.2.1
设序列的通项
则对于所有的
8.2.2
差分表的第
的序列的通项满足:
的关于
证明思路
线性性+简单差分表
8.2.3
假设序列
那么:
(证明中间有一段:
应用
- 一般项为多项式的序列的部分和
8.2.4
若
类比二项式公式中:
类
直接上方的元素乘以
8.2.5
第二类
8.2.6
对每一个满足
从而
8.2.7
如果
8.2.8
若
8.2.9
第一类
性质
- 差分表由第
行上元素的值就能决定 - 差分表也可由第
条对角线决定
例子
简单差分表1
若第
简单差分表1
第
首先
其次
差分表的线性性
设
- 一般的:
- 更一般的,对于任何常数
来说,
差分表的第0条
组合意义
(由定理8.2.2)
对于序列
则有:
特殊值1:
特殊值2:
由
特殊值3:
则,
递推关系:
且:
故:
令
所以
第二类 数
特殊值:
递推公式:
定理8.2.4
组合解释:
投球入盒
定理8.2.5
数
令
盒子的划分个数,则
公式:定理 8.2.6
所以
空盒 | |||
---|---|---|---|
有区别 | 无区别 | 没有 | |
有区别 | 有区别 | 没有 |
定义
定义
是第二类
递推
定理 8.2.7
第一类 数
对比
第二类
- 指出如何用
写出 - 把
个元素的集合划分到 个不可区分的盒子且没有空盒的划分的个数
第一类
- 如何用
写出 - 将
个物品排成 个非空的循环排列方法数
定义
一般地,
乘开后得到
其系数的符号正负相间。故:
特殊值
递推式
定理 8.2.8
组合意义
定理 8.2.9
小结
是否为空 | 方案个数 | |||
---|---|---|---|---|
有区别 | 有区别 | 有空盒 | ||
有区别 | 无区别 | 无空盒 | ||
有区别 | 有区别 | 无空盒 | ||
有区别 | 无区别 | 有空盒 | ||
有区别 | 无区别 | 有空盒 | ||
有区别 | 非空 |