靴下洗濯問題の美しい解法

はじめに

先日、ふと思いついて次のような問題を投稿した。

高橋くんは十分大きなN組の相異なる靴下を持っています。この2N本から無作為にN本選んで洗濯し、残りのN本は捨てました。さらに、洗濯したN本のうち、相方が捨てられてしまった靴下も捨てました。この操作を1回行ったあと、残っている高橋くんの靴下の割合の、N→∞における極限を求めてください。
— かりばぁ🐬（右上のかりんちゃん） (@KRiver1) 2018年11月12日

問題は以下の通りだ。
まず、 $N$ 組の相異なる靴下を用意する。 $N$ 組なので、当然靴下は全部で $2N$ 本あることになる。
次に、この $2N$ 本の靴下から、無作為に $N$ 本の靴下を選択する。
そして、選択した $N$ 本の靴下の中で、ペアが揃っている靴下が何組あるかを数える。
このときの揃っている靴下の組を $f(N)$ とするとき、期待値 $\mathbb{E}\left[\frac{f(N)}{N}\right]$ （とその $N\rightarrow \infty$ の極限）を求めるという問題だ。

この問題について、仕事の早い友人から非常に綺麗で美しい解法を貰ったので、ぜひとも紹介させてほしい。
もちろん、興味のある人は先に自分で解いてみるといいと思う。

解法

まず、 $f(N)$ の期待値を求めたいので、 $P(x)=P\left(f(N)=x\right)$ を計算する。
そのために、 $N$ 本の靴下を選択する組み合わせを数えることにしよう。

$N$ 本の靴下を選択する組み合わせは、全部で ${}_{2N} C_{N}$ 通りである。これを $M_N={}_{2N} C_{N}$ とおく。

一方、 $P(0)$ をまず考えると、これは靴下が1組も揃わない場合だから、すべての靴下について右か左を選択することになる。
ゆえに、この組み合わせは $2^{N}$ 通りであり、 $P(0) = 2^{N} / M_N$ である。

また、 $P(1)$ を考えると、まず揃う靴下の組を1つ選択して、次に両方とも選択されない靴下の組を1つ選んで、最後に残り $N-2$ 組の左右を決めることになるから、この組み合わせは $N\cdot (N-1) \cdot 2^{N-2}$ 通りであり、 $P(1) = N\cdot (N-1) \cdot 2^{N-2} / M_N$ である。

同様に考えて、 $P(i) \; (0\le i \le \frac{N}{2})$ は、

$\displaystyle M_N P(i) = {}_{N}C_{i} \cdot {}_{N-i}C_{i} \cdot 2^{N-2i}$

となることがわかる。ただし、 $N$ が偶数であることを仮定した。
（以下の議論は $N$ が奇数でもおおよそ成り立つし、最後は極限に飛ばすのでおおよそ問題ない。）

したがって、期待値 $E_N = \mathbb{E}\left[\frac{f(N)}{N}\right]$ は

$\displaystyle \begin{align} \begin{aligned} E_N =& \frac{1}{N}\sum_{i=0}^{\frac{N}{2}} i \cdot P(i) \\ =& \frac{1}{N \cdot M_N} \sum_{i=1}^{\frac{N}{2}} i \cdot {}_{N}C_{i} \cdot {}_{N-i}C_{i} \cdot 2^{N-2i} \end{aligned} \end{align}$

となる。

さて、このように組み合わせと期待値が登場する場合、組み合わせに関する等式

$\displaystyle \begin{align} \begin{aligned} i\cdot {}_{N}C_{i} =& i \cdot \frac{N!}{i!(N-i)!} \\ =& \frac{N (N-1)!}{(i-1)! \left(\left(N-1\right) - \left(i-1\right)\right)} \\ =& N \cdot {}_{N-1}C_{i-1} \end{aligned} \end{align}$

を用いて $i$ を消滅せしめることがよく行われる。今回もそれを用いて、

$\displaystyle \begin{align} \begin{aligned} E_N =& \frac{1}{N \cdot M_N} \sum_{i=1}^{\frac{N}{2}} i \cdot {}_{N}C_{i} \cdot {}_{N-i}C_{i} \cdot 2^{N-2i} \\ =& \frac{1}{M_N} \sum_{i=1}^{\frac{N}{2}} {}_{N-1}C_{i-1} \cdot {}_{N-i}C_{i} \cdot 2^{N-2i} \end{aligned} \end{align}$

とする。

ここまでは進んだ方もいるのではないだろうか。
ここからが本当の問題である。この複雑な組み合わせに関する式をどう計算すればよいだろうか。

ここで、右辺の組み合わせの積をよく凝視してみる。
すると、シグマの中が

