组合数学与容斥

数学知识也快学到尾声了…也许要花好久才能消化呢。
（持续更新中）

组合数学

基础知识

• 排列数

  从 $n$ 个不同元素中依次取出 $m$ 个元素排成一列，产生不同的排列数为

  $A_n^m=\cfrac{n!}{(n-m)!}=n\cdot (n-1)\cdots (n-m+1)$

• 组合数

  从 $n$ 个不同元素取出 $m$ 个组成一个集合，产生不同的集合数量为

  $C_n^m=\cfrac{n!}{m!(n-m)!}=\cfrac{n\cdot(n-1)\cdots(n-m+1)}{m\cdot(m-1)\cdots 1}$

  • 性质
    1. $C_n^m=C_n^{n-m} $
    2. $ C_n^m=C_{n-1}^{m-1}+C_{n-1}^m $
    3. $ C_n^0+C_n^1+\cdots+C_n^n=2^n $

• Lucas 定理

  若 $p$ 为质数，对于任何整数 $1\leq m\leq n$ 有

  $C_n^m\equiv C_{n\bmod p}^{m\bmod p}\ \ \cdot C_{n/p}^{m/p} \pmod p$

• 二项式定理

  $(a+b)^n=\displaystyle\sum_{k=0}^n{C_n^k a^k b^{n-k}}$