组合数学

组合数学进阶

插板法

问题1

求把 \(n\) 个相同的球放进 \(m\) 个不同的盒子的方案数（盒子不可以为空）。
考虑在间隔里插板子，答案 \(\binom{n-1}{m-1}\)。
问题2

求把 \(n\) 个相同的球放进 \(m\) 个不同的盒子的方案数（盒子可以为空）。
考虑借 \(m\) 个球，使问题转换为问题1，答案 \(\binom{n+m-1}{m-1}\)。
Catalan数

问题1

求在网格图中，每次可以向上或向右走，从 \((0,0)\) 走到 \((n,m)\) 的方案数。
一共需要走 \(n+m\) 步，其中 \(n\) 步向右，答案 \(\binom{n+m}{n}\)。
问题2

求在网格图中，每次可以向上或向右走，且不能碰到直线 \(y=x+1\)，从 \((0,0)\) 走到 \((n,m)\) 的方案数。
先计算不考虑限制的方案数。再考虑不合法路径数，把不合法路径与直线的交点后面的线关于 \(y=x+1\) 做翻折，则路径会变成一条到 \((n,m)\) 关于 \(y=x+1\) 的对称点，即 \((m-1,n+1)\)，最终答案 \(\binom{n+m}{n}-\binom{n+m}{m-1}\)。
斯特林数

第一类斯特林数：把 \(n\) 个不同元素构成 \(m\) 个非空圆排列的方案数，记为 \(\begin{bmatrix} n \\ m \end{bmatrix}\)。
递推公式：

\[\begin{bmatrix} n \\ m \end{bmatrix}=\begin{bmatrix} n-1 \\ m-1 \end{bmatrix}+(n-1)\begin{bmatrix} n-1 \\ m \end{bmatrix}\]
第二类斯特林数：把 \(n\) 个不同元素构成 \(m\) 个非空子集的方案数，记为 \(\begin{Bmatrix} n \\ m \end{Bmatrix}\)。
递推公式：

\[\begin{Bmatrix} n \\ m \end{Bmatrix}=\begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix}+m\begin{Bmatrix} n-1 \\ m \end{Bmatrix}\]
重要公式：

\[m^n=\sum_{i=0}^{m}\begin{Bmatrix} n \\ i \end{Bmatrix}m^{\underline{i}}=\sum_{i=0}^{m}\begin{Bmatrix} n \\ i \end{Bmatrix}\binom{m}{i}i!\]
证明：两边都是在计算 \(n\) 个有标号球放到 \(m\) 个有标号盒子里的方案数。
反演

二项式反演

当 \(g_i\) 表示至多 \(i\) 个，\(f_i\) 表示恰好 \(i\) 时：

\[g_k=\sum_{i=0}^{k}\binom{k}{i}f_i \iff f_k=\sum_{i=0}^{k}\binom{k}{i}(-1)^{k-i}g_i\]
当 \(g_i\) 表示至少 \(i\) 个，\(f_i\) 表示恰好 \(i\) 时：

\[g_k=\sum_{i=k}^{n}\binom{i}{k}f_i \iff f_k=\sum_{i=k}^{n}\binom{i}{k}(-1)^{i-k}g_i\]
子集反演

前置知识：高维前缀和

前缀和代码
[code]for(int i=0;i

收藏一下   不知道什么时候能用到

这个有用。

前排留名，哈哈哈

鼓励转贴优秀软件安全工具和文档！