2×2の格子を左上から出発して逆戻りせずに右下に移動するには6通りの経路が ある。（図はProject Eulerのサイト参照）
20×20の格子の場合の経路の数を求めよ。
この問題はプログラムを書かなくても答えを求めることができる。逆戻りをせ ずに移動する場合、どんなルートを通っても右に20回、下に20回の計40回移動 することになる。つまりは40回の移動のうちのいずれか20回が右への移動であ る組み合わせの数を求めればいいわけだ。式で書く と40C20ということになる。ここではcombinationを Haskellで書いて計算してみることにする。定義は以下のようにmに関する再帰 で直感的なものとした。これは割り算を使っているので決して高速ではないが、 今回の用途には問題ない。
combination n 1 = n combination n m = (combination (n - 1) (m - 1)) * n `div` m euler015 = combination 40 20