§D2.2数え上げの原理と全単射による数え上げ

証明. 自然数$k$について$Q(k)$を「全単射$g\colon [m] \to [k-1]$が存在するならば$m=k-1$」と定める。$Q(1)$は$n=0$の場合であり、帰納段階$Q(k)\Rightarrow Q(k+1)$は「$n=k-1$の場合を仮定して$n=k$の場合を示す」ことと一致するから、$Q$に関する数学的帰納法（§A3.10 定理 1.1）により、以下では$n := k-1$として主張を示す。

$n = 0$のとき、$[n] = \varnothing$である。$m \ge 1$とすると$g(1) \in \varnothing$となって矛盾するから$m = 0$である。

$n \ge 1$とし、$n - 1$について主張が成り立つと仮定する。全単射$g\colon [m] \to [n]$をとる。$[n]$は空でないから$g$の全射性より$m \ge 1$である。$[n]$の二元$n$と$g(m)$を入れ替え、他の元を動かさない写像を$\tau\colon [n] \to [n]$とすると、$\tau$は自分自身を逆写像とする全単射である。合成$h := \tau \circ g$は定義 1.1により全単射であり、$h(m) = \tau(g(m)) = n$を満たす。$h$は単射だから$i \le m - 1$のとき$h(i) \ne n$、すなわち$h(i) \in [n-1]$である。ゆえに$h$の$[m-1]$への制限は$[m-1] \to [n-1]$の写像を与え、単射性は$h$から受け継がれ、全射性は$h$の全射性と$h(m) = n$から従う。帰納法の仮定により$m - 1 = n - 1$、すなわち$m = n$である。▨

証明.$|A|=n$とすると全単射$g\colon[n]\to A$がとれる。定義 1.1により、合成$f\circ g\colon[n]\to B$は全単射である。したがって、要素の個数の定義により$|B|=n=|A|$である。▨

証明. 互いに素な有限集合$A,B$をとり、$|A|=m$、$|B|=k$とする。全単射$f\colon[m]\to A$と$g\colon[k]\to B$をとり、写像$h\colon[m+k]\to A\cup B$を$h(i) = \begin{cases} f(i) & (1\le i\le m),\\ g(i-m) & (m< i\le m+k) \end{cases}$で定める。$h(i)=h(j)$ならば、$A\cap B=\varnothing$より$h(i),h(j)$は同じ集合に属し、$f$または$g$の単射性から$i=j$を得るので、$h$は単射である。また$A\cup B$の任意の元は$A$または$B$に属し、$f,g$の全射性から$h$の像に入るので、$h$は全射である。したがって$h$は全単射であり、命題 1.5により$|A\cup B|=m+k$である。

$n=|I|$とし、全単射$\alpha\colon[n]\to I$をとる。$n=0$ならば$I=\varnothing$であり、合併は空集合、和は$0$である。$n\ge1$の場合について、$B_j=A_{\alpha(j)}$とおき、$n$に関する数学的帰納法（§A3.10 定理 1.1）を適用する。$n=1$ならば$\left|\bigcup_{j=1}^{1}B_j\right|=|B_1|$である。$n\ge2$とし、$n-1$個の族に対して等式が成り立つと仮定して、$C=\bigcup_{j=1}^{n-1}B_j$とおく。族が互いに素であることから$C\cap B_n=\varnothing$である。二つの集合に対する上の等式と帰納法の仮定により$\left|\bigcup_{j=1}^{n}B_j\right| = |C| + |B_n| = \sum_{j=1}^{n-1}|B_j| + |B_n| = \sum_{j=1}^{n}|B_j|.$$\alpha$は全単射であるから、$j\in[n]$による族$(B_j)$は$i\in I$による族$(A_i)$の添字を付け替えたものである。したがって主張の等式を得る。▨

証明.$X = \bigcup_{y\in Y} f^{-1}(\{y\})$であり、$y\ne y'$のとき$f^{-1}(\{y\})\cap f^{-1}(\{y'\}) = \varnothing$である。さらに$f$は全射であるから、各$y\in Y$の逆像は空でない。したがって、加法原理（定理 2.1）より$|X| = \sum_{y\in Y} |f^{-1}(\{y\})| = \sum_{y\in Y} d = d\,|Y|.$▨

