パスカルの三角形

格子上の2点間の最短経路の数を求めるときにパスカルの三角形をどのように使うかです。
下図のような格子上の点アから各点の最短経路の数について説明します。


点アから右に隣接する点イに至る経路の数は1です。また、点アから上に隣接する点オに至る経路の数も1です。
次に点アから斜め上の点カに至る最短経路の数を考えます。
点アから点カへの最短経路は、点カの下の点イか、点カの左の点オを経由しないといけません。また、点イから点カと点オから点カの経路はそれぞれ1なので、点アから点カに至る最短経路の数は点アから点イに至る最短経路の数と、点アから点オに至る最短経路の数の和になります。すなわち、1+1=2です。

同様に、点アから点キに至る最短経路の数を考えます。
まず、点アから右に2つ離れた点ウに至る最短経路の数は、点ウへの最短経路は必ず点イを経由し、点アから点イへの最短経路の数が1なので、点アから点ウへ至る最短経路の数も1になります。
点アから点キに至る最短経路は点ウか点カを必ず経由し、点アから点ウへの最短経路の数は1、点アから点カの最短経路の数は2なので、点アから点キへ至る最短経路の数はこの和になり、1+2=3です。(ここで、点アから見て点キと対象の位置にある点コの最短経路の数も同様に3になります。)

もう一つ、点アから点サに至る最短経路の数を求めてみます。
点アから点サへの最短経路は点キか点コを経由します。点アから点キ、点アから点コの最短経路の数はそれぞれ3なので、点アから点サに至る最短経路の数はこの和を求めて、3+3=6になります。

以下同様に、各点の経路の数を求めると、下の図のようになります。


格子上の2点間の最短経路の数を求める方法としては組合せの考えを用いる方法もありますが、点キと点サの経路が通れない場合に、点アから点シまでの最短経路の数を求めるときなどは、組合せを用いて解くのは難しいので、パスカルの三角形を用いたほうが簡単になりますので、この解き方も知っていると便利です。
ちなみに、点キと点サの経路が通れないときの点アから点シまでの最短経路の数は下図のようになります。
　

このくらいの問題までだと組合せの式を使っても解くことが可能なので、パスカルの三角形を使うメリットをあまり感じない人もいると思いますが、更に複雑な3次元の経路を数える場合パスカルの三角形の応用以外で解くことは非常に困難でしょう。

戻る 一覧へ