格子上の経路

Project Euler 15

2$\times$2 マスの左上隅からスタートし、右方向および下方向にしか移動できない場合、右下隅への行き方は6通りである。

20$\times$20 の場合、何通りあるか？

---

どのような通り方をしても、40 回のうち右方向および下方向に 20 回移動しなければならない。
よって、組み合わせ ${}_{40}C_{20}$ により計算できる。

組み合わせ ${}_mC_n$ は 順列 ${}_mP_n$ により ${}_mC_n = \frac{{}_mP_n}{n!}$ となることから、順列／組み合わせ関数を以下のように定義して計算すればよい。

def permutations(n, c=None):
    x = math.factorial(n)
    if c is not None:
        if c < 1:
            raise ValueError
        x = x/math.factorial(n-c)
    return x


def combinations(n, c):
    return permutations(n, c)/permutations(c)