二項定理

整数論の有名な公式：

連続する $n$ 個の整数の積は $n!$ の倍数である。

包除原理：

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B\cup C|\\ =|A|+|B|+|C|\\ -|A\cap B|-|B\cap C|-|C\cap A|\\ +|A\cap B\cap C|$

より一般に，

$|A_1\cup A_2\cup\cdots\cup A_n|$

$=\displaystyle\sum_{k=1}^n(-1)^{k-1}$（$k$個の「かつ」の総和）

$=\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cap A_j|$

$+\sum_{i < j < k}|A_i\cap A_j\cap A_k|$

$-\cdots +(-1)^{n-1}|A_1\cap\cdots\cap A_n|$

ヴァンデルモンドの畳み込み：

以下の恒等式が成立する：

$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$

ただし，$p < k$ のとき ${}_p\mathrm{C}_k=0$ と約束する。