$\displaystyle \begin{align} \begin{aligned} & {}_{N-1}C_{i-1} \cdot {}_{N-i}C_{i} \cdot 2^{N-2i} \\ =& {}_{N-1}C_{i-1} \cdot {}_{\left(N-1\right) - \left(i - 1\right)}C_{i} \cdot 2^{\left(N-1\right) - \left(i - 1\right) - i} \end{aligned} \end{align}$

という形をしていることに気づけるだろう。

すなわちこれは、「 $N-1$ 個のモノの中から、まず $i-1$ 個を取り、次に $i$ 個を取る組み合わせ」の数だけ $2$ を掛けた値である。

見覚えのある形だ。
そう、二項定理である。

二項定理は次のような等式だった。

$\displaystyle {(a+b)}^N = \sum_{i=1}^{N} \cdot {}_{N}C_{i} \cdot a^{i} \cdot b^{N-i}$

これがなぜ成り立つのかというと、 $(a+b)^N$ を展開した時に、 $a$ を $i$ 回、 $b$ を $N-i$ 回掛けた項が出てくる重複回数が、ちょうど ${}_N C_{i}$ 回に等しいからであり、それをすべての $i$ について考えた結果は、ちょうど $(a+b)^N$ の展開した項をすべて考えた結果に等しくなるからである。

ゆえに、今回も同じように考えればよい。

$\displaystyle \begin{align} \begin{aligned} & {}_{N-1}C_{i-1} \cdot {}_{\left(N-1\right) - \left(i - 1\right)}C_{i} \cdot 2^{\left(N-1\right) - \left(i - 1\right) - i} \\=& {}_{N-1}C_{i-1} \cdot {}_{\left(N-1\right) - \left(i - 1\right)}C_{i} \cdot 1^{i-1} \cdot 1^{i} \cdot 2^{\left(N-1\right) - \left(i - 1\right) - i} \end{aligned} \end{align}$

であるから、これをすべての $i$ について足した和は「 $N-1$ 回選べる状況で、 $1$ を $i$ 回、 $1$ を $i-1$ 回、残りは $2$ を選択した」値になっている。
これがもし、

$\displaystyle \sum_{i=1}^{N-1} \sum_{j=0}^{N-1-i} {}_{N-1}C_{i-1} \cdot {}_{\left(N-1\right) - \left(i - 1\right)}C_{j} \cdot 1^{i-1} \cdot 1^{j} \cdot 2^{\left(N-1\right) - \left(i - 1\right) - j}$

のようになっていれば、二項定理の応用（三項定理とでも呼べばよいだろうか）で答えは $(1+1+2)^{N-1}=4^{N-1}$ となっていただろう。

ところが、今回はそうではなく、

$\displaystyle M_N E_N = \sum_{i=1}^{\frac{N}{2}} {}_{N-1}C_{i-1} \cdot {}_{\left(N-1\right) - \left(i - 1\right)}C_{i} \cdot 1^{i-1} \cdot 1^{i} \cdot 2^{\left(N-1\right) - \left(i - 1\right) - i}$

と、シグマが一個少なくなっている。

これが何を表しているのか。

つまり、「 $(1+1+2)^{N-1}$ の展開項のうち、2つ目の $1$ と1つ目の $1$ を選んだ回数の差がちょうど $1$ であるような項だけを足した値」を表しているということになる。

より具体的に言えば、（負の冪を含む）多項式 $(x+\frac{1}{x} + 2)^{N-1}$ の、 $\frac{1}{x}$ の係数がちょうど $M_N E_N$ に等しいのである。

さて、ではこの係数、 $(x+\frac{1}{x} + 2)^{N-1}$ の $\frac{1}{x}$ の係数を求めれば良いとわかったところで、これをどう求めればよいだろうか。

実はここでも二項定理を用いる。
二項定理にしたいので、3つも項があるいまの状況は困りものだ。
そこで、次の事実を用いよう。

$\displaystyle \left( \sqrt{x} + \frac{1}{\sqrt{x}} \right)^2 = x + \frac{1}{x} + 2$

これを用いて、上の式を書き換えると以下のようになる。

$(x+\frac{1}{x} + 2)^{N-1} = \left( \sqrt{x} + \frac{1}{\sqrt{x}} \right)^{2N-2}$

これは $y=\sqrt{x}$ についての多項式であり、この式の $y^{-2}$ の係数が求めたい値である。
これは明らかに「 $2N-2$ 個の因数において $N$ 個 $\frac{1}{y}$ を、 $N-2$ 個 $y$ を取る場合の数」に等しいから、この値は ${}_{2N-2}C_{N}$ であるとわかる。

以上より、

$\displaystyle \begin{align} \begin{aligned} M_N E_N =& {}_{2N-2}C_{N} \\ E_N =& \frac{(2N-2)!}{N! (N-2)!} \cdot \frac{N! N!}{(2N)!} \\ =& \frac{(2N-2)!}{(2N)!} \cdot \frac{N!}{(N-2)!} \\ =& \frac{N-1}{2(2N-1)} \end{aligned} \end{align}$