组合数性质

1.

​ $C_n^0 + C_n^1 + C_n^2 ··· + C_n^{n-1} + C_n^n = 2^n$

2.

​ $C_n^0 + C_n^2 + C_n^4 ··· = C_n^1 + C_n^3 + C_n^5 ··· = 2 ^{n-1}$

3.

​ $0 * C_n^0 + 1 * C_n^1 + 2 * C_n^2 + ··· + n * C_n^n = n * 2^{n-1}$

4.

​ $C_n^m = \frac{n}{m} * C_{n-1}^{m-1}$

​ $C_n^{m+1} = \frac{n-m}{m+1}C_n^m$

5.

​ $({C_n^0})^2 + ({C_n^1})^2 + ··· + ({C_n^n})^2 = C_{2n}^n$

6.

​ $\sum_{i=0}^n C_i^k = C_{n+1}^{k+1}$

7.

​ $C_n^m$为奇数时有 $n$ & $m = m$

​ 模数为2时也满足$n$ & $m = m $(根据卢卡斯定理)，可将问题转化成二进制下的问题，然后考虑数位dp

8.

​ $C_n^k * C_k^r = C_n^r * C_{n-r}^{k-r}(k \geq r)$

9.

$C_{n+r+1}^{r} = C_{n}^{0}+C_{n+1}^{1}+···+C_{n+r-1}^{r-1}+C_{n+r}^{r}$

$C_{n+r+1}^{n+1} = C_{n}^{n}+C_{n+1}^{n}+···+C_{n+r}^{n}$

10.

$\sum_{i=0}^{i=s}C_s^i*i = s2^{s-1}$

11.

$\sum_{i=0}^{min(x,y)}C_x^iC_y^i = C_{x+y}^x$

12.

$\sum_{i=0}^{k}C_{n}^{i}C_m^{k-i}=C_{n+m}^{k}$

1691377380501

二项式定理

​ 1.一般二项式定理($n$为非负整数)

​ $(a + b) ^ n = \sum_{k=0}^{n} C_n^k a ^ kb^{n-k}$

二项式反演

二项式反演为一种反演形式，常用于通过 “指定某若干个” 求 “恰好若干个” 的问题。

考虑解决至少、至多的问题，这个问题解决就是 $f(n)$ 的值。一般是会比较好求的，用点数学方法或者DP就可以解决。然后，用二项式反演，求出 $g(n)$。这就是恰好的方案数

形式零

$f(n)=\sum_{i=0}^{n}(-1)^iC_n^ig(i) \Longleftrightarrow g(n)=\sum_{i=0}^{n}(-1)^iC_n^if(i)$

形式一

$f(n)=\sum_{i=m}^{n}C_n^ig(i) \Longleftrightarrow g(n)=\sum_{i=m}^{n}(-1)^{n-i}C_n^if(i)$

形式二

$f(n)=\sum_{i=n}^{m}C_i^ng(i) \Longleftrightarrow g(n)=\sum_{i=n}^{m}(-1)^{i-n}C_i^nf(i)$

组合意义 : 记 $f(n)$ 表示 “钦定选 $n$ 个”，$g(n)$ 表示 “恰好选 $n$ 个”，则对于任意的 $i≥n$ ，$g(i)$ 在 $f(n)$ 中被计算了 $C_i^n$ 次，故 $f(n)=\sum_{i=n}^{m}C_i^n g(i)$ ，其中 $m$ 是数目上界。

多重集合的排列数

有$n$种物品，每种物品有$c_i$个，将物品全排列的方案数为

$\frac{\sum_{i=1}^{n} c_i}{\prod_{i=1}^{n} c_i}$

多重集的组合数

有$n$种物品，每种物品有$c_i$个，从中选出 $m \ (m \leq c_i)$ 个物品的方案数为

$C_{m + n - 1}^{n - 1}$

若没有对于 $m$ 的限制

  1. 多项式

  2. $dp_{i+1,j}=dp_{i+1,j-1}+dp_{i,j}-dp_{i,j-1-c_i}$

    $dp_{ij} : $前 $i$ 种物品拿了 $j$ 个的方案数

    在计数DP中，为了避免重复计算，同一类物品往往要一起处理

错排

$f(n) = (n - 1)(f(n - 1) + f(n - 2))$

​ $= nf(n-1) +(-1)^n$

随着元素的增加，一个随机排列是错排的概率接近$\frac{1}{e}$

圆排列

从 $n$ 个不同元素中选取 $r$ 个元素，不分首尾地围成一个圆圈的排列叫做圆排列，其排列方案数为

$\frac{A_n^r}{r}$

可重复组合数

多重集的排列数$(r < n_i)$

$H_n^r = C_{n+r-1}^r$

分装问题