証明. 各$a\in A$に対し$\{a\}\times B := \{(a,b): b\in B\}$とおくと、$b\mapsto (a,b)$は$B\to\{a\}\times B$の全単射だから、命題 1.5により$|\{a\}\times B|=|B|$である。さらに$A\times B = \bigsqcup_{a\in A}(\{a\}\times B)$は互いに素な有限集合族の合併であるから、加法原理（定理 2.1）より$|A\times B| = \sum_{a\in A} |\{a\}\times B| = \sum_{a\in A} |B| = |A|\cdot|B|.$選択列については、$1\le i\le k$に対して$i$段階までの選択列の集合を$S_i := \{(a_1,\dots,a_i) : a_1\in C_1,\ a_2\in C_2(a_1),\ \dots,\ a_i\in C_i(a_1,\dots,a_{i-1})\}$とおき、$|S_i| = n_1 n_2\cdots n_i$を$i$に関する帰納法（§A3.10 定理 1.1）で示す。$i=1$のとき$S_1=C_1$だから$|S_1|=n_1$。$i\ge2$とし$|S_{i-1}|=n_1\cdots n_{i-1}$を仮定する。各$p\in S_{i-1}$に対して$T_p:=\{(a_1,\dots,a_i)\in S_i:(a_1,\dots,a_{i-1})=p\}$とおく。各$i$組は前半の$(i-1)$組をただ一つもつから、$(T_p)_{p\in S_{i-1}}$は互いに素であり、$S_i=\bigsqcup_{p\in S_{i-1}}T_p$である。$p=(p_1,\dots,p_{i-1})$と書くと、末成分写像

を考える。選択列の定義により、$b\in C_i(p)$を$(p_1,\dots,p_{i-1},b)$へ送る写像$C_i(p)\to T_p$が定まり、この写像は末成分写像の逆写像である。したがって、末成分写像は全単射であり、命題 1.5により$|T_p|=n_i$である。加法原理（定理 2.1）より$|S_i| = \sum_{p\in S_{i-1}} |T_p| = \sum_{p\in S_{i-1}} n_i = n_i\,|S_{i-1}| = n_1\cdots n_{i-1}n_i.$したがって$|S_k| = n_1\cdots n_k$である。▨

証明.$k=0$のとき、空の順序付き組はただ一つであり、$[n]$の$0$元部分集合も空集合ただ一つである。$0!=1$と空積を$1$とする規約により

である。したがって、二つの公式はいずれも$k=0$の場合に成り立つ。

以下では$1\le k\le n$とする。順列は、第$1$成分を$n$通り、第$2$成分を残り$n-1$通り、…、第$k$成分を$n-k+1$通りから選ぶ選択列である。各段階の選択肢数はそれまでの選択に依らず定まるので、乗法原理（定理 2.3）より$P(n,k) = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}.$

組合せの公式を示す。$\mathcal{C}$を$[n]$の$k$元部分集合全体、$\mathcal{P}$を$[n]$の相異なる$k$個の元を並べた順序付き$k$組全体とする。写像$\varphi\colon\mathcal{P}\to\mathcal{C}$を、順序付き$k$組に現れる要素の集合を対応させる写像とする。各$S\in\mathcal{C}$に対し、原像$\varphi^{-1}(\{S\})$は$S$の要素の並べ替え全体であり、$|\varphi^{-1}(\{S\})|=P(k,k)=k!$である。特に各原像は空でないので$\varphi$は全射である。この原像による分割は、同じ集合を与えるという同値関係による類別にほかならない（§D2.5 定義 2.1）。命題 2.2を$X=\mathcal{P}$、$Y=\mathcal{C}$、$d=k!$に適用すると$|\mathcal{P}|=k!\,|\mathcal{C}|$を得る。$|\mathcal{P}|=P(n,k)$ゆえ$\binom{n}{k}=|\mathcal{C}|=\dfrac{P(n,k)}{k!}=\dfrac{n!}{k!\,(n-k)!}$。▨

