131024 初版 131024 更新
数学の小部屋
トップページ
もくじ
>
経路数問題
定式化
漸化式
問題
次のような、街路の左上の点A から右下の点B に至る最短経路の数を求めよう。
各格子点の名前を図のようにして，
C
0,0
から格子点に至る経路数も同じ記号で表すことにする。
次の漸化式が成り立つ。
C
0,n
= 1, C
n,0
= 1
C
m,n
= C
m-1,n
+ C
m,n-1
このように漸化式を立てる手法は，
場面の変遷を確率で結びつける， いわゆる確率漸化式の問題で役に立つ。
つづく