集合論の言葉による「数え上げ (counting)」

この記事では、集合論の言葉を使って「個数」とは何か、「個数を数える (数え上げ)」とは何かを定義していく。そして、その定義を利用して高校数学で扱う「順列」や「組合せ」の個数を数える。

自然数

小学校の算数で最初に数を習うときは「個数を数えるため」に数を導入するだろう。たとえばおはじきの個数として数を表現したりする。後々に、その時に習った数のことを自然数と呼び始めるが、つまり自然数は個数を数えるために使える数であるということである。

そこで、この記事でも自然数を用いるが、集合論の言葉では何通りもの方法で自然数を表現できる。ここでは前回確認した $\omega$ に属するモノを自然数として扱うことにする (準備編)。したがって、この記事の中では\[\begin{array}{rclcl} 0 &=& \emptyset \\ 1&=& 0\cup\{0\} &=& \{0\}\\ 2 &=& 1\cup\{1\} &=& \{0,1\}\\ 3 &=& 2\cup\{2\} &=& \{0,1,2\}\\ & \vdots &&&\\ \text{$n$ の次の数} &=& n\cup\{n\}&& \end{array}\]となる。つまり集合 $n$ は「$n$ 以前の自然数がすべて属し、それ以外のモノが属さない集合」となる。

集合に属するモノの数

ここで例として「1と3と5だけが属し、それ以外のモノが属さない集合」である\[\{1,3,5\}\]に、いくつのモノが属するかを考えてみよう。素朴な知識に忠実であるならば、この集合に属するモノの個数は 3 となるべきである。つまり、これから「個数を数える」ことを定義するにあたって、$\{1,3,5\}$ に属するモノの個数が 3 となるような定義になっていなければならない (そうでなければ素朴に「個数」と呼んでいる概念とは違う何かを定義していることになる)。

さて、個数の定義をしようというのだが、その際に最も重要になるのは、自然数と呼ばれる集合に属するモノの個数である。よくよく見てみると、$1=\{0\}$ なので 1 に属するモノの個数を素朴に数えると 1 つである。$2=\{0,1\}$ なので 2 に属するモノの個数は素朴には 2 である。このことから $\omega$ に属する自然数 $n$ に属するモノの個数は $n$ であるべきである。ということは、$x$ に属するモノの個数が、自然数 $n$ に属するモノの個数に一致するときは、$x$ に属するモノの個数が $n$ 個だと言われるべきと考えることができる。

ただこれをそのまま定義にはできない。そもそも「個数」を定義しようとしているのに、その中で「個数」という言葉は使えないだろう。だから、上で「属するモノの個数の一致」と表現していたことを別の何かで表現しなければならない。そのために全単射を持ち出す。全単射は写像の一種であるが、言い換えれば一対一対応のことであり、「$x$ から $y$ への全単射」とは「$x$ に属するモノと $y$ に属するモノとが過不足なくちょうど1対1で対応しあう関係」のことである。たとえば、上の $x=\{1,3,5\}$ と $3=\{0,1,2\}$ の間では\begin{eqnarray}1 &\mapsto& 0 \\ 3 &\mapsto& 1 \\ 5&\mapsto& 2\end{eqnarray}のような全単射を作ることができる。一方で $x=\{1,3,5\}$ と $2=\{0,1\}$ の間では全単射を作れない。どうやっても $x$ 側でモノが余るか、$2$ 側のモノを2回以上使わなくてはいけなくなる。

要素数

前節の「余る」という現象は個数が一致していないと解釈することができるだろう。そう考えると、全単射を作れること (一対一を余りなく作れること) が「属するモノの個数の一致」の代わりになりそうである。そこで、集合に属するモノの個数のことを「要素数」と呼ぶことにして次のように定義する。

定義$x$ を集合とし、$n$ を $\omega$ に属する自然数とする。$x$ から $n$ への全単射が存在するとき、$n$ を $x$ の要素数という。$x$ の要素数は高々一つしかないので、$x$ の要素数を $\#x$ と表す。

