组合数学笔记(三)
组合数学
第6章 容斥原理及应用
6.1 容斥原理
定义
计数函数:
定理和推论
设集合
6.1.1
集合
6.1.2
集合
其中,第一个和对
特别情况
若:
则,
6.2 带重复的组合
多重集组合与方程整数解个数
多重集
的整数解的个数。
6.3 错位排列
定义
1.
设
定理
6.3.1
对
性质
错位排列的递推关系
1
2
6.4 带有禁止位置的排列
定义
(1) 带有禁止位置的排列
令
记
(2) 带禁止位置的“非攻击性车”
令
为坐标的n个车的位置
满足第
定理
6.4.1
将
所以
- 任意两个车不在同一行或同一列
- 所有的
个车放置在其禁止位置上的放置方法数, 的计算不考虑剩下的 个车的放置
6.5 另一个禁止位置问题
定义
相对禁止位置排列计数
对
定理
6.5.1
对于
例题
旋转木马问题
看ppt去
相对禁止 与错位排列 的关系
第7章 递推关系和生成函数
生成函数(也称母函数)核心思想:
把离散数列和幂级数一一对应起来,
把离散数列间的相互结合关系对应成为幂级数间的运算关系
由幂级数形式来确定 离散数列 的构造
7.1 若干数列
定义
斐波那契数列
设有数列
称该数列为斐波那契(Fibonacci)数列,这个数列的项称为斐波那契数
定理
7.1.1
斐波那契数
7.1.2
沿
其中, t=
性质
斐波那契数列
斐波那契数列的项的部分和
斐波那契数是偶数当且仅当n被3整除
斐波那契数能被3整除当且仅当n可被4整除
斐波那契数能被4整除当且仅当n可被6整除
Fibonacci数列与黄金分割数
7.2 生成函数
涉及一个整数参数
*常见展开式
对满足
当
令
生成函数的定义
令
有限数列
适合多重集组合
生成函数——多重集组合
求生成函数
设
的非负整数解个数,
即
当
求通项
把生成函数向根本形式:
排列逆序
记
设
- 对于
,有 - 对
,有
定理
7.2.1
设
7.3 指数生成函数
指数生成函数的定义
数列
例
设
其中,
求数列
多重集排列
考虑由n个元素组成的多重集
其中
若
若
由组合生成排列——即先选后全排列
有限重数
已知
则
展开后
此处:
故指数生成函数为:
定理
7.3.1
设
其中,对于
推广到无穷重数
设
其中:
当
*常用展开式
7.4 求解线性齐次递推关系
定义
线性齐次递推关系
令
则称该数列满足
若
若
解法
本节重点讨论
- 特征方程法
- 生成函数法
定理
7.4.1(特征方程法)
令
的解当且仅当
的一个根。(特征根)
若多项式方程
是下述意义下 $ (1)
$ 式和初始条件的唯一的数列。
7.4.2(通解)
令
的特征方程的互异的根。
如果
且该递推关系的通解为:
7.4.3
令
的数列, 则它的生成函数
其中,
若
且
反之, 给定这样的多项式
方法
特征方程法
详见定理7.4.1、7.4.2
特征方程有重根
定理7.4.1不适用于特征方程有重根的情况
生成函数法
(1)利用递推关系求出序列的生成函数:
(2)用部分分式法,把
(3)利用牛顿二项式展开
如何得到生成函数:
- 先设出生成函数的通项
- 利用递推关系加减消除法到只剩初始项
- 加减消除法的系数为递推关系的系数!!!
- 最终是含
项系数尽量为
牛顿二项式:
如果
是正整数,而 是非零实数, 时,则有
联系
设特征方程为
设相应特征方程
…
不想写了,详见PPT~~~
小结
利用特征方程求解常系数线性齐次递推关系:
- 写出相应的特征方程
- 求解特征方程
- 如果没有重根,则直接给出通解(定理7.4.1)
- 如果有重根,根据重根求出通解(定理7.4.2)
- 将初始条件代入通解,得到满足初始条件的解
利用生成函数求解:使得
7.5 非齐次递推关系
定义:
对于常系数线性递推关系
若
汉诺塔问题
递推关系
迭代求解
就嗯迭代
但是迭代完了一定要数学归纳法证明结果的正确性
通解
生成函数法
不一定可行,若
特征方程法
假设有非齐次递推关系
若
的通解, 而
那么:
小结
- 求对应的齐次递推关系的通解;
- 求该非齐次递推关系的一个特解;
- 将一般解和特解结合得到该非齐次递推关系的
通解; - 通过初始条件确定通解中出现的常系数值.
难点:
- 特征方程求解
- 找出一个特解
尝试特解的方法:
根据非齐次项
如果
是 的 次多项式,尝试 也是 的 次多项式- 若
, 尝试 - 若
, 尝试 - 若
, 尝试$ hn = rn^2+sn+t (r, s, t是常数) $
- 若
若
是指数形式,尝试 也是指数形式。
如:
若
7.6 一个几何例子
定义
定义1
设有平面或空间中的点集
定理
定理7.6.1
设
在有
定义
则
该递推关系解为:
其中: