错排问题
递推:
$D(n)=(n-1)[D(n-2)+D(n-1)]$
容斥:
容斥的式子可以由二项式反演简单的推出来:不考虑 $i \neq a_i$ 这个条件,那么方案数即为 $n!$。这些排列中包含了所有恰由 $k(k=0,1,2,\cdots,n)$ 个位置不变的排列,因此有
使用二项式反演即可得到
第一类 Stirling 数
第一类 Stirling 数表示 n 个不同元素构成 m 个圆排列的数目。有无符号 Stirling 数也表示升阶函数和降阶函数的系数:
有无符号 Stirling 数之间的关系为 $s_s(n,m)=(-1)^{n-m}s_u(n,m)$
递推形式:$s(n,r)=(n-1)s(n-1,r)+s(n-1,r-1)$
有符号的第一类 Stirling 数可以简单推导如下:
即
性质:
- $s(n,0)=[n=0]$
- $s(n,1)=(n-1)!$
- $s(n,2)=(n-1)!\sum_{i=1}^{n-1}\frac{1}{i}$
- $s(n,n-1)=\binom{n}{2}$
- $\sum_{k=0}^ns_u(n,k)=n!$
- $\sum_{k=0}^ns_s(n,k)=[n=0]$
第二类 Stirling 数
第二类 Stirling 数可以表示把 $n$ 个球放进 $r$ 个相同的盒子里的方案数(没有空盒)。
递推形式: $S(n,r)=rS(n-1,r)+S(n-1,r-1)$
第二类 Stirling 数也可用下降阶乘幂定义:
通项公式为
可以用容斥理解。$k$ 为有多少集合是空的,每个 $k$ 有 $\binom{m}{k}$ 种空集,$n$ 个元素可以放进非空的 $m-k$ 个集合中。最后再除以 $m!$ 使其变为无序的情况。
性质:
- $S(n,1)=S(n,n)=1$
- $S(n,0)=[n=0]$
- $S(n,2)=2^{n-1}-1$
- $S(n,3)=\frac{1}{6}(3^n-3\cdot 2^n+3)$
- $S(n,n-1)=\binom{n}{2}$
Catalan 数
Catalan数从 $0$ 开始的前几项:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845
Catalan 数常见公式
Catalan 数应用
路径计数问题:只能往右或往上走一个单位长度,问有多少种不同的路径可以从左下角 $(1,1)$ 走到右上角 $(n,n)$,并且要求路径不能经过直线 $y=x$ 上方的点。
对于一种不合法的方案,它的路径一定与 $y=x+1$ 有交。将第一个交点后面的路径关于 $y=x+1$ 做个对称,新的路径就会到达 $(n-1,n+1)$。合法的方案总数就是
括号序列计数:有多少种不同的长度为 $n$ 的括号序列。长度为 $2n$ 的括号序列的方案数就是 $C_n$
出栈顺序:有多少种可能的操作序列。
二叉树计数:有多少种不同的 $n$ 个结点的二叉树
对这棵树进行遍历,遍历顺序即是一个括号序列。
在圆上选择 $2n$ 个点,将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数。
对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数。