§D2.3包除原理の応用と鳩の巣原理の一般形

証明. 三つの集合$A \setminus B$、$A \cap B$、$B \setminus A$は互いに素であり、その合併は$A \cup B$です。また$A$は互いに素な$A \setminus B$と$A \cap B$の合併、$B$は互いに素な$B \setminus A$と$A \cap B$の合併です。和の法則（§D2.2 定理 2.1）を三つの分解へ適用すると

が得られます。後の二つの等式から$|A \setminus B| = |A| - |A \cap B|$と$|B \setminus A| = |B| - |A \cap B|$を求め、最初の等式へ代入すると

となります。▨

証明.$n$についての単純帰納法（§A3.10 定理 1.1）で示します。

$n = 1$のとき、$[1]$の空でない部分集合は$\{1\}$だけであり、$(-1)^{1+1} = 1$なので、右辺は$|A_1|$です。左辺も$|A_1|$なので、等式が成り立ちます。

$n$個の有限集合について等式が成り立つと仮定し、有限集合$A_1, \dots, A_{n+1}$をとります。$U = \bigcup_{i=1}^{n} A_i$とおくと補題 1.1により

です。分配律により$U \cap A_{n+1} = \bigcup_{i=1}^{n} (A_i \cap A_{n+1})$なので、$n$個の有限集合$B_i = A_i \cap A_{n+1}$（$i = 1, \dots, n$）へ帰納法の仮定を適用することができます。$\varnothing \ne S \subseteq [n]$について$\bigcap_{i \in S} B_i = \bigcap_{i \in S \cup \{n+1\}} A_i$であることに注意すると、

が得られます。ここで$S \subseteq [n]$に対し$T = S \cup \{n+1\}$とおくと、$n+1 \notin S$より$|T| = |S| + 1$であり、$(-1)^{|S|+1} = (-1)^{|T|} = -(-1)^{|T|+1}$です。したがって

となります。対応$S \mapsto S \cup \{n+1\}$は、$[n]$の空でない部分集合の全体から、$n+1$を含み要素の個数が$2$以上である$[n+1]$の部分集合の全体への全単射なので、右辺の和は過不足なく取られています。また$|A_{n+1}|$は$T = \{n+1\}$に対応する項です。以上の三つを合わせると、$n+1$を含む$[n+1]$の部分集合すべてと、$n+1$を含まない空でない部分集合すべて、すなわち$[n+1]$の空でない部分集合すべてにわたる和が得られ、

となります。▨

証明.$\bigcup_{i=1}^{n} A_i \subseteq X$なので、和の法則（§D2.2 定理 2.1）により

です。定理 1.2を代入すると

となり、$|X|$を$S = \varnothing$の項として和へ入れれば主張の形になります。▨

証明.$X$を$[n]$から$[k]$への写像の全体とすると、積の法則（§D2.2 定理 2.3）により$|X| = k^{n}$です。$i \in [k]$について$A_i = \{\, \sigma \in X : i \notin \sigma([n]) \,\}$、すなわち値$i$をとらない写像の全体とおきます。写像$\sigma$が全射でないことと、ある$i$について$\sigma \in A_i$であることは同値なので、全射の全体は$X \setminus \bigcup_{i=1}^{k} A_i$です。

$S \subseteq [k]$について、$\bigcap_{i \in S} A_i$は$S$のどの要素も値にとらない写像の全体、すなわち$[n]$から$[k] \setminus S$への写像の全体です。$|[k] \setminus S| = k - |S|$なので、積の法則により$\bigl| \bigcap_{i \in S} A_i \bigr| = (k - |S|)^{n}$です。この値は$|S|$だけで決まり、$|S| = j$である$S \subseteq [k]$は$\binom{k}{j}$個あります（§D2.2 命題 3.1）。したがって系 1.3により

が得られます。▨

証明.$X = \{1, 2, \dots, n\}$とし、$i \in [r]$について$A_i = \{\, m \in X : p_i \mid m \,\}$とおきます。整数$m$が$n$と互いに素でないことは、$m$と$n$の共通の素因数が存在すること、すなわち$n$の素因数$p_i$のいずれかで$m$が割り切れることと同値です。よって$n$と互いに素な$X$の要素の全体は$X \setminus \bigcup_{i=1}^{r} A_i$であり、$\varphi(n)$はその要素の個数です。

$\varnothing \ne S \subseteq [r]$について$d_S = \prod_{i \in S} p_i$とおきます。認めて用いる事実により、$m \in \bigcap_{i \in S} A_i$であることと$d_S \mid m$であることは同値です。$p_1, \dots, p_r$は$n$の相異なる素因数なので$d_S$は$n$の約数であり、$1$以上$n$以下で$d_S$の倍数であるものは$n / d_S$個です。したがって$\bigl| \bigcap_{i \in S} A_i \bigr| = n / d_S$です。系 1.3を適用すると、第一の等式

が得られます（$S = \varnothing$の項は$|X| = n$です）。

第二の等式を示します。積$n \prod_{i=1}^{r} (1 - 1/p_i)$を分配律で展開すると、各因子から$1$または$-1/p_i$のどちらを選ぶかによって項が定まります。$-1/p_i$を選ぶ添字の全体を$S$とすると、その項は$n \cdot (-1)^{|S|} / \prod_{i \in S} p_i$です。選び方$S$は$[r]$の部分集合の全体を過不足なく動くので、展開した和は第一の等式の右辺に一致します。▨

証明. すべての$i$について$a_i < \bar{a}$であると仮定します。$n \ge 1$なので、両辺を$i = 1$から$n$まで加えると

となり、同じ実数がそれ自身より真に小さいことになって矛盾します。したがって$a_i \ge \bar{a}$を満たす$i$が存在します。後半は、この結果を実数$-a_1, \dots, -a_n$へ適用し、その平均が$-\bar{a}$であることを用いれば得られます。▨

証明.$i$番目の箱に入っている対象の個数を$a_i$とします。どの対象もちょうど一つの箱へ入るので、対象の全体は各箱の中身へ互いに素に分割されており、和の法則（§D2.2 定理 2.1）により$\sum_{i=1}^{n} a_i = N$です。よって平均は$\bar{a} = N/n$です。定理 4.1により$a_i \ge N/n$を満たす$i$が存在します。$a_i$は整数なので、$N/n$以上の整数のうち最小のもの、すなわち$\lceil N/n \rceil$以上です。後半も同様に、$a_j \le N/n$を満たす$j$に対して$a_j \le \lfloor N/n \rfloor$が従います。▨

証明.系 4.2を$N = n+1$に適用すると、$\lceil (n+1)/n \rceil$個以上の対象が入っている箱が存在します。$n \ge 1$より$1 < (n+1)/n \le 2$なので$\lceil (n+1)/n \rceil = 2$です。▨