プロジェクトオイラー15. ~ Lattice Paths ~

No.15 Lattice Paths

$2\times 2$ の格子の左上の角から始めて, 右か下への移動のみ可能であるとき, 右下の角へ移動する道は 6 通りある.

では, $20\times 20$ の格子では何通りあるか求めよ.

$N\times N$ の格子において左上から右下まで, 右または下への移動のみで行く方法は,

\begin{align*}
{}_{2N}C_{N} &= \dfrac{(4N)!}{(2N)!(2N)!}\\
&= \dfrac{4N\cdot(4N-1)\cdots (2N+1)}{2N\cdot (2N-1)\cdots 1}
\end{align*}

なので, これを計算すればいいだけなのですが, 分母と分子をそれぞれ計算して割り算しようとすると, $N=20$ だと分母, 分子がそれぞれ大きくなりすぎてしまい, うまく計算できません.

そこで, 次の式を使います.

$\begin{align*} {}_nC_k &= {}_nC_{k-1}\cdot \dfrac{n-k+1}{k} \end{align*}$

この式を使って,

$\begin{align*} {}_{40}C_0, {}_{40}C_1, \ldots, {}_{40}C_{20} \end{align*}$

の順に求めていきます.

この方法を使えば, $N$ が20 よりももっと大きい数でも2項係数を計算できます.

N = 20
binom = 1
for k in range(1, N+1):
    binom = binom * (2 * N - k + 1) / k
print(binom)