【数学】最短経路問題

対象：定期試験以上

今回は　最短経路問題です
前提として　同じものを含む順列　の理解が必要です

最短経路の基本的な問題です
総数は同じものを含む順列で考えることができます
経由点がある場合には　A→C　C→B　とわけて考えましょう
Pを通らないものは　今回は余事象で数えています

いずれにしても　この問題が簡単な計算で出来るのは
経路全体が規則的だからです
つまり　経路自体に規則性がなければ　他の方法をとることになります

AからBに逃げる犯人に　警察が検問を仕掛けます
検問の数をできるだけ少なく
かつ　2か所の検問を通るような経路がなく
かつ　抜け道がないように設置すると
例えば　上図のC，D，E，Fのようになります
全体としては不規則ですが
A→検問　検問→B　の経路は規則的なので　数えることができます

一方　地道に1つ1つ数えていく方法もあります

すべてを数え上げる　という最も基本的で地味なものですが
規則性がないものについては　重宝する数え方です

二項係数を用いて書いています
パスカルの三角形が現れていますね

以上　最短経路問題でした