右(下)のような街路で、PからQまで行く最短経路のうち、次の場合は何通りあるか。
(1) 総数
(2) Rを通る経路
(3) R,Sをともに通る経路
(4) ×印の箇所を通らない経路
解
(1) 792通り
PからQに進むには右に移動を7回、上に移動を5回する必要があります。
簡単にすると、右7個と上5個の計12個を一列に並べればOKです。
例 右右右右右右右上上上上上
12個あるので12！
右は7個あるので7！で割ります。
さらに、上は5個あるので5！で割ります。
よって
12！÷7！÷5！＝792通りになります。
＊12！÷7！＝12・11・10・9・8になることを知っていると少し楽に解けます。
(2) 350通り
PからRまでの道と、RからQまでの道を分けて考えましょう。
PからRまでは右が3回、上が2回必要なので
5！÷3！÷2！＝10通り
RからQまでは右が4回、上が3回必要なので
7！÷4！÷3！＝35通り
PからRまでと、RからQまでを組み合わせて考えると
10・35＝350通りになります。
(3) 120通り
(2)と同様に、
PからRまでの道、RからSまでの道、SからQまでの道に分けて考えましょう。
PからRは右が3回、上が2回必要なので
5！÷3！÷2！＝10通り
RからSは右が1回、上が2回必要なので
3！÷1！÷2！＝3通り
SからQは右が3回、上が1回必要なので
4！÷3！÷1！＝4通り
3つを組み合わせて考えると
10・3・4＝120通りになります。
(4) 582通り
×を通る場合を求めて総数から引きましょう。
Pから×の左端までは、右が4回、上が3回必要なので
7！÷4！÷3！＝35通り
×の右端からQまでは、右が2回、上が2回必要なので
4！÷2！÷2！＝6通り
組み合わせると35・6＝210通りになります。
総数は(1)で求めているので
792ー210＝582通りになります。
HPやYoutubeはこちらからどうぞ ↓ ↓ ↓
