组合数学
组合数学进阶插板法
问题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}\]
重要公式：
\
证明：两边都是在计算 \(n\) 个有标号球放到 \(m\) 个有标号盒子里的方案数。
反演
二项式反演
当 \(g_i\) 表示至多 \(i\) 个，\(f_i\) 表示恰好 \(i\) 时：
\
当 \(g_i\) 表示至少 \(i\) 个，\(f_i\) 表示恰好 \(i\) 时：
\
子集反演
前置知识：高维前缀和
前缀和代码
for(int i=0;i 收藏一下 不知道什么时候能用到 这个有用。 前排留名，哈哈哈 鼓励转贴优秀软件安全工具和文档！ 不错，里面软件多更新就更好了 很好很强大我过来先占个楼 待编辑 用心讨论，共获提升！ 谢谢分享，辛苦了 不错，里面软件多更新就更好了 东西不错很实用谢谢分享 感谢，下载保存了 前排留名，哈哈哈
页:
[1]