“性质”与“公式”——The First Part

一、排列数

• 计算公式：

\[P_n^m=\frac{n!}{(n-m)!} \]

• 规定性质：\(P_n^0=1\)，\(P_n^n=n!\)
• 递推性质1：\(P_n^m=nP_{n-1}^{m-1}\)
• 递推性质2：\(P_n^m=mP_{n-1}^{m-1}+P_{n-1}^m\)
• 递推性质3：\(P_n^m=(n-m+1)P_n^{m-1}\)

二、组合数

• 计算公式：

\[C_n^m=\frac{P_n^m}{p_m^m}=\frac{n!}{m!(n-m)!} \]

• 互补性质：\(C_n^m=C_n^{n-m}\)
• 规定性质：\(C_n^0=C_n^n=1\)
• 加法性质（杨辉三角性质）：\(C_n^m+C_n^{m-1}=C_{n+1}^m\)
• 吸收恒等式：\(mC_n^m=nC_{n-1}^{m-1}\)
• 二项式定理：

\[(a+b)^n=\sum_{m=0}^nC_n^ma^{n-m}b^m \]

• 上指标求和：\(\sum_{k=r}^nC_k^r=C_{n+1}^{r+1}\)
• 下指标求和（范德蒙德恒等式）：

\[\sum_{k=0}^rC_m^kC_n^{r-k}=C_{m+n}^r \]

三、同余

• 自反性：\(a\equiv a\pmod m\)
• 对称性：if \(a\equiv b\pmod m\) , then \(b\equiv a\pmod m\)
• 传递性：if \(a\equiv b\pmod m\) and \(b\equiv c\pmod m\) , then \(a\equiv c\pmod m\)
• 同余式相加：if \(a\equiv b\pmod m\) and \(c\equiv d\pmod m\) , then \(a+c\equiv b+d\pmod m\)
• 同余式相乘：if \(a\equiv b\pmod m\) and \(c\equiv d\pmod m\) , then \(ac\equiv bd\pmod m\)
• 同余式数乘：if \(a\equiv b\pmod m\) , then \(na\equiv nb\pmod m\)
• 同余式幂运算：if \(a\equiv b\pmod m\) , then \(a^n\equiv b^n\pmod m\)
• 模的整除性质：if \(a\equiv b\pmod m\) and \(d|m\),\(d>0\) , then \(a\equiv b\pmod d\)
• 最大公约数性质：if \(ac\equiv bc\pmod m\) and \(\gcd(c,m)=d\) , then \(a\equiv b\pmod{\frac{m}{d}}\)