组合数学 1
xcrr
·
·
个人记录
备忘用。
排列组合
\begin{aligned}A_{n}^{m}=n\left( n-1\right) \cdot \left( n-2\right) \cdot \ldots \cdot \left( n-m+1\right)
=\dfrac{n!}{\left( n-m\right) !}
=C_{n}^{m}\cdot m!\end{aligned}
={n}^{\underline{m}}
C_{n}^{}=\dfrac{A_{n}^{m}}{m!}=\dfrac{n!}{\left( n-m\right) !\cdot m!}=\dfrac{ n^{\underline{m}}}{ m^{\underline{m}}}
杨辉三角形
C_{n}^{k}=C_{n-1}^{k-1}+C_{n-1}^{k}
C_{n}^{k}=0 \begin{pmatrix}k<0\| k>n\end{pmatrix}
简单的几个式子：
C_{n}^{k}=C_{n}^{n-k}
\sum ^{n}_{i=0}C_{n}^{i}=2^{n}
C_{n}^{0}+C_{n}^{2}+\ldots +C_{n}^{\small\lfloor \dfrac{n}{2}\rfloor \cdot 2}=2^{n-1}
\sum \left( C_{n}^{i}\cdot \sum C_i^{j}\right) =3^{n}
\sum ^{n}_{m=k}C_{m-1}^{k-1}=C_{n}^{k}
\sum ^{k}_{m=0}C_{p}^{m}\cdot C_{q}^{k-m}=C_{p+q}^{k}
k\cdot C_{m}^{k}=m\cdot C_{m-1}^{k-1}
\sum ^{n}_{k=0}k\cdot C_{m}^{k}=\sum ^{n-1}_{k=0}m\cdot C_{m-1}^{k}
\sum ^{n}_{k=0}k\cdot C_{n}^{k}=n \cdot 2^{n-1}
\sum ^{n}_{k=0}k^{2}\cdot C_{n}^{k}=n\cdot \left( n+1\right) \cdot 2^{n-2}
组合数求和
对角线求和
C_{n}^{m}+C_{n+1}^{m+1}+\ldots +C_{n+k}^{m+k}=C_{n+k+1}^{m+k}-C^{m-1}_{n}
直线求和
C_{n}^{m}+C_{n+1}^{m}+\ldots +C_{n+k}^{m}=C_{n+k+1}^{m+1}-C_n^{m+1}
二项式定理
\left( a+b\right) ^{n}=\sum ^{n}_{k=0}C_{n}^{k}\cdot a^{k}b^{n-k}
#### $\mathtt{Lucas}$ 定理
若 $p$ 是质数，则对于任意整数 $1\leq m\leq n$ 满足：
$$
C_{n}^{m}\equiv C_{n\% p}^{m\% p}\cdot C_{n/p}^{m/p}\;\left(mod\; p\right)
$$