組み合わせ爆発のはなし - 大人になってからの再学習YouTube 上に公開された 「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」 という動画が話題になっている。 http://youtube.com/watch?v=Q4gTV4r0zRs 下の図のようなNxNの格子を用意して、左上のスタート地点から、右下のゴール地点にたどり着くルートの数を数えてみよう、というもの。 この例は3x3の格子。 さて、何通りあるか？ ルートは最短ルートである必要はなくて、下から上に向かっても構わない。ただし、ルートは自分自身に交わってはいけない。 3x3の格子の例では、答えは184通りある。 意外とたくさんあることに驚かされる。 では、4x4の場合は？ 動画の中では「おねえさん」が手で数えているけど、答えは8,512通り。 5x5の場合は、もはや手で数えるわけにはいかなくなる。動画の中のコンピュータを使って求めた答えは1,262,81
