去年聞いた中で、私が一番感動した式の話。
k! = limn→∞ nk / nCk
kの階乗は、「nのk乗 ÷ n個のものからk個選ぶ組み合わせの数」という式で n を無限に大きくしていったときの収束先、である。 特に難しい証明が要るとかではなくて、nCk = n(n-1)(n-2)...(n-k+1) / k! であることを使うと、
limn→∞ nk / nCk
= limn→∞ nk k! / n(n-1)(n-2)...(n-k+1)
で、n が k に比べて十分大きければ n も n-k+1 もほとんど同じ値なので、 分子も分母もだいたい n を k 個かけているわけでして、 その部分が相殺して、k! が残るという寸法。 （厳密な表現ではないので、気になる人は厳密に証明してください。）
と、この式自体はそんなに不思議ではないのです。面白かったのはこの式が現れた文脈でした。
何かすっごくヘンテコな言語（Brainfuckとかそういうの系）でプログラム書いてて、 整数の四則演算はまあ割と簡単に実装できたんですけど、物凄く頑張ってやっとベキ乗の計算ができて、 次に何故か階乗よりも簡単に nCk の計算が作れてしまった！ という状況なのです。 次は階乗を実装したい…どうしましょう、という文脈で出てきたのが上記の式。 割り算とベキ乗とnCkで書けてるから、これで実装できるんじゃ？
とんでもない、数列の n→∞ の極限を求めるなんて演算、 普通の言語でも難しいのに、こんなまともにループも書けない言語で…、 と私は聞いて思いました。ところが、できるんです。 Python で説明すると、こういう実装。
from functools import reduce
def c(n,k): # nCk は実験用に手抜きの普通の定義
si = reduce(lambda x,y:x*y, range(n,n-k,-1), 1)
bo = reduce(lambda x,y:x*y, range(1,k+1), 1)
return si // bo
# 階乗！
def factorial(k):
n = (k+1)**(k+2)
return n**k // c(n,k)
print( factorial(1) ) # 1
print( factorial(2) ) # 2
print( factorial(3) ) # 6
print( factorial(4) ) # 24
print( factorial(5) ) # 120
print( factorial(6) ) # 720
Python 使わない人向けに補足説明すると、
** はベキ乗演算（例： 2**16 は 65536）で、
// は整数除算（例：7//2 は 3）です。
説明されるととても当たり前なんですが、
n→∞ で収束すると言うことは、nを十分大きくすれば極限との差が 1 よりも小さくなる、
ということです。なので、ここで整数÷整数が整数になる整数除算を使えば、
余りは切り捨てられて、割り算一撃で n→∞ の極限が求まってしまうのでした。
n を (k+1)**(k+2) まで大きくすれば差が 1 より小さくなることも、頑張ると証明できます。
割り算結果を正確に実数で出す実数の割り算と比べると、 整数除算、というか、余りを切り捨てる floor 演算って、 実用面はともかく理論的にはなんかショボいことしかやってないような気がしてしまっていました。 計算機が無限小数を表現できないから、しかたなく途中で打ち切って我慢している、みたいな。 けど、見方を変えるとコイツは 「nを∞に飛ばしたときの極限の計算」 なんて恐ろしいことを一演算でやってのけたりするんですよね。見直しました。
で、この非常に怪しい階乗の実装がでてきた出所はどこかというと、 ヒルベルトの第10問題 の証明です。 1900年に当時の23大未解決問題として提唱されてから解決まで 70 年かかったこの問題は、 「ディオファントス方程式を使ってチューリングマシンの停止問題をエンコードできる」ことが示されて解かれました。 足し算と掛け算だけの連立方程式さえあれば、ありとあらゆる計算能力をエンコードできる、 と示す、まさに変態プログラミングてんこ盛りの証明です。
なんでも、ベキ乗さえ作れれば、そこから nCk や上に書いたように階乗や、 ありとあらゆる計算を記述していくのは、どっちかというと簡単な方だそうです。 とにかくこのディオファントス方程式という esoteric 言語では、 「誰もベキ乗の実装の仕方がわからなかった」せいで、 長年未解決問題として君臨することになったらしい。 面白いですね。