最短経路の数 = 組合せ

アニメを見なくても、このページの流れを最後まで文章で追えるよ。

1. ① 考えてみよう
2. 1

   左下のSから右上のGまで進むよ。動けるのは右(→)か上(↑)だけ。遠回りなしの最短で行く道は、ぜんぶで何通りあると思う?

3. 2

   1本ずつ全部の道を描いて数えるのは大変そう…。交差点ごとに「そこまで何通りで行けるか」を書きこむ、うまい数え方はないかな?

4. ② 考え方
5. 3

   たとえばこの道。右・右・上・右・上だね。横3マス・縦2マスだから、どの道も必ず右に3回・上に2回、合わせて5回の動きでできてるよ。

6. 4

   数えるコツ。各交差点まで「何通りで行けるか」を書きこむよ。いちばん下の道といちばん左の道は、まっすぐ進むしかないから、どれも1通りだね。

7. 5

   内側の点へは「左から」か「下から」しか来られない。だからその点の数は、左どなりと下の数を足したもの。真ん中の段は 1+1=2、1+2=3、1+3=4 だよ。

8. ③ 解答
9. 6

   同じように上の段も足し算でうめると、3・6ときて、ゴールGは 4+6=10。最短の道はぜんぶで10通りだ!

10. 7

    この10は、5回の動きのうち「どの2回を上にするか」を選ぶ数=${}_{5}\mathrm{C}_{2}$とぴったり同じ。右3個・上2個を並べる順列でもあるね。経路の数は組合せで一発だよ。