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补上
$$