KV熵的Blog

排列数

通常被记作$A(n,m)$或$A^n_m$，意为：从$m$个元素中选择$n$个元素的排列的方案数

公式：$A^n_m = \frac{m!}{(m-n)!}$

证明：忘了

组合数

通常被记作$C(n,m)$或$C^n_m$或$\dbinom{n}{m}$，意为：从$m$个元素中选择$n$个元素的排列的方案数

公式：$\dbinom{n}{m} = \frac{A(n,m)}{m!} = \frac{m!}{n!(m-n)!}$

二项式定理

$(x+y)^n = \sum_{i=0}^n\dbinom{n}{i}x^iy^{n-i}$

证明：还是忘了

卢卡斯定理

当$p$为质数时

$\dbinom{n}{m} \bmod{p} = \dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\dbinom{n\bmod{p}}{m\bmod{p}}\bmod{p}$

证明：不需要忘了，本来就不知道