组合数公式相关-神的馈赠

· · 个人记录

更好的阅读体验请移步到

定义：从 n 个物品中选出 m 个的方案数，记作 C_{n}^{m} ，也记作 \tbinom{n}{m} 。

组合：对于顺序没有要求

排列：对于顺序有要求

C_{n}^{m}=\frac{A_{n}^{m}}{A_{m}^{m}}=\frac{n!}{(n-m)!m!}

递推公式

C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}

意义：从 n 个不同的数中取 m 个，第 m 个数不取有 C_{n-1}^{m} ，取有 C_{n-1}^{m-1} 种。

### 性质 $1.~~~C_{n}^{m} = C_{n}^{n-m}

证：取 m 个和选 m 个不取是等价的

\space 2.~~~C_{n}^{m} \cdot C_{m}^{r}~=~C_{n}^{r} \cdot C_{n-r}^{m-r}

证：相当于是调换选择的顺序，最后的结果都是选出 m 个再中的 r 个元素，并记录该 m 个元素（可以感性理解一下）。等式左边是先选 m 个再选 r 个，而等式右边则是选出 r 个再在剩下的元素中选出 m-r 个以达到 “ 记录 m 个元素 ” 的目的。

\space 3.~~~m*C_{n}^{m}=n*C_{n-1}^{m-1}

证：m*C_{n}^{m}=C_{n}^{m}\cdot C_{m}^{1}=C_{n}^{1} \cdot C_{n-1}^{m-1}=n*C_{n-1}^{m-1}

\space 4.~~~\sum_{i=1}^{n} i*C_{n}^{i} = n*2^{n-1}

证：\sum_{i=1}^{n} i*C_{n}^{i}=\sum_{i=1}^{n} n*C_{n-1}^{i-1} = n*\sum_{i=0}^{n-1} C_{n-1}^{i} = n*2^{n-1}

\space 5.~~~\sum_{i=1}^{n} i^2*C_{n}^{i} = n*(n+1)*2^{n-2}

证：\sum_{i=1}^{n} i^2*C_{n}^{i}\\= n*\sum_{i=0}^{n-1} (i+1)C_{n-1}^{i} \\= n*2^{n-1}+\sum_{i=0}^{n-1} i*C_{n-1}^{i}\\=n*2*2^{n-2}+n*(n-1)*2^{n-2}\\=n*(n+1)*2^{n-2}

\space 6.~~~\sum_{i=0}^{n} C_{n}^{i}=2^n$ $二项式定理

证：C_{n}^{i}代表一个~n~位二进制数有~i~个~0~的情况下的数量，那么这个和就是~n~位二进制数的数量了。

​ \sum_{i=0}^{n} C_{n}^{i} x^i= (x+1)^n 二项式定理推广

证：杨辉三角

\space 7.~~~C_{n+m+1}^{m}=\sum_{i=0}^{m} C_{n+i}^{i}

证：

利用C_{n}^{0}=1=C_{n+1}^{0}

\sum_{i=0}^{m} C_{n+i}^{i}\\ =C_{n}^{0}+C_{n+1}^{1}+C_{n+2}^{2}+\cdots+C_{n+m}^{m}\\=C_{n}^{1}+C_{n+1}^{1}+C_{n+2}^{2}+\cdots+C_{n+m}^{m}

利用 C_{n}^{m}+C_{n+1}^{m}=C_{n+1}^{m+1}从小到大一次合并最终得出 C_{n+m+1}^{m} 。

\space 8.~~~\sum_{i=0}^{n} (-1)^iC_{n}^{i}=0

证：

拆开成

\begin{matrix} C_{n}^{0}-C_{n}^{1}+C_{n}^{2}-\cdots-C_{n}^{n}=0~~~~(n\%2=1)\\ C_{n}^{0}-C_{n}^{1}+C_{n}^{2}-\cdots+C_{n}^{n}=0~~~~(n\%2=0) \end{matrix} \right. $(n\%2=0)$ 根据 $C_{n}^{m}=C_{n}^{m-1}+C_{n-1}^{m-1},C_{n}^{0}=C_{n-1}^{0},C_{n}^{n}=C_{n-1}^{n-1}$ 对于原式进行裂项为 $C_{n-1}^{0}-(C_{n-1}^{0}+C_{n-1}^{1})+(C_{n-1}^{1}+C_{n-1}^{2})-(C_{n-1}^{2}+C_{n-1}^{3})+\cdots +C_{n-1}^{n-1}=0 \space 9.~~~\sum_{i=0}^{n}[2\mid i]C_{n}^{i}=\sum_{j=0}^{n}[2\nmid j]C_{n}^{i}=2^{n-1}

根据 \sum_{i=0}^{n}[2\mid i]C_{n}^{i}-\sum_{i=0}^{n}[2\nmid i]C_{n}^{i}=\sum_{i=0}^{n} (-1)^iC_{n}^{i}=0

移项可知 \sum_{i=0}^{n}[2\mid i]C_{n}^{i}=\sum_{j=0}^{n}[2\nmid j]C_{n}^{i}

则 C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+\cdots=C_{n}^{1}+C_{n}^{3}+C_{n}^{5}\cdots=\dfrac{\sum_{i=0}^{n} C_{n}^{i}}{2}=\dfrac{2^n}{2}=2^{n-1}

\space 10.~~~C_{n+m}^{r}=\sum_{i=0}^{r} C_{n}^{i} \cdot C_{m}^{r-i}

证：根据定义，有 n+m 个物品，在前 n 个物品中取出 i 个，在后 m 个物品中取出 r-i 个相乘求和即可。

变形：C_{n+m}^{r}=\sum_{i=0}^{r} C_{n}^{i} \cdot C_{m}^{r-i}=\sum_{i=0}^{r} C_{n}^{i} \cdot C_{m}^{m-r+i}

当 r=m 时 C_{n+m}^{m}=\sum_{i=0}^{m} C_{n}^{i}\cdot C_{m}^{i}

变形2 ： C_{n+m}^{m}=\sum_{i=0}^{m} C_{n}^{i}\cdot C_{m}^{i}

当 m=n 时 C_{2n}^{n} = \sum_{i=0}^{n} (C_{n}^{i})^2