2024.7.5

### 2024.7.5 【向之所欣，俯仰之间，已为陈迹。】 ### Thursday 五月三十 --- # 组合 # 数学！ ~~可能公式比较多~~ ## 二项式！ $$ \begin{pmatrix}n\\m\end{pmatrix}=\begin{pmatrix}n-1\\m-1 \end{pmatrix}+\begin{pmatrix} n-1 \\m\end{pmatrix} $$ $$ \begin{pmatrix} n\\m \end{pmatrix} =\frac {m!}{n!(m-n)!} $$ 非常常见的递推式和计算式 递推式即**加法恒等式** 计算式即**阶乘展开式** 所以 $$ \begin{pmatrix} n \\m \end{pmatrix} = \begin{pmatrix} n \\n-m \end{pmatrix} $$ 称之为**对称** $$ \sum_{m=0}^{n}m\begin{pmatrix} n \\m \end{pmatrix} = \sum_{m=0}^{n}\begin{pmatrix} n \\m \end{pmatrix}\begin{pmatrix} m \\1 \end{pmatrix} =\sum_{m=0}^{n}\begin{pmatrix} n \\1 \end{pmatrix}\begin{pmatrix} n-1 \\m-1 \end{pmatrix}=n\sum_{m=0}^{n}\begin{pmatrix} n-1 \\m-1 \end{pmatrix}=n\sum_{m=0}^{n-1}\begin{pmatrix} n-1 \\m \end{pmatrix}=n2^{n-1} $$ 上面用到的这个 $$ \begin{pmatrix} n \\r \end{pmatrix}\begin{pmatrix} r \\m \end{pmatrix}=\begin{pmatrix} n \\m \end{pmatrix}\begin{pmatrix} n-m \\r-m \end{pmatrix} $$ 的公式，叫做**吸收恒等式** 其意义为在n个中选择r，在r个中选择m个， 等价于在n个中选择m个，再在剩余的n-m个中选r-m个 $$ \sum_{0\le k \le n}\begin{pmatrix} k \\ m \end{pmatrix} = \begin{pmatrix} n+1 \\m+1 \end{pmatrix} $$ 这个叫做**上指标求和** >在形如 >$$ >\begin{pmatrix} > >n \\m > >\end{pmatrix} >$$ >公式中，我们将n称作**上指标**，相应的，m为**下指标** 证明吗，考虑现实意义， 我们在m+1个数中，枚举第一个数选择第k+1个的时候，剩余的选择方案， 即 $$ \begin{pmatrix} k \\m \end{pmatrix} $$ 则，在总共m+1个数中，选取k+1个，即是枚举k的情况下，求解和值 至于**下指标求和**吗 $$ \sum_{k=0}^{n}\begin{pmatrix} n \\k \end{pmatrix} = 2^{n} $$ 还是挺简单的吧/le 至于**平行求和式** 即 $$ \sum_{k \le n}\begin{pmatrix} r+k\\r \end{pmatrix}=\begin{pmatrix} r+n+1\\n \end{pmatrix} $$ 证明： $$ \sum _{k=0}^{n}\begin{pmatrix} m+k\\n \end{pmatrix}=\sum_{k=0}^{n}\begin{pmatrix} m+k\\m \end{pmatrix}+0=\sum_{k=0}^{n+m}\begin{pmatrix} m+k\\m \end{pmatrix}+\sum_{k=0}^{m-1}\begin{pmatrix} m+k\\m \end{pmatrix}=\sum_{k=0}^{n+m}\begin{pmatrix} k\\m \end{pmatrix} = \begin{pmatrix} m+n+1\\m+1 \end{pmatrix}\begin{pmatrix} m+n+1\\n \end{pmatrix} $$ 还是依据上指标求和解出来的 以及**上指标反转** $$ \begin{pmatrix} r\\k \end{pmatrix} = (-1)^{k}\begin{pmatrix} k-r-1\\k \end{pmatrix} $$ 证明： $$ 首先爆拆\\ \begin{pmatrix} r\\k \end{pmatrix} = \frac{r^{\underline{k} }}{k!} \\ \begin{pmatrix} k-r-1\\k \end{pmatrix} = \frac{(k-r-1)^{\underline{k}}}{k!} \\ r^{\underline{k}} = (-1)^k(k-r-1)^{\underline{k}} \\ r*(r-1)*...*(r-k+1) = (-1)^k*(k-r-1)*(k-r-2)*...*(-r) \\注意到\\ -r和r为相反数\\ r-k+1和k-r-1为相反数\\ 则k为奇数时前后刚好差一个负号， 则由(-1)^k补上 $$