定義$x$ を集合とする。$x$ の要素数である自然数が存在するなら、$x$ は有限である。

たとえば $\{1,3,5\}$ から $3=\{0,1,2\}$ への全単射が存在するので、\[\#\{1,3,5\} = 3\]となり $\{1,3,5\}$ は有限である。要素数の定義の2つ目の文にある「$x$ の要素数は一つしかない」というのは、$x$ の要素数と呼ぶべき自然数が1つしかないということである。例えば $\{1,3,5\}$ との間に全単射がある自然数は3しかない。このことを証明するに、まず異なる自然数同士の間に全単射が存在しないことを示す。

定理$n$, $m$ を $\omega$ に属する自然数とする。$n$ から $m$ への全単射が存在するとき、$n=m$ である。

(証明) $n$ についての数学的帰納法で示す。$\emptyset$ から $m$ への全単射があるとすると $m$ に属するモノがないことになるので、$\emptyset=m$ である。

次に固定された自然数 $n$ について「$n$ から自然数 $m$ への全単射が存在するとき $n=m$」と仮定し、全単射 $f':n\cup \{n\}\to m'$ が存在するとする。$n\cup \{n\}\neq\emptyset$ だから先に述べたのと同様に $m'\neq\emptyset$ であり、したがってある $m$ が存在して $m'=m\cup\{m\}$。このとき、新たな写像 $f:n\to m$ を\begin{eqnarray}f(x)=\left\{\begin{array}{ll}f'(x) & \text{if $f'(x)\in m$} \\ f'(n) & \text{otherwise}\end{array}\right.\end{eqnarray}と定めると、これも全単射である。したがって数学的帰納法の仮定より $n=m$ であり、よって\[n\cup\{n\}=m\cup\{m\}=m'.\]

この定理を元に、異なる2つの自然数が1つの集合の要素数とはならないことも次のように証明できる。

命題$x$ を集合とし、$n$, $m$ を $\omega$ に属する自然数とする。$n$ も $m$ も $x$ の要素数であるとき、$n=m$ である。

(証明) $n$ も $m$ も $x$ の要素数であるとすると、2つの全単射 $f:x\to n$, $g:x\to m$ が存在する。このとき、$f$ の逆写像 $f^{-1}:n\to x$ も全単射であり、全単射同士の合成も全単射なので、$(g\circ f^{-1}):n\to m$ は全単射である。よって、上で示した自然数の非対等性より $n=m$。

前節の考察から、全単射の存在を元にここで定義した要素数は、素朴に考える「集合に属するモノの個数」に一致し、高校数学で扱う要素数にも一致する。よって、今後はモノの個数を数えたいときは、「そのモノたちがすべて属し、それ以外のモノが属さない集合」の要素数を答えとすればよい。

鳩の巣原理

ここで、数え上げについての基礎的な命題を証明しておく。

命題$n$, $m$ を自然数とする。$m\gt n$ であるとき $m$ から $n$ への単射は存在しない。

(証明) $n$ についての数学的帰納法を用いる。まず $n=0$ に対しては空集合への写像が存在しないので明らか。

