場合の数

$|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$ と約束する。

$c_n=\dfrac{1}{n+1}{}_{2n}\mathrm{C}_{n}={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}$

で定義されるカタラン数は場合の数の問題で頻繁に登場する。

$n$ 個の要素からなる集合 $\{1,2,\cdots,n\}$ から要素数が $k$ の部分集合たちを以下の条件を満たすようにできるだけたくさん選びたい。

条件：選んだ部分集合のどの二つを選んでも共通元が存在する。

$n\geq 2k$ のとき， 選べる部分集合の限界 $N$ は，$N={}_{n-1}\mathrm{C}_{k-1}$ 個である。

$a,b$ を正の整数とする。各項が相異なる長さ $ab+1$ の数列があるとき，以下の二つのうち少なくとも一つは必ず存在する。

1：長さ $a+1$ の部分列で，単調増加なもの

2：長さ $b+1$ の部分列で，単調減少なもの

二項定理とは，$n$ 乗の式を展開するための以下のような公式のことです。

$$(a+b)^n=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_ka^{n-k}b^{k}$$

$(x_1+x_2+\cdots +x_k)^n$ を展開したときの $x_1^{e_1}x_2^{e_2}\cdots x_k^{e_k}$ の係数は

$e_1+e_2+\cdots +e_k=n$ かつ各 $e_i$ が非負なら $\dfrac{n!}{e_1!e_2!\cdots e_k!}$

（そうでないなら $0$ ）

異なる $n$ 個のものを円形に並べる方法の総数は $(n-1)!$ 通り