计数杂项 ​

组合恒等式 ​

推导组合恒等式的常见办法 ​

• 组合意义：一般更方便
• 二项式定理：处理行的和
• 利用已有恒等式推导

常见式子 ​

基本定义 ​

• $A(n,i)$即$n$的下降幂
• $C(n,j)=\frac{A(n,j)}{A(j,j)}=\frac{n!}{j!(n - j)!}$

对称性 ​

$C(n,i)=C(n,n - i)$

加法分解 ​

• $C(n,i)=C(n - 1,i - 1)+C(n - 1,i)$
• $A(n,i)=A(n - 1,i)+i\times A(n - 1,i - 1)$
• $C(n,i)=\sum_{j = i - 1}^{n - 1} C(j,i - 1)$

乘法转换 ​

• $A(n,i)=A(n,j)\times A(n - j,i - j)$
• $C(n,i)\times A(i,j)=C(n - j,i - j)\times A(n,j)$
• $C(n,i)\times C(i,j)=C(n,j)\times C(n - j,i - j)$

利用二项式定理巧妙赋值 ​

• C(n,\text{奇}) = C(n,\text{偶})
• $\sum_{i} C(n,i)=2^n$

二项式反演 ​

原理 ​

若$f[n]=\sum_{i} C(i,n)\times g[i]$，则$g[n]=\sum_{i} (-1)^{(i - n)}\times C(i,n)\times f[i]$

判断正确性的依据 ​

“至少”是否满足和“恰好”的关系，满足就可以用

实现相关 ​

法一 ​

已经得到$g$的情况下，可以利用卷积实现二项式反演。直接暴力卷积是平方的，利用$ntt$是线性对数的。

法二（一般模数） ​

需要将答案式写出，进行进一步的推式子和优化。

$k$维二项式反演 ​

类比理解 ​

高维前缀和与其逆变换

具体处理 ​

对每一维分别做二项式反演即可

复杂度 ​

$k\times$单次二项式反演复杂度

常见应用 ​

• （容斥）去掉一个条件
• 处理恰好$k$个的条件

斯特林数 ​

以下记第二类斯特林数为$S$

$S(n,k)$的组合意义 ​

将$n$个不同的球恰分成$k$组的方案数。其中，两个方案不同当且仅当存在两个球在其中一个方案中在同一个组中，在另一个方案中不在同一个组中。

辨 ​

• 将$n$个不同的球放进$k$个不同盘子（允许放空）的方案数是$k^n$
• 将$n$个不同的球放进$k$个相同盘子（不允许放空）的方案数是$S(n,k)$

递推公式 ​

$S(n,k)= S(n - 1,k - 1)+S(n - 1,k)\times k$

proof：考虑$S(n,k)$的所有方案中第$n$个球的情况，是否是自己一个组，证明双射即可。

通项公式 ​

$S(n,k)=\sum_{i} (-1)^{(k - i)} \times \frac{i^n}{k! \times (k - i)!}$

proof：发现无标号可放空是好算的，直接容斥即可。

普通幂转下降幂 ​

$k^n=\sum_{i} A(k,i)\times S(n,i)$

prufer序列 ​

构造 ​

每次选出编号最小的度数为$1$的节点，将其删去，并将其父节点加入序列。

性质 ​

• 序列和有标号有根树一一对应
• 点$i$的出现次数等于其度数减$1$
• 构造时最终剩下的两个节点有一个是$n$

重要推论 ​

图中有$k$个连通块，其大小分别为$a[1\sim k]$，添加$k - 1$条边将其连成一个连通图的方案数为$n^{k - 2} \times (a[1]\times a[2]\times\cdots\times a[k])$

理性理解：

• 不妨先统计有根树的数量，最后除以$n$即可。
• 将$prufer$序列改一下变成每次删的对应的具体连的父亲节点。
• 然后再钦定一下删除当前块连给父亲的是哪个点，钦定最后一个删除块钦定的点就是根。
• 那么发现这应该可以一一对应，就证完了。

生成函数简陋知识 ​

• $\frac{1}{(1 - x)^k}=\sum_{i} C(i + k - 1,k - 1)\times x^i$
• $\frac{x^n}{1 - x}=\sum_{i = 0}^{n - 1} x^i$
• $e^x=\sum_{i} \frac{x^i}{i!}$
• $OGF$和$EGF$的卷积