将 $n$ 个球放入 $r$ 个盒子称为分装问题

  1. $n$ 个球完全相同，$r$ 个盒子完全不相同，允许空盒 ： $C_{n+r-1}^{r-1}$
  2. $n$ 个球完全相同，$r$ 个盒子完全不相同，不允许空盒 ：$C_{n-1}^{r-1}$
  3. $n$ 个球完全相同，$r$ 个盒子完全相同，允许空盒 ：$\sum _{k=1}^{r}P(n,k)$，分拆数
  4. $n$ 个球完全相同，$r$ 个盒子完全相同，不允许空盒($n \geq r $) ：$P(n,r)$，分拆数
  5. $n$ 个球完全不相同，$r$ 个盒子完全不相同，允许空盒 ：$r^n$
  6. $n$ 个球完全不相同，$r$ 个盒子完全不相同，不允许空盒 : $r!S(n,r)$，第二类斯特林数
  7. $n$ 个球完全不相同，$r$ 个盒子完全相同，允许空盒 ：$\sum _{k=1}^{r}S(n,k)$，第二类斯特林数
  8. $n$ 个球完全不相同，$r$ 个盒子完全相同，不允许空盒: $S(n,r)$，第二类斯特林数

Lucas 定理

​ 若$p$是质数，则对于任意整数 $1 \leq m \leq n$, 有：

$C_n^m \equiv C_{n \ mod \ p}^{m \ mod \ p} * C_{n/p}^{m/p}(mod \ p)$

​ 也就是把 $n$ 和 $m$ 表示成 $p$ 进制数， 对 $p$ 进制下的每一位分别计算组合数，最后再乘起来

ll C(ll n, ll m)
{
	if (m < 0 || m > n) return 0;
	if (m == 0) return 1;
	if (m < p && n < p)
		return fac[n] * invfac[m] % p * invfac[n - m] % p;
	return C(n / p, m / p) * C(n % p, m % p) % p;
}

若$(_a^{a+b}) \neq 0$，则说明$a + b$在$p$进制里加法不进位

斐波那契数列

性质

  1. $\sum_{i=1}^nf_i = f_{n+2}-1$
  2. $\sum_{i=1}^nf_{2i-1} = f_{2n}$
  3. $\sum_{i=1}^nf_{2i} = f_{2n+1} - 1$
  4. $\sum_{i=1}^n(f_i)^2 = f_nf_{n+1}$
  5. $f_{n+m} = f_{n-1}f_{m-1} + f_nf_m$
  6. $(f_n)^2 = (-1)^{n-1} + f_{n-1}f_{n+1}$
  7. $f_{2n-1} = (f_n)^2 - (f_{n-2})^2$
  8. $f_n = \frac{f_{n+2} + f_{n-2}}{3}$
  9. $\frac{f_i}{f_{i-1}} \thickapprox \frac{\sqrt{5} - 1}{5} \thickapprox 0.618$
  10. $f_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$

Catalan数列

$Cat_n = Cat_0 * Cat_{n-1} + Cat_1 * Cat_{n-2} + ··· + Cat_{n-1}*Cat_0(n \geq 2)$

$ = Cat_{n-1} * \frac{4n-2}{n+1}$

$= C_{2n}^{n} - C_{2n}^{n-1}$

$ = \frac{C_{2n}^{n}}{n+1}$

Cat = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670}

​ 应用：

1.n个左括号和n个右括号组成的合法括号序列的数量为 $Cat_n$

2.$1,2,···,n$ 经过一个栈， 形成的合法出栈序列的数量为 $Cat_n$

3.n 个节点构成的不同二叉树的数量为 $Cat_n$

4.在平面直角坐标系上， 每一步只能向上或向右走， 从$(0,0)$走到$(n,n)$并且除两个端点外不接触直线$y = x$的路线数量为 $2Cat_{n-1}$

5.在平面直角坐标系上， 每一步只能向上或向右走， 从$(0,0)$走到$(n,n)$，在任一时刻，向右走的次数不能少于向上走的次数，方案数为 $Cat_{n}$

6.在圆上选择$2n$个点，将这些点成对连接起来使得所得到的$n$条线段不相交的方法数为 $Cat_n$

7.一个有$n$个定点的凸多边形区域划分成三角形区域的方法数为$Cat_{n-2}$

斯特林数(Stirling)

第一类斯特林数 $s(n,m)$，也记为 $[_m^n]$。表示将 $n$ 个不同元素构成 $m$ 个圆排列的方案数。同时还分为无符号第一类斯特林数 $s_u(n,m)$ 和有符号第一类第一类斯特林数 $s_s(n,m)$。

第二类斯特林数 $S(n,m)$，也记为 ${_m^n}$。表示将 $n$ 个不同的元素划分成 $m$ 个集合的方案数。

第二类斯特林数

