• 原地址

组合数学学习笔记

组合数学常用公式

基本公式

1. 排列：

$$A_{n}^r=\frac{n!}{(n-r)!}$$

1. 组合：

$$C_{n}^r=\frac{n!}{r!(n-r)!} \\ \dbinom{n}{r}=\frac{n!}{r!(n-r)!}$$

1. 二项式定理：

$$n\in \mathbb{N},(x+y)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^ky^{n-k}$$

1. 广义二项式定理：

若

$$\left | x \right |<1,\alpha\in\mathbb{R}$$

则

$$(1+x)^\alpha=\sum_{k=0}^{\infty}\dbinom{\alpha}{k}x^k$$

这里 。当 时，右侧幂级数不一定收敛。

组合公式

1. 杨辉恒等式：

$$\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$$

1. 等效代换：

$$\dbinom{n}{m}=\dbinom{n}{n-m}$$

1. 连续应用1：

$$\dbinom{n+r+1}{r}=\sum_{i=0}^{r}\dbinom{n+i}{i}$$

1. 组合意义：

$$\dbinom{n}{m}\dbinom{m}{r}=\dbinom{n}{r}\dbinom{n-r}{m-r}$$

1. 4中 时的特例：

$$\dbinom{n}{m}\dbinom{m}{1}=\dbinom{n}{1}\dbinom{n-1}{m-1}\\ m\dbinom{n}{m}=n\dbinom{n-1}{m-1}$$

1. 组合意义：

$$\dbinom{n+m}{r}=\sum_{i=0}^{r}\dbinom{n}{i}\dbinom{m}{r-i}$$

1. 性质5与二项式定理：

$$\sum_{i=0}^{n}i\dbinom{n}{i}=n2^{n-1}$$

常用数及其推论

第一类斯特林数

排成 个圆排列也就是 排列的个数，满足 向 连边后，形成 个环的图。我们用 来表示 个节点， 个环的斯特林数。

考虑递推意义，有一下两种情况：

1. 新加入的点自己成为一个新环，方案数为 。

2. 新加入的点加在了任意一个原有的环中的任意一个点的后续，方案数为 。

总递推式为 。

第二类斯特林数

将 个元素划分到 个集合的方案数，集合不能为空。我们用 来表示 个元素， 个集合的斯特林数。

依旧是考虑递推意义，有两种情况：

1. 和第一类斯特林数一样，新加入的元素自己成为一个新集合，方案数为 。

2. 新元素加入任意一个已有集合，方案数为

总递推式为 。

卡特兰数

卡特兰数是以下四类问题的通解：

1. 个数 依次进栈，问有多少种不同的出栈序列。

2. 求长为 的合法括号序列的数量。

3. 求 个点，每个非叶子节点都恰好有两个儿子的有根、无标号、区分左右儿
   子的二叉树个数。

4. 给定 的网格图，问有多少种 到 的路径使
   得其不越过对角线。

问题转化：

1. 入栈为 ，出栈为 ，过程中序列操作值保证大于等于 。

2. 左括号 ，右括号 ，同问题 1。

3. 在 dfs 整棵树时，左儿子为左括号，右儿子为右括号，转化为问题2。

4. 向右走为左括号，向上走为右括号，转化为问题 2。

这个问题的答案称作卡特兰（Catalan）数 。

我们通过问题4来求出卡特兰数的表达式：

若没有对角线的限制，方案数为 。

若接触了次对角线 ，则从其第一次接触的位置起关于这条对角线对称，终点变为 ，不合法路径与 到 的路径一一对应，所以 。