组合数学学习笔记

数学还是太菜了 \kk 。

组合数和排列数

定义

~~高中数学选修三内容。~~

定义排列数 $A_n^m$ 为从 $n$ 个不重复的元素中选 $m$ 个按一定顺序排列的方案数。

根据乘法原理易得

A_n^m=n\times (n-1)\times … \times(n-m+1)=\frac{n!}{(n-m)!}

定义排列数 $C_n^m$ 为从 $n$ 个不重复的元素中选 $m$ 个的方案数。

由排列数公式易得

C_n^m=\dbinom{n}{m}=\frac{n!}{m!(n-m)!}

也就输排列数除去 $n!$ ，简单易懂。

推广

二项式定理

(x+y)^n=\sum\limits_{i=0}^n \dbinom{n}{i}x^iy^{n-i}

二项式反演

若

g(i)=\sum\limits_{i=k}^n \dbinom{n}{i}f(i)

则

f(i)=\sum\limits_{i=k}^n \dbinom{n}{i}(-1)^{i-k}g(i)

常用于解决一类形如 “恰好……” 的问题。这类问题中，一般将其转化为 “钦定……” 的问题便于求解，最后使用二项式反演即可。

例题：P4859，P6478

常用的组合恒等式

(一)

\dbinom{n}{i}=\frac{n-i+1}{i}\dbinom{n}{i-1}

证明：显然。

(二)

\dbinom{n}{i}=\frac{n}{i}\dbinom{n-1}{i-1}

证明：显然。

(三) 基本求和公式

\sum\limits_{i=0}^n\dbinom{n}{i}=2^n

证明：由组合意义易证。

(四) 交错和

\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}=0

证明：套用二项式定理即可。

(五)

\sum\limits_{i=0||1}^nk\dbinom{n}{i}=n2^{n-1}

证明：

\begin{aligned} \sum\limits_{i=1}^nk\dbinom{n}{i} & = \sum\limits_{i=1}^ni\frac{n!}{i!(n-i)!}\\ & = n\sum\limits_{i=0}^{n-1}\frac{(n-1)!}{i!(n-(i+1))!}\\ & = n\sum\limits_{i=0}^{n-1}\frac{(n-1)!}{i!(n-1-i))!}\\ & = n\sum\limits_{i=0}^{n-1}\dbinom{n-1}{i}\\ & =n2^{n-1}\\ \end{aligned}

总结

在大多数情况下，组合数学最常用的方面是计数问题，或直接根据题面公式计算。

在进行推导时，需灵活使用上述组合恒等式和定理进行代换和化简，必要时，也可以直接通过组合意义抽象出具体问题，需要大量的做题经验。

卡特兰数

卡特兰数是组合数学中的一种常见数列，前几项如下：

1，1，2，5，14，42，132，429，1430，4862，……

公式

从最经典的进出栈问题开始理解，通常大多数卡特兰数问题可以转化为这个。

由简单容斥可得，合法出栈序列 = 总序列个数 - 非法序列个数。

进栈抽象为 + 1 ，出栈抽象为 - 1 。

则序列总个数为 $C_{2n}^n$ 。

非法序列个数比较麻烦，需要转化一下。

找到每个非法序列第一个前缀和小于 0 的地方，将这之前的序列全部反转，容易证明这和原序列一一对应。

那么非法序列总个数即为 $C_{2n}^{n+1}$ 。

合法序列总个数即为： ($C_n$ 即为卡特兰数的第 $n$ 项)

C_n=C_{2n}^n-C_{xn}^{n-1}=\frac{C_{2n}^{n}}{(n+1)}

由组合恒等变换得到递推公式：

C_n=C_{n-1}\frac{4n-2}{n+1}

顺便给一下最基础的通式吧：

C_n= \begin{cases} 1&n=0,1\\\sum\limits _ {i=0}^{n-1} C_iC_{n-i-1}&n\ge 2 \end{cases}

组合意义/应用

$n$ 个元素入栈序列为 $1$ 至 $n$ ，出栈序列的总个数。
$n$ 对括号所能组合成的合法括号序列的个数。
$n+1$ 个节点所能构成的形状不同的满二叉树的总个数。
$n$ 个节点的形状不同的二叉树的总个数。
……

斯特林数

前置知识

上升幂：

x^{\overline n}=x(x+1)(x+2)…(x+n-1)

下降幂：

x^{\underline n}=x(x-1)(x-2)…(x-n+1)

第一类斯特林数

定义

把 1 到 $n$ 排列成 $k$ 个非空循环(或者叫做圆排列?)的方案数，写作 $s(n,k)$ 或 $\begin{bmatrix}n\k\end{bmatrix}$ 。

公式

加入 $n$ 即可看作自身构成循环或加入到前 $n$ 个数前，易得递推公式:

\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}

推广

$s(0,0)=1$
$s(n,0)=0$
$s(n,1)=(n-1)!$
$s(n,n-1)=C_n^2$

第二类斯特林数

比第一类斯特林数更为常用。

定义

把 1 到 $n$ 分成 $k$ 个集合的方案数，写作 $S(n,k)$ 或 $\begin{Bmatrix}n\k\end{Bmatrix}$ 。

公式

和第一类斯特林数类似的：

\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}

推广

$S(0,0)=S(n,1)=1$
$S(n,0)=S(n,0)=0$
$S(n,2)=2^{n-1}-1$

斯特林数和上升/下降幂的应用

原本是打算自己找资料的，但看到几篇博文写的实在太好，就摆了。

https://www.luogu.com.cn/blog/wangrx/finite-calculus

https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan

ChengJY's blog