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