次に固定された $n$ について成立するとする。$m\gt n+1$ であれば $m-1\gt n$ であるので数学的帰納法の仮定より $m-1$ から $n$ への単射は存在しない。ここで $m$ から $n+1$ への単射 $f$ が存在すると仮定すると写像 $g:m-1\to n;$ \[g(i)=\left\{\begin{array}{ll} f(i) & \text{if $f(i)\in n$} \\ f(m-1) & \text{otherwise}\end{array}\right.\]が単射となって矛盾する。よって $m$ から $n+1$ への単射は存在しない。

命題$x$, $y$ を有限集合とする。$\#x \leq \#y$ であるとき、$x$ から $y$ への単射が存在し、$\#x\gt \#y$ であるときそのような単射は存在しない。

(証明) まず $\#x \leq \#y$ であるときの単射の存在を示す。要素数の定義より全単射 $f:x\to \#x$, $g: y\to\#y$ が存在する。全単射にはその逆写像となる全単射が存在するので、全単射 $g^{-1}:\#y \to y$ も存在する。また、$\#x\leq\#y$ より $\#x\subset \#y$ であるから自然な単射 $i:\#x\to\#y$ も存在する。単射同士の合成は単射であるので $g^{-1}\circ i\circ f$ は $x$ から $y$ への単射である。

次に $\#x\gt \#y$ であるときの単射の非存在の対偶を示す。単射 $\varphi: x\to y$ が存在するとき $g\circ \varphi\circ f^{-1}: \#x\to\#y$ は単射である。したがって自然数の鳩の巣原理より $\#x\leq \#y$。

自然数の演算の確認

準備編の記事では、自然数の加法と乗法を定義している。そのときは触れなかったが、実はこのときに要素数の考え方を積極的に使っていた。現に振り返ってみると「……から自然数 $z$ への全単射が存在する」のような表現がある。いまは要素数という言葉を定義しているので、それを準備編での定義に適応すると、以下のことが成立する。\begin{eqnarray}n+m &=& \#(n\times\{\omega\}\cup\{\omega\}\times m) \\ n\cdot m&=& \#(n\times m)\end{eqnarray}結局のところ、自然数の加法は直和の要素数を、乗法は直積の要素数を数えていたのである。

これまでの知見から次のことが言えるが、ここで述べることはこの記事で数え上げを扱うにあたって重要なことである。

定理$x$, $y$ を有限集合とする。$x$ から $y$ への全単射が存在するとき\[\#x = \#y\]

(証明) 要素数の定義より全単射 $f:y\to \#y$ が存在する。定理の前提より全単射 $g:x\to y$ も存在する。全単射同士の合成は全単射であるから $(f\circ g):x\to\#y$ も全単射である。よって要素数の定義より $x$ の要素数は $\#y$ である。

定理$x$, $y$ を有限集合とし、$\ast\not\in x\cup y$ とする。このとき\begin{eqnarray}\#((x\times\{\ast\})\cup(\{\ast\}\times y))=(\#x)+(\#y).\end{eqnarray}

(証明) 自然数の加法の定義より\[(\#x)+(\#y) = \#(((\#x)\times\{\omega\})\cup(\{\omega\}\times(\#y)))\]である。したがって、2つの集合\[(x\times\{\ast\})\cup(\{\ast\}\times y)\\ ((\#x)\times\{\omega\})\cup(\{\omega\}\times(\#y))\]間に全単射があることを示せばよい (bijective proof)。

要素数の定義より全単射 $f: x\to \#x$, $g:y\to \#y$ が存在する。このとき写像 $\varphi: (x\times\{\ast\})\cup(\{\ast\}\times y)\to ((\#x)\times\{\omega\})\cup(\{\omega\}\times(\#y))$を\[\varphi(\langle \xi, \zeta\rangle) = \left\{ \begin{array}{ll}\langle f(\xi), \omega\rangle & \text{if $\zeta=\ast$} \\ \langle \omega, g(\zeta)\rangle &\text{if $\xi=\ast$}\end{array}\right.\]と定めると $\varphi$ は全単射である。

定理$x$, $y$ を有限集合とし、$x\cap y=\emptyset$ とする。このとき\begin{eqnarray}\#(x\cup y)=(\#x)+(\#y).\end{eqnarray}

(証明) 自然数の加法の定義より\[(\#x)+(\#y) = \#(((\#x)\times\{\omega\})\cup(\{\omega\}\times(\#y)))\]である。したがって、2つの集合\[x\cup y\\ ((\#x)\times\{\omega\})\cup(\{\omega\}\times(\#y))\]間に全単射があることを示せばよい (bijective proof)。

要素数の定義より全単射 $f: x\to \#x$, $g:y\to \#y$ が存在する。このとき写像 $\varphi: x\cup y \to ((\#x)\times\{\omega\})\cup(\{\omega\}\times(\#y))$を\[\varphi(\xi) = \left\{ \begin{array}{ll} \langle f(\xi),\omega\rangle & \text{if $\xi\in x$} \\ \langle \omega, g(\xi)\rangle &\text{if $\xi\in y$}\end{array}\right.\]と定めると $\varphi$ は全単射である。

定理$x$, $y$ を有限集合とする。このとき\begin{eqnarray}\#(x\times y)=(\#x)\cdot(\#y).\end{eqnarray}

(証明) 自然数の乗法の定義より\[(\#x)\cdot(\#y) = \#((\#x)\times(\#y))\]である。したがって、2つの集合\[x\times y\\ (\#x)\times(\#y)\]間に全単射があることを示せばよい (bijective proof)。

要素数の定義より全単射 $f: x\to \#x$, $g:y\to \#y$ が存在する。このとき写像 $\varphi: x\times y\to (\#x)\times(\#y)$を\[\varphi(\langle \xi, \zeta\rangle) = \langle f(\xi), g(\zeta)\rangle\]と定めると $\varphi$ は全単射である。

重なりを許す順列

ここからは要素数の定義を用いて、高校数学で扱うもろもろの数え上げ問題に取り掛かる。そのために、高校数学では曖昧な言葉で説明されていた状況を集合論の言葉で書き直すところから始める。

高校数学では次のような問題を扱うことがある。

問題A, B, C, D の4種の文字を5個並べるとき、その並べ方の総数はいくつか。ただし、同じ文字を何度使ってもよい。

指示通りに並べると、たとえば「ABCDD」や「AAAAA」などの文字列を作ることができるが、何種類の文字列を作ることができるのだろうかという問題である。ここでまず作っているモノに注目すると、文字の列である。そして、総数を数えるだけなら使う文字はどんなモノに変えてもよいはずなので、A, B, C, D のそれぞれを何かしらの互いに異なる集合であるとして、$x=\{{\rm A,B,C,D}\}$ としよう。すると、作られる文字の列は「$x$ に属するモノを並べた、長さが 5 の有限列」となる。その総数を数えたいのだが、「そのような列がすべて属し、それ以外のモノが属さない集合」は $\text{Map}(5,x)$ と表されるのだったから、その要素数\[\#\text{Map}(5,x)\]がこの問題の答えとなる。ただ、これでは味気ない (高校数学ではおそらく正解として扱われない) のでもう少し代数的にわかりやすい表現を探そう。

命題$x$ を有限集合とし、$n$ を $\omega$ に属する自然数とする。このとき\begin{eqnarray}\#\text{Map}(0,x)&=& 1\\ \#\text{Map}(n\cup\{n\}, x) &=& (\#x)\cdot(\#\text{Map}(n,x))\end{eqnarray}

(証明) まず上の式から示す。写像は二項関係として定義されるので、$f\in \text{Map}(0,x)$ であれば $f\subset 0\times x$ である。ところが $0\times m=\emptyset$ であるから $f$ が存在するなら $f=\emptyset$ しかない。この $\emptyset$ は写像の定義を満たすので、$\emptyset$ は $\text{Map}(0,x)$ に属する唯一の写像である。このとき $\text{Map}(0,x)=\{\emptyset\}=1$ だから $\#\text{Map}(0,x)=1$。

次に下の式を示す。右辺にある自然数の積について、乗法原理より\begin{eqnarray} (\#x)\cdot(\#\text{Map}(n,x))  &=& \#(x\times\text{Map}(n,x)) \end{eqnarray}である。したがって、2つの集合\[\text{Map}(n\cup\{n\}, x)\\ x\times\text{Map}(n,x)\]の間に全単射が存在することを示せばよい。写像$\varphi: \text{Map}(n\cup\{n\}, x)\to x\times\text{Map}(n,x)$を\begin{eqnarray}\varphi(f) &=& \langle f(n), g_{f} \rangle \\ g_{f}&:& n\to x \\ g_{f}(\xi)&=&f(\xi)\end{eqnarray}と定めると $\varphi$ は全単射である。したがって\[\#\text{Map}(n\cup\{n\}, x)=\#(x\times\text{Map}(n,x))\]

以上のことから $\#\text{Map}(n,x)$ は $\#x$ を $n$ 回かけた数に等しい。高校数学の表現を使えば\[\#\text{Map}(n,x)=(\#x)^n\]ということになる。いままで数の冪を定義してこなかったが、これをもとに自然数の冪を定義することができ、その場合は\[m^n=\#\text{Map}(n,m)\]となる。ただし、集合論の言葉では要素数の方ではなく、集合そのものの方に冪表現を割り当てて\[x^n=\text{Map}(n,x)\]とする場合もあるので、注意が必要である。その場合は $\#(x^y)$ は $\#x$ を $\#y$ 回かけた数に等しいとなる。

いずれにしても、$x=\{{\rm A,B,C,D}\}$ とすると当初の問題の答えは\begin{eqnarray}\#\text{Map}(5,\{{\rm A,B,C,D}\}) &=& (\#x)(\#x)(\#x)(\#x)(\#x)\\&=& 4\cdot4\cdot4\cdot4\cdot4\\ &=& 1024\end{eqnarray}となる。そして、一般には次のようになる。

解答「$m$ 種の文字を $n$ 個並べるとき、その並べ方の総数はいくつか。ただし、同じ文字を何度使ってもよい。」という問題の解答は\[\#\text{Map}(n, m)\]となり、これは $m$ を $n$ 回かけた数に等しい。

重なりを許さない順列

今度は少し問題の条件を変えて次のようにする。

問題A, B, C, D の4種の文字を3個並べるとき、その並べ方の総数はいくつか。ただし、同じ文字を二度使ってはならない。

たとえば「DBC」や「ADC」は条件に合っているので数える。一方で「ACC」のように同じ文字を2回使っているものは先ほどと違って数える対象としない。このことを踏まえて先ほどの問題と同様に考察する。

やはり $x=\{{\rm A,B,C,D}\}$ とすれば数える対象は「$x$ に属するモノを並べた、長さが 3 の有限列」であり、これは準備編で述べたように「3 から $x$ への写像」であるのだが、そのすべてを数えるわけではない。上でも述べたが「ACC」のように同じ文字を使っているものは数える対象から外さなくてはならない。『同じ文字を使っている列』とは写像の言葉にすると『単射でない (異なる番号に同じ文字を割り当てている) 写像』ということになる。よって、数えるべき対象は「$\#x$ から $x$ への単射」となり、つまり「3 から $x$ への単射がすべて属し、それ以外が属さない集合」の要素数\[\#\{f\in\text{Map}(3,x) \mid \text{$f$ は単射}\} \]が答えとなる。ここで「$k$ から $x$ への単射がすべて属し、それ以外が属さない集合」のことを $\mathfrak{M}(k,x)$ と表すことにすると答えは\[\#\mathfrak{M}(3,x)\]と表せる。もちろんこのままでは不正解と見なされるであろうから、より計算しやすい簡素な表現を探す。そのためにまず $n=\#x$ と考えて次のことを証明しておく。

命題$n$, $k$ を自然数とする。このとき\begin{eqnarray}\#\mathfrak{M}(0,n)&=& 1\\ \#\mathfrak{M}(k,n) &=& \left\{\begin{array}{ll}0 &\text{if $n\lt k$}\\n\cdot\#\mathfrak{M}(k-1,n-1) & \text{if $1\leq k \leq n$} \end{array}\right.\end{eqnarray}

(証明) まず1つ目の式を示す。命題の証明と同様に $\mathfrak{M}(0,n)=\{\emptyset\}$ であるから $\#\mathfrak{M}(0,n) = 1$。

次に2つ目の式の $n\lt k$ の場合を示す。このとき鳩の巣原理より $k$ から $n$ への単射は存在しないので $\mathfrak{M}(k,n)=\emptyset$ であり、したがって $\#\mathfrak{M}(k,n)=0$。

最後に2つ目の式の $1\leq k\leq n$ の場合を示す。$n=\#n$ であるので、乗法原理より右辺は\[n\times\mathfrak{M}(k-1,n-1)\]の要素数に等しい。したがって、2つの集合\[\mathfrak{M}(k,n) \\ n\times\mathfrak{M}(k-1,n-1)\]の間に全単射が存在することを示せばよい (bijective proof)。写像$\varphi: \mathfrak{M}(k,n)\to n\times\mathfrak{M}(k-1,n-1)$を\begin{eqnarray}\varphi(f) &=& \langle f(k-1), g_{f} \rangle \\ g_{f}&:& k-1\to n-1; \\ g_{f}(\xi)&=&\left\{\begin{array}{ll}f(\xi) & \text{if $f(\xi)\neq n-1$} \\ f(k-1) & \text{otherwise}\end{array}\right.\end{eqnarray}と定めると $\varphi$ は全単射である。

以上のことから、直感的な表現で端的に書くと $k\leq n$ に対して\[\#\mathfrak{M}(k,n)=n(n-1)\cdots(n-k+1)\]ということになる。ここで $_n{\rm P}_k$ で表される自然数を\[_n{\rm P}_k =\#\mathfrak{M}(k,n) \]と定義すれば高校で習うとおりの\[_n{\rm P}_k=n(n-1)\cdots(n-k+1)\]という式が得られる。また、とくに\[n! = \#\mathfrak{M}(n,n)\]と $n$ の階乗を定義すれば\begin{eqnarray}0! &=&1 \\ n! &=& n(n-1)\cdots1 \\ (n+1)! &=& n!\cdot (n+1) \end{eqnarray}となりやはり高校で習うとおりの式が得られる。

ではいよいよ本題の $\#\mathfrak{M}(k,x)$ を考えるが、実は $\#\mathfrak{M}(k,n)$ に等しい。

命題$n$, $k$ を自然数とし、$x$ を集合とする。$\#x=n$ であるとき\[\#\mathfrak{M}(k,x)=\#\mathfrak{M}(k,n)\]

(証明) $\mathfrak{M}(k,x)$ から $\mathfrak{M}(k,n)$ への全単射が存在することを示せばよい (bijective proof)。

$\#x=n$ より全単射 $f:x\to n$ が存在する。これを用いて $\psi: \mathfrak{M}(k,x)\to \mathfrak{M}(k,n)$ を\[\psi(g)=f\circ g\]と定義すると、$\psi$ は全単射である。

以上から、当初の問題の答えは\begin{eqnarray}\#\mathfrak{M}(3,\{{\rm A,B,C,D}\})&=& \#\mathfrak{M}(3,4) \\ &=& 4\cdot 3\cdot 2 \\ &=& 24\end{eqnarray}となる。そして、一般には次のようになる。

解答「$n$ 種の文字を $k$ 個並べるとき、その並べ方の総数はいくつか。ただし、同じ文字を2度以上使ってはならない。」という問題の解答は\[\#\mathfrak{M}(k, n)\]となり、これは $k\leq n$ なら\[n(n-1)\cdots(n-k+1)\]に等しく、$n\lt k$ なら 0 に等しい。

組合せ (二項係数)

次に、高校数学でよく扱われる次の問題を考える。

問題A, B, C, D の4種の文字から2個を選ぶとき、その選び方の総数はいくつか。ただし、同じ文字を2回以上選んではならない。

「ただし...」のくだりはわざわざ書かれていない場合も多いと思うが、典型的な出題である。指示通りの選び方は「AB」「AC」「AD」「BC」「BD」「CD」の6通りだけあるので、この問題の答えは6である。この程度ならすべて書いてみてもよいのだが、数が大きくなるとそうもいかないので、やはり計算方法を確立したいところだ。

そこで集合の言葉に直すことを試みる。まず用意された文字は先ほどと同じなので、同じように $x=\{{\rm A,B,C,D}\}$ としよう。すると「4種の文字から2個を選ぶ」というのは「$x$ の要素を 2 つ選ぶ」ということになるが、実はこれは「$x$ の部分集合を要素数が 2 になるように選ぶ」ことと一致する。なぜなら、要素数が 2 の部分集合を選べば、その要素を取り出すことで $x$ の要素を 2 個選んだことになるし、その方法で取り出せない組合せはなく (つまり数えこぼしがない)、異なる部分集合を選んだのに同じ組合せが取り出されることはない (つまり2重に数えることがない) からである。

以上のことから、「$x$ の要素を $k$ 個選ぶ選び方の総数」は「$x$ の部分集合のうち要素数が $k$ のものの個数」となるので、つまり\[\#\{y\subset x\mid \#y=k\} \]が答えとなる。「$x$ の部分集合のうち要素数が $k$ のものがすべて属し、それ以外のモノが属さない集合」を $\mathfrak{P}_k(x)$ と表すことにすれば答えは\[\#\mathfrak{P}_k(x)\]となる。やはりこれでは高校数学では正解とされないであろうから、より簡素な表現を探すことにする。

ここで、簡単のために $n=\#x$ のようにし、まずは $\mathfrak{P}_k(n)=\{y\subset n \mid \#y=k\}$ について考える。

命題$n$, $k$ を自然数とする。このとき\begin{eqnarray}\#\mathfrak{P}_{0}(n) &=& 1\\ \#\mathfrak{P}_{n}(n) &=& 1\\ \#\mathfrak{P}_{k+1}(n+1) &=& \left\{ \begin{array}{ll} 0 & \text{if $n\lt k$}\\ \#\mathfrak{P}_k(n)+ \#\mathfrak{P}_{k+1}(n) &\text{if $k\leq n$} \end{array}\right.\end{eqnarray}

(証明) まず1つ目の式を示す。$\mathfrak{P}_{0}(n)=\{\emptyset\}$ だから $\#\mathfrak{P}_{0}(n)=1$。

次に2つ目の式を示す。もし $y\in\mathfrak{P}_n(n)$ とすると $y\subset n$ であるので $y$ から $n$ への自然な単射 $a\mapsto a$ が存在する。ここで $\#y=\#n$ だからこの単射は全単射である。よって恒等な全単射が存在するので $y=n$。以上より $\mathfrak{P}_{n}(n)=\{n\}$ だから $\#\mathfrak{P}_{n}(n)=1$。

次に、3つ目の式の $n\lt k$ のときを示す。もし $y\in\mathfrak{P}_k(n)$ とすると $y\subset n$ であるので $y$ から $n$ への自然な単射 $a\mapsto a$ が存在する。一方で $\#n\lt \#y$ だから鳩の巣原理より $y$ から $n$ への単射は存在しない。したがって矛盾するので $\mathfrak{P}_k(n)$ は空集合である。

最後に、3つ目の式の $k\leq n$ のときを示す。$\mathfrak{P}_k(n)$ に属するモノがもつ要素数は $k$ であり$\mathfrak{P}_{k+1}(n)$ に属するモノがもつ要素数は $k+1$ であるので、要素数の一意性より\[\mathfrak{P}_k(n) \cap \mathfrak{P}_{k+1}(n)=\emptyset.\]したがって、加法原理より、2つの集合\[\mathfrak{P}_{k+1}(n+1) \\ \mathfrak{P}_k(n)\cup\mathfrak{P}_{k+1}(n)\]の間に全単射が存在することを示せばよい (bijective proof)。写像 $\varphi: \mathfrak{P}_{k+1}(n+1) \to \mathfrak{P}_k(n)\cup\mathfrak{P}_{k+1}(n)$を\[\varphi(y) = y\setminus \{n\}\]とすると、$\varphi$ は全単射である。

ここで $_n{\rm C}_k$ を\[_n{\rm C}_k = \#\mathfrak{P}_k(n)\]と定義すると、高校で習う通りの\[_n{\rm C}_k = _{n-1}{\rm C}_{k-1}+_{n-1}{\rm C}_k\]という漸化式が得られる。上で証明した漸化式を用いて以下の式を証明する。

命題$n$, $k$ を自然数とする。$k\leq n$ であれば\[\#\mathfrak{P}_k(n) = \frac{n!}{k!(n-k)!}\]

(証明) $n$ について数学的帰納法を用いて、任意の $n$ に対して「任意の $k\leq n$ に対して $\#\mathfrak{P}_k(n) = \frac{n!}{k!(n-k)!}$ (★)」であることを示す。

まず事前に示したように $\#\mathfrak{P}_0(0)=1=\frac{0!}{0!(0-0)!}$。

次に、固定された $n$ について★が成立するとする。このとき $1\leq k\leq n$ に対しては事前に示した漸化式より\begin{eqnarray}\#\mathfrak{P}_k(n+1) &=& \#\mathfrak{P}_{k-1}(n)+\#\mathfrak{P}_k(n) \\&=& \frac{n!}{(k-1)!(n-k+1)!} + \frac{n!}{k!(n-k)!}\\ &=&\frac{n!\cdot k}{k!(n-k+1)!} + \frac{n!\cdot (n-k+1)}{k!(n-k+1)!} \\ &=&\frac{(n+1)!}{k!(n+1-k)!}\end{eqnarray}である。また $k=0$ と $k=n+1$ に対しては事前に示したように\begin{eqnarray}\#\mathfrak{P}_0(n+1) &=& 1 \\ &=& \frac{(n+1)!}{0!(n+1-0)!}, \\ \#\mathfrak{P}_{n+1}(n+1) &=& 1 \\ &=& \frac{(n+1)!}{(n+1)!(n+1-(n+1))!}\end{eqnarray}である。以上より $n+1$ について★が成立する。

このことから、先ほど定義した $_n{\rm C}_k$ について\[_n{\rm C}_k = \frac{n!}{k!(n-k)!}\]という高校数学でおなじみの式が得られる。

では本題の $\#\mathfrak{P}_k(x)$ を計算するが、例によってこれは $\#\mathfrak{P}_k(n)$ に等しい。

命題$n$, $k$ を自然数とし、$x$ を集合とする。$\#x=n$ であるとき\[\#\mathfrak{P}_k(x)=\#\mathfrak{P}_k(n)\]

(証明) $\mathfrak{P}_k(x)$ から $\mathfrak{P}_k(n)$ への全単射が存在することを示せばよい (bijective proof)。

$\#x=n$ より全単射 $f:x\to n$ が存在する。これを用いて $\psi: \mathfrak{P}_k(x)\to\mathfrak{P}_k(n)$ を\[\psi(y)=\{f(i) \mid i\in y\} \]と定義すると、$\psi$ は全単射である。

以上から、当初の問題の答えは\begin{eqnarray}\#\mathfrak{P}_2(\{{\rm A,B,C,D}\})&=& \#\mathfrak{P}_2(4) \\ &=& \frac{4!}{2!(4-2)!}\\ &=& 6\end{eqnarray}となる。そして、一般には次のようになる。

解答「$n$ 種の文字から $k$ 個を選ぶとき、その選び方の総数はいくつか。ただし、同じ文字を2回以上選んではならない。」という問題の解答は\[\#\mathfrak{P}_k(n)\]となり、これは $k\leq n$ なら\[\frac{n!}{k!(n-k)!}\]に等しく、$n\lt k$ なら 0 に等しい。

倍数の個数(執筆中)

まとめ

ここまでで示したように、場合の数を数える問題は集合の要素数を答える問題ととらえることができ、そうすれば集合論の言葉で説明することができる。

補足: 記法について

この記事では要素数を表すのに、番号記号 $\#$ を用いたが、$A$ の要素数を $n(A)$ や $|A|$ で表すことも多いと思うので覚えておくとよいだろう。

むしろ $\#$ だけ初めて見る人が多いかもしれない。そんな人の中には「なんでシャープなんだ」と思っている者も多いだろう。実はこの記号は音楽記号のシャープではない。実際に五線譜にこの番号記号を書いてみるとかなり違和感があるはずである。というのも番号記号は2本の水平線と2本の斜線でできているので、五線譜の上に書くと水平線だらけになる。本物のシャープ (♯) なら2本の鉛直線と2本の斜線でできているのでそうはならない。ちなみに電話のボタンについているのもシャープではなく番号記号である。