错位排列
二项式定理
\[{(a + b)^k} = \sum_{i=0}^k {k \choose i} * a ^ i * b^{k - i}
\]
似乎比较显然。接下来是关于二项式定理的几个推论。
推论一
\[{(a + b)^k} = \sum_{i=0}^k {k \choose i} * a ^ i * b^{k - i} = \sum_{i = 0} ^ k {k \choose k - i} * a^ i * b^{k - i}
\]
由 \(n \choose m\) = \(n \choose n - m\) 可得。
推论二
\[(a + 1)^k = \sum_{i = 0} ^ k {k \choose i} * a ^i
\]
取 \(b = 1\) 代入即可。
推论三
\[2^k = \sum_{i = 0}^k{k \choose k - i}
\]
\(2^k\) 即代表在 \(k\) 个数中，每个数可选，可不选，以此得到的总方案数。
推论四
\[0 = \sum_{i = 0} ^ k {k \choose i} * -1 ^i
\]
取 \(a = 1,b = -1\) 代入二项式定理。
组合恒等式
算是一些组合数的二级结论，不过有些结论的证明感觉很奇妙，这里记录下来。
恒等式一
\[{n \choose m} = {n - 1 \choose m - 1} * \frac{n}{m}
\]
按照组合数计算式展开即可。
恒等式二
\[\sum_{i = 0}^k i * {k \choose i} = k * 2 ^ {k - 1}
\]
对 \((1 + x)^k\) 求导，得 \(k * (1 + x)^{k - 1}\)。
对 \(\sum_{I = 0} ^ k {k \choose i}x^i\) 求导，得 \(\sum_{i = 0} ^ k i * x^{i - 1}\)
由二项式定理推论二得：\(k * (1 + x)^{k - 1} = \sum_{i = 0} ^ k i * x^{i - 1}\)
将 \(x = 1\) 代入即可。
恒等式三
\[\sum_{i = 0} ^ k (-1) ^ i * i * {k \choose i} = 0,k >= 2
\]
整理
\[\sum_{i = 0} ^ k (-1) ^ i * \frac{k}{i} * i * {k - 1 \choose i - 1} = 0
\]
然后
\[k * \sum_{i = 0} ^ k (-1) ^ i * {k - 1 \choose i - 1} = 0
\]
由二项式定理推论四即可知二者恒等。
恒等式四
\[\sum_{i = 0} ^ k i ^ 2 * {k \choose i} = k * (k + 1) * 2 ^ {k - 2}
\]
由 \((x + 1)^k = \sum_{i = 1} ^ k x^i * {k \choose i}\)，两边连续求导两次，最后代入 \(x = 1\) 即可得。
恒等式五
\[\sum_{i = 0}^k (-1)^i * i ^ 2 * {k \choose i} = 0,k >= 3
\]
在恒等式四证明的基础上，代入 \(x = -1\)。
恒等式六
\[\sum_{i = 0}^k {k \choose i} * (i + 1)^{-1} = (2^{k + 1} - 1) * (k + 1)^{-1}
\]
证明如下：
首先有 $$(x + 1) ^ k = \sum_{i = 0} ^ k {k \choose i} * x^i$$
同时积分，有
\[(x + 1) ^ {k + 1} * (k + 1)^{-1} = \sum_{i = 0} ^ k {k \choose i} * x^{i + 1} * (i + 1)^{-1}
\]
代入 \(x = 1\)，积分范围 为 \(0～1\)，即可化为理想形式。
恒等式七
\[{n + m \choose r} = \sum_{i = 0}^r {n \choose i} * {m \choose r - i}
\]
直接看数学意义：一共有 \(n + m\) 个求，在大小为 \(n\) 的这一堆取 \(i\) 个有 \(n \choose i\) 种方法，在大小为 \(m\) 的一堆里取 \(r - i\) 个有 \(m \choose r - i\) 种方法，由乘法原理就能得到结果了。
恒等式八
\[{n + m \choose r} = \sum_{i = 0}^r {n \choose i} * {m \choose i}
\]
显然。
恒等式九
\[{2n \choose n} = \sum_{i = 0}^r {n \choose i} * {n \choose i}
\]
显然。
恒等式十
\[{n \choose i} * {i \choose j} = {n \choose j} * {n - j \choose i - j} = {n \choose j} * {n - j \choose n - i}
\]
展开，整理式子可以得到。
恒等式十一
\[\sum_{i = 0}^n {i \choose m} = {n + 1 \choose m + 1}
\]
从 \(n+1\) 个不同的球中选出 \(m+1\) 个不同的球，方案数为 \(n+1 \choose m+1\)。枚举选出的最后一个球编号为 \(i+1\)，方案数为从前 \(i\) 个球中选出剩余 \(m\) 个球的方案，为 \(i \choose m\)。
恒等式十二
\[{n + m + 1 \choose n} = \sum_{i = 0}^n {m + i \choose i}
\]
将 \(m+n+1\) 和 \(n\) 代入推论三即可得到