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

この記事の所要時間: 134

No.15 Lattice Paths

問題.

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

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

考え方とプログラム例(Python3).

\(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項係数を計算できます.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加