最短経路について

質問

正方形を横に5個、縦に4個ならべた碁盤を考える(つまり線の上を通る)
このとき左下にＡ地点、右上にＢ地点を置き、Ａ地点から2つ右上の(つまりＡ地点から右に2つ、上に2つ行くと到達する)地点にＰ地点を置くとする
(1)Ｐ地点が右左折禁止(つまり通過するときは直進することしかできない)の場合、Ａ地点からＢ地点まで行く最短経路は全部で何通りあるか

答えには左から右へＰ地点を直進する場合と下から上へＰ地点を直進する場合に分けて、前者は3Ｃ1×4Ｃ2、後者は3Ｃ1×4Ｃ1通りでそれらとＰ地点が通行止めのときのＡ地点からＢ地点までの最短経路の全体を足しているのですが3Ｃ1×4Ｃ2と3Ｃ1×4Ｃ1がどういう意味か分かりません 教えてください

回答No.1

DJ-Potato · ベストアンサー

左から右へＰ地点を通過する場合
(A)　上上右　右(P)右　上上右右　(B)
みたいな経路を通るわけですよね。
Pの前後の右右は固定で、
AからPの上上右の部分が、3か所のうち１か所に右が入る場合、つまり3C1
PからBの上上右右の部分が、4か所のうち2か所に右が入る場合、つまり4C2

よって、3C1×4C2通りあるわけです。

下から上へP地点を通過する場合
(A)　右右上　上(P)上　上右右右　(B)
みたいな経路を通るわけですよね。
Pの前後の上上は固定で、
AからPの右右上の部分が、3か所のうち１か所に上が入る場合、つまり3C1
PからBの上右右右の部分が、4か所のうち1か所に上が入る場合、つまり4C1

よって、3C1×4C1通りあるわけです。

あと、Pを通らない経路を足したら、全部の最短経路が得られる、と。

お礼

理解しました
回答ありがとうございました