証明. 選び方は、種類$i$を選ぶ回数$x_i$の組によってただ一つに定まるから、選び方の全体は$\mathcal{M} := \Bigl\{(x_1,\dots,x_n) \in \mathbb{Z}_{\ge 0}^{\,n} : \sum_{j=1}^{n} x_j = k\Bigr\}$と全単射に対応する。$\mathcal{S}$を$[n+k-1]$の$(n-1)$元部分集合の全体とし、$\mathcal{M}$と$\mathcal{S}$のあいだに全単射を作る。

$(x_1,\dots,x_n) \in \mathcal{M}$に対し、$s_j := x_1 + \cdots + x_j + j$（$1 \le j \le n-1$）とおき$\varphi(x_1,\dots,x_n) := \{s_1, s_2, \dots, s_{n-1}\}$と定める。各$x_j \ge 0$だから$s_{j+1} - s_j = x_{j+1} + 1 \ge 1$となり$s_1 < s_2 < \cdots < s_{n-1}$、とくに$\varphi(x)$の要素の個数は$n-1$である。また$s_1 = x_1 + 1 \ge 1$であり、$s_{n-1} = k - x_n + (n-1) \le n+k-1$である。ゆえに$\varphi(x) \in \mathcal{S}$であり、$\varphi\colon \mathcal{M} \to \mathcal{S}$が定まる。

逆に$S = \{s_1 < s_2 < \cdots < s_{n-1}\} \in \mathcal{S}$に対し、$s_0 := 0$、$s_n := n+k$とおいて$\psi(S) := (x_1,\dots,x_n), \qquad x_j := s_j - s_{j-1} - 1 \quad (1 \le j \le n)$と定める。$1 \le j \le n-1$では$s_{j-1} < s_j$より$x_j \ge 0$であり、$j = n$では$s_{n-1} \le n+k-1 < n+k = s_n$より$x_n \ge 0$である。さらに$\sum_{j=1}^{n} x_j = \sum_{j=1}^{n}(s_j - s_{j-1}) - n = (s_n - s_0) - n = (n+k) - n = k$だから$\psi(S) \in \mathcal{M}$である。

二つの対応が互いに逆であることを確かめる。$x \in \mathcal{M}$に対し$\varphi(x)$の第$j$番目に小さい要素は$s_j = x_1 + \cdots + x_j + j$だから、$\psi(\varphi(x))$の第$j$成分は$s_j - s_{j-1} - 1 = x_j$に等しい（$j = n$では$s_n - s_{n-1} - 1 = (n+k) - (k - x_n + n - 1) - 1 = x_n$）。逆に$S \in \mathcal{S}$に対し$\psi(S) = (x_1,\dots,x_n)$とおくと$x_1 + \cdots + x_j + j = s_j$が$j$についての和で従うから、$\varphi(\psi(S)) = S$である。ゆえに$\varphi$は全単射である。

全単射原理（命題 1.5）と組合せの個数（命題 3.1）により$|\mathcal{M}| = |\mathcal{S}| = \binom{n+k-1}{n-1} = \binom{n+k-1}{k}$を得る。最後の等号は$(n+k-1) - (n-1) = k$による。▨

証明.$(x+y)^n = \prod_{i=1}^{n}(x+y)$の各因子から$x$または$y$を選ぶ操作を、$x$を選ぶ因子の添字全体$S\subseteq[n]$によって径数付ける。分配法則と$x,y$の可換性により

$|S|=k$を満たす部分集合$S\subseteq[n]$は命題 3.1により$\binom{n}{k}$個であるから主張を得る。$n=0$のときも、$[0]=\varnothing$の唯一の部分集合に対応する空積を$1$とすることで同じ等式が成り立つ。▨

証明.$[n]$の$k$元部分集合全体$\mathcal{C}$を、要素$n$を含むものの集合$\mathcal{C}_1$と含まないものの集合$\mathcal{C}_0$に分ける。これは互いに素な分割である。$\mathcal{C}_1$の集合は$\{n\}$に$[n-1]$から$k-1$個を選んで加えたものと一対一対応するので$|\mathcal{C}_1|=\binom{n-1}{k-1}$。$\mathcal{C}_0$の集合は$[n-1]$から$k$個を選んだものだから$|\mathcal{C}_0|=\binom{n-1}{k}$。加法原理（定理 2.1）より$\binom{n}{k}=|\mathcal{C}_1|+|\mathcal{C}_0|=\binom{n-1}{k-1}+\binom{n-1}{k}$。▨