卡特兰数
常见公式： 不是很懂。
\[H_n=C_{2n}^n-C_{2n}^{n-1} \]应用：折线计数。
第二类斯特林数
在小球与盒子那道模板题中见到的，表示表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空子集的方案数。
递推式：
\[\operatorname{S2}_{i,j}=j \times \operatorname{S2}_{i-1,j}+\operatorname{S2}_{i-1,j-1} \]通项公式：\(n,m\) 较大时使用，需要二项式反演来证，参 OI Wiki。
\[\operatorname{S2}_{n,m}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} \]应用：组合数学，若要求非空子集互相区分，直接乘上 \(!m\) 即可。
二项式定理
内容：
\[(x+y)^n=\sum_{k=0}^n\ C{_n^k} x^k y^{n-k} = \sum_{k=0}^n\ C{_n^k} x^{n-k} y^k \]应用：
二项式定理对于化简式子极为有用，降低复杂度。
形式 \(\sum_{k=0}^n\ C{_n^k} x^k y^{n-k}\) 要想到化为左式。
对于形式 \(\sum_{k=0}^n C_n^k x^k\)，要想到化为 \(\sum_{k=0}^n C_n^k x^k 1^{n-k}=(x+1)^n\)。
二项式反演
记 \(f_n\) 表示恰好使用 \(n\) 个不同元素形成特定结构的方案数，\(g_n\) 表示从 \(n\) 个不同元素中选出 \(i \geq 0\) 个元素形成特定结构的总方案数。
若已知 \(f_n\) 求 \(g_n\)，那么显然有：
\[g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i \]若已知 \(g_n\) 求 \(f_n\)，那么：
\[f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i \]上述已知 \(g_n\) 求 \(f_n\) 的过程，就称为二项式反演。
参考资料
- https://oi-wiki.org/math/combinatorics/stirling/
2.https://oi-wiki.org/math/combinatorics/combination/