包除原理とは何か？

包除原理は、複数の集合の和集合の要素数を求める公式である。各集合の要素数の和から、2つずつの共通部分を引き、3つずつの共通部分を足し…と交互に加減する。

鳩の巣原理とは何か？

鳩の巣原理（ディリクレの箱入れ原理）は、n+1個の物をn個の箱に入れると、少なくとも1つの箱には2個以上入るという原理である。存在証明に広く用いられる。

数え上げの原理（全単射原理、二重計数）、包除原理、漸化式の解法、鳩の巣原理、グラフ理論の基礎（グラフの定義、木、オイラー路）を学ぶ。大学1〜2年レベルの内容である。

数え上げの技法とグラフ理論（大学1-2年レベル）

初級では、大学レベルの組合せ論の基礎技法を学ぶ。包除原理や鳩の巣原理などの強力な数え上げ手法、漸化式を用いた数列の解析、そしてグラフ理論の入門を扱う。

包除原理

$$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_i |A_i| - \sum_{i \lt j} |A_i \cap A_j| + \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$$

例：$|A \cup B| = |A| + |B| - |A \cap B|$。重複を補正しながら和集合の要素数を求める。

鳩の巣原理

$n+1$個の物を$n$個の箱に入れると、少なくとも1つの箱には2個以上入る。

例：13人いれば、同じ誕生月の人が必ず2人以上いる（13人を12か月に割り当て）。

握手補題

$$\sum_{v \in V} \deg(v) = 2|E|$$

グラフの全頂点の次数の和は辺の数の2倍である。各辺は両端の2頂点の次数に1ずつ寄与するため成り立つ。