Project Euler 015

問題15
20マス*20マスのグリッドの左上から右下へと到るルートは何通りあるか求める。

正直言って、解き方わからない。いろいろ調べてみたら、40C20ということなのでそういうことなら、と結城さんの本を引っ張りだしてきて式に当てはめてみる。

| n k |
n := 40.
m := 20.
^n factorial / (m factorial * (n - m) factorial))

答えは出たみたいだけど、なんで組み合わせでこの問題が解けるのかさっぱり。

後の宿題にする。

ちょっとだけぐぐった。どういうときに、こういう分類をされるかがわからないことには、式だけわかっても仕方ない。
置換 -> nPn = n!
順列 -> nPm = n! / (n-m)!
組み合わせ -> nCm = n! / n!(n-m)!