一時期ネットでも少し話題になった、数学の「組み合わせ爆発」という問題を皆さんは耳にしたことがあるだろうか。
縦横１マスの格子、つまり漢字の口の字であるが、これを辺にそって対角の点から点まで最短で進むルートは２通りである。縦横２マスの格子、漢字の田の字だが、これを対角まで最短で進むルートは６通りだ。これくらいなら、一目見て数えられるだろう。しかしマス目の数が増えるごとにルートの数はどんどん跳ね上がり、縦横10マスの格子ともなると、そのルートの数を全て数え上げるのに当時のスパコンで数十万年かかるらしい。
ではなぜ格子の対角を結ぶルートの数は、文字通り爆発的に増えるのだろうか。試しに格子問題の解を一般化してみる。縦横ｎマスの格子を対角から対角まで結ぶためには、横にｎマス、縦にｎマス、合計２ｎマス進まなくてはならない。そしてその過程で、縦に進む機会はｎ回ある。よってその組み合わせの数は、
2ｎＣｎ=(2ｎ)!/(ｎ!)^2
となる。ここで肝要なのは、これはｎを含む部分をｎ回掛け合わせた数になることだ。ざっくり言うと、
ｙ=ｘ^ｘ
この関数が凄まじい増加をすることは想像に難くないだろう。
途方もなく膨大な数を、よく天文学的数字と言ったりする。けれど天文学に用いられる数は、例えば観測可能な宇宙に含まれる全ての素粒子の数であっても、せいぜい10^80程度だ。しかし格子問題に代表される数学の組み合わせという分野では、それを遥かに凌駕する巨大数がバンバン登場する。俺などは根っからの文系であるが、それでも興味は尽きないではないか。