组合数学
基础概念
加法和乘法原理
加法原理
同一步下的不同选择，可以通过累加得到方案数。
乘法原理
整个流程的方案数可以由每一步的方案数相乘得到。
有了加法原理和乘法原理，就可以解决一些没有选择导致分支的问题了。
例题1
有 /(n/) 个篮子，第 /(i/) 篮子有 /(a_i/) 有水果，每个水果各不相同，问每个篮子选出一个得到的水果的方案数。
解答：
用加法和乘法原理，那么每个篮子选出的方案数为 /(a_i/) ，总共就是 /(/prod a_i/) 种方案。
排列和组合
排列数
从 /(n/) 个不同元素中选出 /(m/) 个，按照一定顺序排列，简而言之就是选出一个数列的方案数。
组合数
从 /(n/) 个不同元素中选出 /(m/) 个的方案数，换句话就是选出一个集合的方案数。
其实排列数可以看做在选出 /(m/) 个数后还有对这 /(m/) 个数做一个全排列，所以多一个 /(m!/)
因为组合数我们用得多一点，所以我们一般用二项式系数来表示组合数，也就是说：
然后定义一些离谱的情况： /(m>n/) 或者 /(m<0/) 时， /(/binom{n}{m}=0/)
多重组合数
多重组合数和多重集排列数
多重集合，也叫可重集。一个多重集合 /(S=/{a_1/cdot n_1,a_1/cdot n_2,…,a_m/cdot n_m/}/) （/(n_i/) 表示元素个数， /(a_i/) 表示元素）的排列数（也被称为多重组合数）：
相当于是所有数的全排列数再除去相同元素的全排列数。
顺便补充一嘴：
多重集组合数
一个多重集合 /(S=/{a_1/cdot n_1,a_1/cdot n_2,…,a_k/cdot n_k/}/) 的组合数，就是从中选出 /(r/) 个，得到不同可重集的方案数。
这个怎么弄？先来个简单的的，我们使 /(r<n_i/)。
这个我们考虑用插板法来求。可以看做我们现在有 /(r/) 个小球，然后现在往里面插板来分组。
最初的时候，我们有 /(r/) 个球，那么我们有 /(r+1/) 个位置是可以插空的。当我们插入了一个板子之后，我们可以插入的位置就又多了一个，后面就同理了。
于是乘法原理加上除去板子的全排列可以得到答案：
现在考虑把 /(r<n_i/) 的限制拿掉，怎么做？
这个要容斥原理！但是在这篇博客里我们还没有学！超纲了，我们等会讲容斥的时候再说。
不相邻排列
/(1/to n/) 个自然数中选出 /(k/) 个，使得他们互不相邻的方案数？
答案是 /(/binom{n-k+1}{k}/) ，相当于是留了 /(k-1/) 个空加在每两个被选择的位置中间。
组合恒等式
1.对称式
证明：
从组合意义上来说容易证明。因为你 /(n/) 中拿 /(m/) 个等价于有 /(n-m/) 个不拿。
2.二项式定理
证明：
从组合意义来证明。
我们把 /((x+y)^n/) 看作是有 /(n/) 个 /((x+y)/) 相乘，那么得到一个 /(x^ay^{n-a}/) 相当于是从 /(n/) 个 /((x+y)/) 中选出 /(a/) 个 /((x+y)/) 中的 /(x/) 相乘，那么结果的多项式中就有一项是 /(/binom{n}{a}x^ay^{n-a}/) 。所以的这种项都满足这种情况，那么公式可得。
Q.E.D.
其实不一定要求必须是两元的，多元的也是同理。
然后我们可以得到多项式定理：
证明：
同二项式定理证明，对于 /(x_1^{n_1}x_2^{n_2}…x_m^{n_m}/) 这一项的系数为 /(/binom{n}{n_1}/binom{n-n_1}{n_2}…/binom{n-n_1-n_2-…-n_{m-1}}{n_m}/) 。
展开发现可以抵消一些东西，于是上面的系数就等于：
Q.E.D.
3.递推式1
帕斯卡定理，你也可以说是杨辉三角。我们知道 /((x+y)^n/) 得到的多项式是系数满足杨辉三角的，我们知道了二项式定理的话，发现这个东西实际上是组合数，所以实际上是组合数的同层展开是满足杨辉三角的。但是证明的话显然不能这么证明。
证明：
我们一个数一个数看这个数是否选取，假设现在已经看了 /(n-1/) 个数，选了 /(x/) 个数。我们考虑如果得到 /(/binom{n}{k}/)
那么接下来这个数选或不选分别造成 /(1/) 和 /(0/) 的贡献，也就是说：
如果接下来这个数选，那么只有 /(x=k-1/) 的情况符合条件。否则只有 /(x=k/) 的情况符合条件。于是加法原理把两种情况的方案数加起来即可。
Q.E.D.
4.特殊的二项式定理
实际上是 /((1+1)^n/) ，当然也可以从组合意义上证明。
实际上是 /((1-1)^n/) ，我称之为第一类二项式反演。
5.递推式2
按定义来就没了，简单提一下。
6.积式
定义展开左边上下分子分母同乘 /((n-k)!/) 即可证明。
7.变下项求和式
证明：
Q.E.D.
证明和上面差不多，就不证了。其实你想拆可以一直这么拆。
8.变上项求和式
证明：
采用组合分析。
指定 /(n+1/) 个数的集合 /(S=/{a_1,a_2,…,a_{n+1}/}/)
先考虑右边的组合意义，即从 /(n+1/) 个数中选出 /(k+1/) 个。
左边的组合意义：相当于是总共 /(n+1/) 种不累加的情况的加法原理。
第一种：在指定必须选择 /(a_1/) ，然后从剩余的 /(n/) 个数中选择 /(k/) 个，方案数 /(/binom{n}{k}/)
第二种：在指定必须不选择 /(a_1/) 而选择 /(a_2/) ，然后从剩余的 /(n-1/) 个数中选择 /(k/) 个，方案数 /(/binom{n-1}{k}/)
第三种：在指定必须不选择 /(a_1,a_2/) 而选择 /(a_3/) ，然后从剩余的 /(n-2/) 个数中选择 /(k/) 个，方案数 /(/binom{n-2}{k}/)
第 /(n+1/) 种：在指定必须不选择 /(a_1,a_2,…,a_n/) 而选择 /(a_{n+1}/) ，然后从剩余的 /(0/) 个数中选择 /(k/) 个，方案数 /(/binom{0}{k}/)
总体的组合意义 /(/sum_{i=0}^n{/binom{i}{k} }/) 等价于从 /(n+1/) 个数中选出 /(k+1/) 个，那么等式左右两边组合意义相同，等式成立。
Q.E.D.
9.积和式
证明：
指定集合 /(A=/{a_1,a_2,…,a_m/}/) 和 /(B=/{b_1,b_2,…,b_n/}/)。
右边问题等价于从 /(A,B/) 两个集合中选出 /(r/) 个的方案数。
左边问题等价于：
对于 /(k/in [0,r]/)，先在 /(A/) 中先取出 /(k/) 个，然后在 /(B/) 中选出 /(r-k/) 个的总方案数。
即 /(A,B/) 中总共选出 /(r/) 个的方案数。
所以左右两个问题组合意义等价，等式成立。
Q.E.D.
10.第二类二项式反演
证明：
已知：/(g(n)=/sum_{i=0}^n(-1)^i/binom{n}{i}f(i)/)
则：
Q.E.D.
然后我们还可以得到一个扩展：
证明：
令 /(G(n)=(-1)^ng(n)/) ，有：
若 /(f(n)=/sum_{i=0}^n(-1)^i/binom{n}{i}G(i)/) 成立，有 /(G(n)=/sum_{i=0}^n(-1)^i/binom{n}{i}f(i)/)
即
当 /(n/) 为偶数，则 /(n-i/) 与 /(i/) 奇偶性相同，有 /(g(n)=/sum_{i=0}^n(-1)^{n-i}/binom{n}{i}f(i)/)
当 /(n/) 为奇数，则 /(n-i/) 与 /(i/) 奇偶性相反，同样有 /(g(n)=/sum_{i=0}^n(-1)^{n-i}/binom{n}{i}f(i)/)
由此有 /(g(n)=/sum_{i=0}^n(-1)^{n-i}/binom{n}{i}f(i)/)
Q.E.D.
圆排列
考虑 /(n/) 个人围成圆的圆排列方案数为 /(Q^n_n/) 。我们发现对于一个圆，从每个地方断开都可以形成一个新的排列，所以：
/(Q_n^n/times n=A^n_n/Rightarrow Q^n_n=/frac{Q^n_n}{n}=(n-1)!/)
所以 /(Q^m_n=/frac{A^m_n}{m}=/frac{n!}{r(n-r)!}/)
错位排序
设 /(f(n)/) 表示将 /(n/) 个编号为 /(1,2,…,n/) 的物品，放到编号为 /(1,2,…,n/) 的位置中，使每个物品放置的位置的编号与物品的编号都相同的方案数。
我们考虑递推，考虑目前放置第 /(n/) 个物品，先暂时放在第 /(n/) 个位置，而保证其他 /(n-1/) 个物品都放在 /([1,n-1]/) 的位置。然后考虑前面的一个物品和第 /(n/) 号物品交换位置，可知 /(f(n)/) 只能由两种情况递推而来。
第一种情况：前面的 /(n-1/) 个物品全部错位。这个直接就是每个物品都可以换。总共 /(n-1/) 种交换方法。
第二种情况：前面 /(n-1/) 个中除一个物品外全部错位。/(n/) 必然与这个不错位的物品换位，这个不错位物品有 /(n-1/) 种可能。
那么可得递推式：
鸽巢原理
假设有 /(n+1/) 个物品，那么将物品分为 /(n/) 组后，至少有一组含有两个及以上的物品。
证明：
假设每个分组都只有至多 /(1/) 个物品，那么最多有 /(n/) 个物品，与有 /(n+1/) 个物品的事实矛盾。
由此得证。Q.E.D.
一个扩展：
将 /(n/) 个物品分为 /(k/) 组，至少存在一个分组含有大于等于 /(/lceil/frac{n}{k}/rceil/) 个物品。
同样可以反证，简单就不证了。
容斥原理
有一个集合的集合 /(A=/{S_i/}/) ，那么：
证明：
如果对于每个元素都保证其出现一次，那么上式正确。
现在考虑对于一个元素 /(x/) ，证明其出现次数为 /(1/) 。假设它在集合 /(T_1,T_2,…,T_k/) 中出现。
那么其出现次数为：
可知出现次数为 /(1/) 。Q.E.D.
容斥原理的补集形式
右边容斥计算即可。
容斥原理一般化
对于两个关于集合的函数 /(f(S),g(S)/) ，如果：
那么有：
证明：
我们知道，对于一个关于集合的函数 /(F(P)=/sum_{T /subseteq (P)} (-1)^{|P|-|T|}/)，有：
那么我们就有：
Q.E.D.
还有一个倒过来的推论（补集形式）
如果：
那么有：
Min_max 容斥
对于 /(n/) 长全序序列 /(/{x_i/}/) ，/(S=/{1,2,…,n/}/)，有：
证明：
由于全序的对称性，我们可以知道 /(min/) 和 /(max/) 互换的话，效果也是一样的，所以我们只考虑证明第一个式子。
考虑构造一个系数 /(a_i/)，满足：
那么：
解释一下，这里是对于每个元素统计其贡献，对于第 /(i/) 大的数，我们可以知道其在所处集合作为最小值的集合的大小小于等于 /(i/) 。然后我们可以枚举集合的大小，显然比这个数大的有 /(i-1/) 个，我们从中再选出 /(j-1/) 个和当前这个数组成集合，那么上式可得。
然后我们知道，当 /(/sum_{j=1}^ia_j/binom{i-1}{j-1}=[i=k]/) 时，则构造成立。
令 /(g(n)=[n+1=k],f(n)=a_{n+1}/) 那么：
由二项式反演：
因此：
Q.E.D.
其实 min_max 容斥 在期望意义下也满足：
由期望线性性可知。
再论多重集组合数
我们前面提到过这个问题是需要容斥原理的。现在我们已经可以解决这个问题了。
回顾一下问题：一个多重集合 /(S=/{a_1/cdot n_1,a_1/cdot n_2,…,a_k/cdot n_k/}/) 的组合数，就是从中选出 /(r/) 个，得到不同可重集的方案数。每个数被选出 /(x_i/) 个。
设一个集合 /(S_i/) 表示不满足 /(x_i/le n_i/) ，即满足 /(x_i/ge n_i+1/) 的集合。
那么答案为：
后面那半部分我们容斥计算：
意义就是提前为其留出一些空间使其满足条件。
那么：
那么就可以切掉这个题了
但是这个题还有一个小技巧。
发现范围巨大，不好直接算组合数，但是 /(n/) 很小，我们把组合的求和转换为与 /(n/) 相关的算法。具体转换类似下方的做法。
卡特兰数（Catalan）
卡特兰数 /(Cat_n/) ，是下问题的答案：从 /((0,0)/) 出发，可以按照向量 /((1,0)/) 和 /((0,1)/) 游走，不越过（可以碰到）第一象限角平分线的情况下，到达 /((n,n)/) 的方案数。（就是只能在这条线下方走）
我们通过解决这个问题可得到卡特兰数的公式。
不越过第一象限角平分线 /(y=x/) ，等价于不触碰 /(y=x+1/) 。
然后你发现如果你碰到了直线 /(y=x+1/) ，那么可以发现从这个触碰点到 /((n,n)/) 的方案数和到 /((n-1,n+1)/) （/((n,n)/) 关于 /(y=x+1/) 的对称点）的方案数相同，因为在两边走是对称的。然后我们知道到达 /((n-1,n+1)/) 必然经过 /(y=x+1/) ，所以只需要到达 /((n,n)/) 的方案数减去到达 /((n-1,n+1)/) 的方案数即可。
即 /(Cat_n=/binom{2n}{n}-/binom{2n}{n-1}/)
通项公式
递推公式
然后初始状态 /(Cat_0=Cat_1=1/)
递归公式
证明：
对于 /(2n/) 长的括号序列，如果最后一个右括号与第 /(i/) 个左括号匹配，那么前 /((i-1)/) 个左括号的匹配肯定构成一个合法括号序列。这个 /(i/) 满足 /(1/le i/le n/) 。那么公式可得。
Q.E.D.
应用
我们发现其实对于所有的可以转化为如下问题的问题，都可以考虑卡特兰数列：
长度为 /(2n/) 的合法括号序列计数。
这个问题可以抽象上坐标轴，即从 /((0,0)/) 通过向量 /((1,1)/) 和 /((-1,-1)/) 到达 /((2n,0)/) 且不越过 /(x/) 轴。这个和我们上面的那个问题是等价的，通过关于 /(y=-1/) 对称可以得到相同的答案。
当然，如果遇到等价于我们最初提到的问题的问题，那么也是可以考虑卡特兰数列的。
我们看一些例子来判断一下：
1.有 /(2n/) 个人排成一行进入剧场。入场费 /(5/) 元。其中只有 /(n/) 个人有一张 /(5/) 元钞票，另外 /(n/) 人只有 /(10/) 元钞票，剧院无其它钞票，问有多少种方法使得只要有 /(10/) 元的人买票，售票处就有 /(5/) 元的钞票找零？
每有一个有 /(5/) 元的人进来，就多可以接一个 /(10/) 元的人，分别抽象成左右括号，那么符合卡特兰数列。
2.一个栈，加入顺序为 /(1,2,…,n/) ，问合法出栈顺序的方案数。
左右括号分别代表入栈和出栈，符合卡特兰数列。
3./(n/) 个节点，可以构成多少不同的二叉树？
假设 /(n/) 个节点的答案为 /(h(n)/)
于是我们每次固定根节点，有 /(h(n)=/sum_{i=1}^{n}h(i-1)h(n-i)/)
满足递归公式，符合卡特兰数列。
4.在圆上选择 /(2n/) 个点，求将这些点成对连接起来使得所得到的 /(n/) 条线段不相交的方案数。
选择两个点后其他点被分为两个部分，两边相互独立可以分治进行，满足递归公式，符合卡特兰数列。
5.对角线不相交的情况下，求将一个凸 /(2n/) 边形区域分成三角形区域的方案数。
这个和 /(4/) 的本质相同，就不再赘述。
例题
例题1
直接上公式就过了。
例题2
分析一下可以发现是卡特兰数列。我们可以发现一个结论，在奇数位放置一个数，那么它之前的数都小于它，它之后的数都大于他。然后可以分治处理，且当只有一个奇数位时，方案只有一个，因此满足卡特兰数列。
然后考虑怎么求这个卡特兰数，由于模数随机，我们不能逆元，递推公式就用不了了。
递归公式复杂度是 /(O(n^2)/) 的，显然不行。
那么只能考虑用通项公式求解。
把上下两个数约分一下。具体是把分子分母拆成乘法形式，开数组打个标记表示有多少个这个因数，然后它这些因数继续拆成质因数，最后统一计算每个系数即可。因为卡特兰数必定是整数，因此不用担心约分约不干净的情况。
这个可以增长一下经验，放个代码：
int n,mods; inline int inc(int x,int y){ return (x+=y)>=mods?x-mods:x; } inline int dec(int x,int y){ return (x-=y)<0?x+mods:x; } inline int mul(int x,int y){ return 1ll*x*y%mods; } const int N=1e6+3; int smallest[2*N]; std::vector<int>pri; inline void Euler(){ smallest[1]=1; for(int i=2;i<=2*n;++i){ if(!smallest[i]){ pri.push_back(i); smallest[i]=i; } for(auto it:pri){ if(it*i>2*n) break; smallest[i*it]=it; if(i%it==0){ break; } } } } int cnt[2*N]; inline int qpow(int a,int b){ int ans=1; while(b){ if(b&1) ans=mul(ans,a); a=mul(a,a); b>>=1; } return ans; } int main(){ filein(a);fileot(a); read(n,mods); for(int i=1;i<=n;++i) cnt[i]-=1;//分子 for(int i=n+2;i<=2*n;++i) cnt[i]+=1;//分母 Euler(); for(int i=2*n;i>1;--i){ if(smallest[i]<i){ cnt[smallest[i] ]+=cnt[i]; cnt[i/smallest[i] ]+=cnt[i]; } } int ans=1; for(int i=2;i<=2*n;++i){ if(cnt[i] and smallest[i]==i) ans=mul(ans,qpow(i,cnt[i]) ); } printf("%d/n",ans); return 0; } 斯特林数（Stirling）
第二类斯特林数
记作 /(/begin{Bmatrix} n // k /end{Bmatrix}/) ，或者 /(s_2(n,k)/) 。表示 /(n/) 个两两不同的元素划分为 /(k/) 个互不区分的非空子集的方案数。
递推公式
初始状态 /(/begin{Bmatrix} n // 0 /end{Bmatrix}=[n=0]/) 。
证明：
考虑新加入一个元素。
如果这个元素放在已经存在的非空子集中，有 /(k/begin{Bmatrix} n-1 // k /end{Bmatrix}/) 种方案。
如果这个元素单独新开一个非空子集，有 /(/begin{Bmatrix} n-1 // k-1 /end{Bmatrix}/) 种方案。
然后加法原理合并可得。Q.E.D.
通项公式
证明：
设 /(g(i)/) 为将 /(n/) 个不同元素放入 /(i/) 个不同集合中（可以为空集）的方案数，/(f(i)/) 为将 /(n/) 个不同元素放入 /(i/) 个不同集合（不可为空集）的方案数。
那么
第二个式子成立，是因为集合互不相同，先枚举启用几个集合，再枚举选择具体用哪些集合。
通过二项式反演：
于是有
同行计算
发现是一个卷积的形式，/(f(x)=/sum_{i=0}^n/frac{(-1)^i}{i!}x^i/) 卷积 /(g(x)=/sum_{i=0}^n/frac{i^n}{i!}/) 即可 /(O(n/log n)/) 的时间内求出。
第一类斯特林数
记作 /(/begin{bmatrix} n // k /end{bmatrix}/) 或 /(s(n,k)/) 。表示 /(n/) 个不同的元素划分为 /(k/) 个不同的非空轮换的方案数。
什么叫做轮换？相等于一个首尾相接的环。也就是说，对于轮换 /([A,B,C]/) ，其满足 /([A,B,C]=[C,A,B]=[B,C,A]/)。
递推公式
初始状态 /(/begin{bmatrix} n // k /end{bmatrix}=[n=0]/)
证明：
还是考虑新加入一个元素。
如果单独开一个轮换，那么有方案数 /(/begin{bmatrix} n-1 // k-1 /end{bmatrix}/) 种。
如果加入一个已经存在的轮换，那么可以考虑加在已经存在的数后面，有 /((n-1)/begin{bmatrix} n-1 // k /end{bmatrix}/) 种方案数。然后加法原理合并即可。
Q.E.D.
然后似乎没有什么好用的通项公式？
上升幂和下降幂
上升幂 /(x^{/overline{n}}=/prod_{i=0}^{n-1}(x+i)/)
下降幂 /(x^{/underline{n}}=/frac{x!}{(x-n)!}=/prod_{i=0}^{n-1}(x-i)/)
上升幂转普通幂
证明：
考虑归纳证明：
/(n=0/) 时，等式两边皆为 /(1/),等式成立
/(n=1/) 时，等式左边等于 /(x/) ，等式右边等于 /(x/) ，等式成立。
Q.E.D.
衍生公式：
由上式加上斯特林反演得
下降幂转普通幂
证明：
同样考虑归纳证明：
/(n=0/) 时，等式两边皆为 /(1/) ，等式成立
/(n=1/) 时，等式两边皆为 /(x/) ，等式成立
Q.E.D.
衍生公式：
同样是由上式加上斯特林反演得
其实这个式子也可以不用斯特林反演，我们直接按照组合意义来证明。
证明：
这是因为 /(m^n/) 的组合意义是将 /(n/) 个有区别的数放入 /(m/) 个有区别的集合，允许空集的方案数。上式子相当于先枚举盒子的个数，再枚举盒子的区别，再从 /(m/) 个集合中选出 /(i/) 个，然后再数放入。
当我们用这个来证明反演：
这里枚举范围可以取 /(n/) 的原因是我们认为 /(i/) 大于 /(n/) 时，式子值为 /(0/)。
而大于 /(x/) 的部分，/(/binom{x}{i}/) 取 /(0/) ，因此得到此式。
Q.E.D.
一个小小结论，按上面两个式子拆解易证：
反转公式
反转公式（1）证明：
Q.E.D.
反转公式（2）证明：
Q.E.D.
斯特林反演
上式中一二类斯特林数可以互换位置。
证明：
已知： /(g(n)=/sum_{i=0}^n(-1)^{n-i}/begin{bmatrix} n // i /end{bmatrix}f(i)/)
Q.E.D.
