英語できない

学生時代に,英語が絶望的に苦手な後輩がいた。彼は選択式の英語の試験でも適当に解答し,めでたく0点を取ったという筋金入りの英語できない系だ。試験はA〜Zまで26個の選択肢を持った英語のフレーズ・単語について,同じく1〜26まで並んだ日本語と結びつけるというものだったそうなのだけど,それはすごい確率なんじゃないかと思い,計算してみたことがある。完全順列,と言ってピンとくる人には対して目新しいところのないネタであると思うが,数理ネタのレパートリーにひとまず加えられることとなった。彼に対しては少しだけ申し訳ないところだが,受けは良い。
実際に彼が達成した偉業の確率を計算してみよう。彼は英語が本当にサッパリなので,ランダムに選択肢を結びつけたと仮定することにする。N個の選択肢をすべて外す確率はいくつか?を計算しよう。まずは選択肢の数が小さいところで様子を見てみる。例えばN=2とする。この時は全問外れの組み合わせは当然(a,b)=(2,1)の1通りで,こうなる確率は1/2!=50%である。次にN=3とする。この時,全問外れの組み合わせは(a,b,c)=(2,3,1), (3,1,2)の2通りで,こうなる確率は2/3!=33.3%である。同じように計算すればN=4の場合は,3/8=37.5%である。この時点でなんとなく,この値が有限に収束していきそうなことは想像ができる。


以降,正答を(a[1], a[2], ..., a[N])=(1, 2, ..., N)と表すことにする。このとき,全問外れる条件はすべてのi=1, 2, ..., Nについてa[i]≠iであることである。すなわちこれは完全順列の組み合わせである。完全順列は大学入試では頻出で,Nに対するその組み合わせの数c[N]に関しての漸化式が知られている。
c[n+1] = n (c[n] + c[n-1]) (n = 2, 3, ...) …①
初期条件をc[1] = 0, c[2] = 1と定めれば,以降c[3] = 2, c[4] = 9と求まる。

さて,完全順列を与える①式の一般項が求まればめでたしで,求めたかった,全問外れとなる確率p[N]はc[N]/N!となる。①式の両辺から(n+1)c[n]を引いてみると,c[n+1] - (n+1)c[n] = - c[n] + nc[n-1]となり,これはC[n]=c[n] - nc[n-1]と置いた漸化式C[n+1]=-C[n]に他ならない。C[2] = - C[3] =...= (-1)^n C[n]=1より,
c[n] - nc[n-1] = (-1)^n 両辺を n!で割れば
p[n] - p[n-1] = (-1)^n/n! となる。ここまでくればしめたもので,nについて2〜Nの和を取れば
p[N] = p[1] + Σ[n=2,...,N](-1)^n/n! となる。p[1]=0なので,結局,
p[N] = Σ[n=2→N](-1)^n/n! である。

高校生なら,大学入試ならここまでだろうが,これはどう見てもe^-xのテイラー展開である。すなわち問題数N無限大の極限において,このタイプのテストで全問間違いになる確率は
p[N] → Σ[n=0→∞](-1)^n/n! = 1/e ≒ 36.8%
やはり有限値になるのである。

ちなみにその後輩が挑んだN=26のテストにおける全問外れ確率p[N]が1/eからどれだけ近いか気になるところであるが,その差は非常に小さくておそらく数十桁の数値計算で評価できるかもしれないが,Cのlong long int型でも高々20桁なので正確な評価は期待できない。そこで,ここではN=26での1/26!をもって上から評価してお茶を濁そう。26!=403291461126605635584000000=4e26よりp[26]-1/e < 2.5e-27。この評価にどれだけの意味があるのかわからんが。


ちなみに彼のその後であるが,期末テストで盛り返し,その学生をかわいがっていた先生の手心もあり,留年することなく卒業した。就職も決まり,現在修士論文を書いているそうである。