链接

这里是其它的早期OI资料。

为了防止hexo出错，所有的.md都是在改成.txt之后上传，可以下载之后自己改回去并渲染。

1. $\binom{n}{m} = \binom{n}{n-m}$
2. $\binom{n}{m} + \binom{n}{m+1} = \binom{n+1}{m+1}$
3. $\sum_{m=r}^n \binom{m}{r} = \binom{n+1}{r+1}$
4. $\sum_{m=0}^n \binom{n}{m} = 2^n$
5. $\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}$
   1. $m \binom{n}{m} = n \binom{n-1}{m-1}$
6. $\sum_{r=0}^k \binom{n}{r} \binom{m}{k-r} = \binom{n+m}{k}$
   1. $\sum_{i=0}^n \binom{n}{i}^2 = \sum_{i=0}^n \binom{n}{i} \binom{n}{n-i} = \binom{2n}{n}$

封闭形式：

1. $\frac{1}{(1-x)^{n+1}} = \sum_{k=0}^\infty \binom{n+k}{n} x^k$

   1. $\frac{1}{(1-x)^{n+1}} = (1-x)^{-(n+1)} = \sum_{k=0}^\infty \binom{-n-1}{k} (-x)^k = \sum_{k=0}^\infty (-1)^k \binom{k+n}{k} (-x)^k = \sum_{k=0}^\infty \binom{n+k}{n} x^k$

2. $\frac{1}{\sqrt{1-4x}} = \sum_{k=0}^\infty \binom{2k}{k} x^k$

   1. $$(1-x)^{-\frac{1}{2}} = \sum_{k=0}^\infty \binom{-\frac{1}{2}}{k} (-x)^k\\ = \sum_{k=0}^\infty \frac{(-1)(-3) \cdots (-(2k-1))}{2^k k!} (-x)^k\\ = \sum_{k=0}^\infty (-1)^k \frac{\frac{(2k)!}{2^k k!}}{2^k k!} (-x)^k\\ = \sum_{k=0}^\infty \binom{2k}{k} 4^{-k} x^k\\ \frac{1}{\sqrt{1-4x}} = (1-4x)^{-\frac{1}{2}} = \sum_{k=0}^\infty \binom{2k}{k} 4^{-k} (4x)^k\\ = \sum_{k=0}^\infty \binom{2k}{k} x^k$$

3. $\frac{1 - \sqrt{1-4x}}{2x} = \sum_{k\ge 0} \frac{1}{k+1} \binom{2k}{k} x^k$

   1. $$(1-x)^{\frac{1}{2}} = \sum_{k=0}^\infty \binom{\frac{1}{2}}{k} (-x)^k\\ = \sum_{k=0}^\infty \frac{1(-1)(-3)(-5)\cdots (-(2k-3))}{2^k k!}(-x)^k\\ = - \sum_{k=0}^\infty \frac{\frac{(2k-2)!}{2^{(k-1)}(k-1)!}}{2^kk!}x^k\\ = - 2 \sum_{k=0}^\infty \frac{1}{k} \cdot\binom{2k-2}{k-1} \cdot 4^{-k} x^k\\ 1 - \sqrt{1-4x} = 2 \sum_{k=1}^\infty \frac{1}{k} \cdot\binom{2k-2}{k-1} \cdot 4^{-k} (4x)^k\\ = 2 \sum_{k=1}^\infty \frac{1}{k} \cdot\binom{2k-2}{k-1} \cdot x^k$$

给出$n,k$，求$\sum _{i=0}^n i^k$。

方法1：递推

带标号的连通图计数 bzoj3456 城市规划

这是一个非常经典的问题。我们考虑容斥，那么就是图的数量减去不连通图的数量。计算不连通图的数量时，我们考虑枚举$1$号点所在的连通块大小（这样一定不重不漏），那么得到：

拆组合数：

P1 旅行商问题

统计哈密顿路径的数量。

对于长度为 $n$ 的路径，如果所有的点都在路径中出现过，那么这条路径就是合法的。

参考

https://blog.csdn.net/qq_33229466/article/details/80359560

写于2018年冬，当时水平比较菜，留下的一些思考可能对初学Burnside的后辈有启发，所以现在发出来。

看不懂证明，所以只好愉快地感性理解结论。证明等我长大了再回来补吧。（啊，那就大概就是永远都不会补了吧。）

有向图欧拉回路数量计数。

为什么不是 $\prod_u (\deg_u!)$ 呢？因为任意的边排列顺序不一定能构造出对应的方案，比如

例题：CF gym100958 I

按照从小到大确定每种长度的前缀是否是一个 border，同时对于当前已经确定的 border $l_0,l_1,\cdots l_k$，统计长度为 $l_k$ 且以 $\{l_0,l_1,\cdots l_k\}$ 为 border 的字符串数。

新加入的一个 border $l_{k+1}$ 的时候，分如下情况讨论：

这篇总结基本上就是这篇文章的翻译。

这是一种算法，可以在$O(n)$空间、$O(n\log n)$的时间内求出将一个字符串划分成若干个为回文的子串，最少需要的划分次数。

这个算法魔改一下，还可以求一个字符串划分成若干个回文子串的方案数。（就是CF932G）