知识点讲解
排列组合
圆周排列
从$n$个不同元素中无重复地取出$k(1≤k≤n)$个元素排在一个圆周上，称为$n$个不同元素的一个圆周排列，简称k-圆排列
圆周排列个数为
$$\frac{A^k_n}{k} = \frac{n!}{k\cdot(n-k)!}$$
1 重复组合
从$n$个不同元素中无序但可重复取出$k(1≤k≤n)$个元素，称为$n$个不同元素中取出$k$个元素的一个重复组合，简称k-可重组合
重复组合个数为
$$C^{k}_{n+k-1}$$
2 组合数性质
$C^k_n = C^{n-k}_n$
$C^k_n = C^{k-1}_{n-1} + C^{k}_{n-1}$
$C^k_n = C^{k-1}_{n-1} \times n \div k$
3、求组合数方法
1、阶乘 (定义法)
2、杨辉三角二维递推 (递推式$C^m_n=C_{n-1}^{m-1}+C_{n-1}^{m}$)
3、一维递推 3 个公式 (易从定义式推出)：
$C^m_n=\frac{n}{n-m} C^m_{n-1}$
$C^m_n=\frac{n-m+1}{m} C^{m-1}_n$
$C^m_n = \frac nm C^{m-1}_{n-1}$
4、优化：$C^m_n = C^{n-m}_n$
卡特兰数
Catalan数
递推公式：$f(n)=\sum_{i=0}^{n-1}f(i)f(n-i-1)$(用于乘法原理寻找规律)
通项公式：$\text{Catalan}_n=\frac{1}{n+1}C^n_{2n}$
性质：$\text{Catalan}_n=C_{2n}^n-C_{2n}^{n-1}$, 证明直接用组合数定义通分即可
常见题型：
1
由$n$个1和$n$个$0$构成$2n$项的数列$a_i$
其满足任意前缀$1$个数不比$0$少，这样的数列个数为$\text{Catalan}_n$
变式1：括号正确匹配序列个数是$\text{Catalan}_n$
变式2：$n$个数入栈后的出栈的排列总数是$\text{Catalan}_n$
变式3：对于一个$n \times n$的正方形网格，每次只能向右或者向上移动一格，那么从左下角到右上角所有在副对角线(下图中虚线)右下方的路径总数为$\text{Catalan}_n$
变式4：对于集合$[1,n], n \in \text{Z}$，将集合元素两两分为$n$个子集，若任意两个子集都不交叉，那么我们称此划分为一个不交叉划分, 不交叉的划分数就是$\text{Catalan}_n$
变式5：$n$层的阶梯切割为$n$个矩形的切法数是$\text{Catalan}_n$
2
$dp(i)=dp(i) \cdot dp(n-i-1)$
变式1：三角剖分数为$\text{Catalan}_n$
变式2：$2n$个点均匀排列在圆上，两两连线不相交的方案数为$\text{Catalan}_n$
变式3：平面上连接可以形成凸包的$2n$个点分成$2$个一组连成$n$条线段，两两线段之间不相交的情况总数是$\text{Catalan}_n$
错位排列
错位排列
Bzoj 4517
错位排列可以递推出来，设$n$个数的错位排列是$D(n)$，则有
$$
D(n)=(n-1)(D(n-1)+D(n-2))
$$
证明：考虑$n$这个数放到了$k$位置，有$n-1$种情况。
然后考虑$k$这个数放在哪
1、$k$这个数放在$n$位置，那么显然$n,k$全部被排完，变成了$D(n-2)$的局面
2、$k$这个数不放在$n$位置，那么现在先不放$k$，然后现在我们已经少了一个$n$数和$k$位置，那么其实$k$数等价于现在的$n$数，变成了$D(n-1)$的局面
这里还有一个通项式子
$$
D(n) = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} \cdots + (-1)^n \frac{1}{n!} \right)
$$
证明即使用容斥原理。
还有一种容斥的方法，即先考虑有几个人站在了原来的位置，然后可以容斥
即考虑选出人出来在原来的位置，可以得到
$$
\text{Ans} = \sum_{k = 0}^{n}{(-1)^k\binom{n}{k} (n - k)!}
$$
容斥原理
容斥基本思想就是题目所求的东西有多个限制，我们只满足或者不满足某些限制，然后其他的不管，然后再进行容斥。
容斥套路
1、全部 - 至少一个 + 至少两个 - …… = 一个也没有 (也就是最基础的容斥)
2、所有 - 一个也没有 = 至少有一个 (一些补集转化)
3、恰好有 k 个的：二项式反演 (广义容斥)
4、与质因子相关的容斥用$\mu$为容斥系数。
5、直接求不方便的，而求至少却很容易的
最基础的容斥
即为全部 - 至少一个 + 至少两个 - …… = 一个也没有这样的容斥，是广义容斥恰好有 $k$ 个的$k=0$的特例
例题：Bzoj 4665，多重集的组合数
广义容斥 (二项式反演)
一般题目是求恰好有 k 个的
即若有
$$
F(i)= \sum \limits_{j=i}^{n} C^{i}_{j} \times g(j)
$$
则有
$$
g(i)= \sum \limits_{j=i}^{n} (-1)^{j-i} \times C^{i}_{j} \times F(j)
$$
例题：Bzoj 3622 已经没有什么好害怕的了 ，SDOI spring，CF 285E
容斥系数
有$n$种属性，若干物品。假设我们可以容易地计算出，$g(S)$表示包含$S$集合的物品个数。且给定$w(k)$表示，当物品拥有$k$个属性时它的价值是多少。求所有物品的价值和。
我们需要确定一个容斥系数$f(k)$，使得$Ans=\sum \limits_{s\in S}g(s)f(|s|)$。
同上，考虑令每个物品被算入的贡献等于我们想要的数。即对于一个拥有$k$种属性的物品，需要满足
$$
\sum_{i=1}^kC_k^if(i)=w(k)
$$
$f(i)$ 是可以$O(n^2)$递推的。假设已知$f(1)…f(k−1)$
$$
\sum_{i=1}^kC_k^if(i)=w(k) \Rightarrow f(k)=w(k)-\sum_{i=1}^{k-1}C_k^if(i)
$$
大部分题中是用$O(n^2)$/手推来找规律算的。
最基本的容斥原理的$w(k)$即为$[k=0]$
例题1：“玲珑杯” 线上赛 Round#17 B 当咸鱼也要按照基本法
给定$m$个数$A_i$和$n$。求$[1,n]$中有多少个数能被奇数个$A_i$整除。
$T≤1000$组数据，$n≤10^5$, $m≤15$。
发现$m$很小，可以枚举子集，然后我们很方便求出每个子集在$[1,n]$的整除个数, 然后可以考虑容斥，这里只需要整除个数为奇数的，所以我们可以列出
$$
\sum_{i=1}^kC_k^if(i)=k \mod 2
$$
然后可以计算容斥系数。也可以打表后发现容斥系数的规律
例题2：
求出错位排列中，如果有$k$个人在原来的位置，价值为$w(k)$，求所有排列的价值
$$
\sum_{i=1}^kC_k^if(i)=w(k)
$$
$\mu$函数为容斥系数
求区间$[1,n]$不是完全平方数的正整数倍的数的个数。
是完全平方数的正整数倍的数是很好计数的，我们可以考虑容斥。
我们发现这个容斥就是用$\mu$作为容斥系数的，具体可以看本博客莫比乌斯反演的部分
然后答案就是
$$
\sum_{i=1}^{\sqrt n} \left \lfloor \frac{n}{i^2} \right \rfloor \times \mu(i)
$$
类似的题还有Codeforces 439E
计数题技巧
思考容斥
按顺序计数，不重不漏
「Loj 6185」烷基计数 (按子树大小)
「CH 5302」金字塔
画烷烃的同分异构体 (枚举直径)
补集转化
当正着做不方便时就补集转化。例如一些概率的计算
DP
大部分计数题都和DP递推有关
划分子问题方法
1、正常方法划分
此类问题比较多
2、以0、1划分
1、Catalan数(栈、只向上向右)
2、「poj 1737」Connected Graph