​ ${m^n} = {{m-1}^{n-1}} + m{_{\ \ m}^{n-1}}$

​ ${m^n} = \sum{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$

第一类斯特林数

​ $[m^n] = [{m-1}^{n-1}] + (n-1)[_{\ \ m}^{n-1}]$

上升幂

​ $x^{\bar{n}} = \prod_{k=0}^{n-1}(x+k) = x(x+1)(x+2)\dots(x+n-1)$

​ 1).上升幂转普通幂

​ $x^{\bar{n}} = \sum_{k=0}^n[_k^n]x^k$

​ 2).普通幂转上升幂

​ $x^n = \sum_{k=0}^n(-1)^{n-k}x^{\bar{k}}$

下降幂

​ $x^{\underline{n}} = \frac{x!}{(x-n)!} = \prod_{k=0}^{n-1}(x-k)$

​ 1).下降幂转普通幂

​ $x^{\underline{n}} = \sum_{k=0}^n_k^n^{n-k}x^k$

​ 2).普通幂转下降幂

​ $x^n = \sum_{k=0}^{n}{_k^n}x^{\underline{k}}$

贝尔数

$B_n$ 表示将 $n$ 个集合划分成若干个非空集合的方案数。

$B_n = \sum_{i=0}^{n-1}C_{n-1}^{i}B_i$

$B_n = \frac{1}{e}\sum_{i \geq0}\frac{i^n}{i!}$

$B_n = \sum_{i=0}^nS(n,i)$

$B_n$ 等于第二类斯特林数第 $n$ 行之和

对于质数$p$ ，$B_{p^m+n} = mB_n + B_{n+1}$

Bell数列模质数 $p$ 意义下的循环节长度为 $\frac{p^p-1}{p-1}$

B = {1, 1, 2, 5, 15, 52, 203}

贝尔三角

用以下方法构造一个三角矩阵（形式类似杨辉三角形）

  1. 第一行第一项为 1 $(a_{1,1} = 1)$
  2. 对于 $n > 1$，第 $n$ 行第一项等于第 $n - 1$ 行的第 $n - 1$ 项 $(a_{n,1} = a_{n-1,n-1})$
  3. 对于 $m, n > 1$，第 $n$ 行的第 $m$ 项等于它左边和坐上角两数之和 $(a_{n,m} = a_{n,m-1} + a_{n-1,m-1})$

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

52 67 87 114 151 203

每行的首项是贝尔数。可以利用这个三角形递推求出Bell数

分拆数

$p_n$ : 自然数 $n$ 的分拆为多个正整数的和的方案数， 特殊的 $p_0 = 1$

1672724835573

该递推公式时间复杂度为$O(n\sqrt{n})$

也可以用完全背包 $O(n^2)$求解 $ p_n$

$k$ 部分拆数,$p(n,k)$: 自然数 $n$ 分拆为 $k$ 个正整数的和的方案数

$p(n,k)=\sum_{j=0}^{k}p(n-k,j)$

$p(n,k) = p(n-1,k-1) + p(n-k,k)$

用该递推式时间复杂度为 $O(nk)$

1672724033450

最大 $k$ 分拆数 ：自然数 $n$ 分拆后最大的正整数为 $k$ 的方案数

根据 Ferrers 图与共轭可知， $n$ 的最大 $k$ 拆分数等于 $k$ 部分拆数，都为 $p(n,k)$

互异拆分数($pd_n$) ：自然数 $n$ 拆分后各部分不相同的拆分数

互异$k$部分拆数,$pd(n,k)$ : 自然数 $n$ 拆分为 $k$ 个部分，且各部分不同的方案数

$pd(n,k)=pd(n-k,k-1)+pd(n-k,k)$

1672727028587

cayley定理 (凯莱定理):

​ 有n个标志节点的树的数量等于$n^{n-2}$

生成函数

泰勒展开式

$\frac{1}{1-x}=1+x^2+x^3+x^4 + \dots$

$\frac{1}{(1-x)^2}=1+2x+3x^2+ \dots$

$e^x = 1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots$

$e^{-x} = 1-\frac{x}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}+\dots$

$e^{px}=1+p\frac{x}{1!}+p^2\frac{x^2}{2!}+p^3\frac{x^3}{3!}+\dots$

$\frac{e^x+e^{-x}}{2}=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\dots$

$\frac{e^x-e^{-x}}{2}=\frac{x}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\dots$

1.普通型母函数(OGF)

普通型母函数的乘法和“多重集的组合问题”有关

​ 把一个数列的普通型母函数乘以 $1+x+x^2+x^3+ \dots$ 相当于求其前缀和

​ 把一个数列的普通型母函数乘以 $1-x$ 相当于求其差分

2.指数型母函数(EGF)

指数型母函数的乘法和“多重集的排列问题”有关。

不积跬步，无以至千里！