0%

组合与计数

错排问题

递推:

$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$ 条线段不相交的方法数。

对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数。