ある都市には東西に走る道路が 4 本、南北に走る道路が 4 本あり、格子をなしている。北西の角 A にいる人が南東の角 B まで歩き、各交差点では東か南にしか進まない。経路は何通りあるか。

Step-by-step solution

1. 1

   どの経路も同じ回数だけ進むことを数える。 各方向に道路が $4$ 本あるので、各方向のブロック数は $3$ である。したがってどの経路もちょうど

   $3\ \text{回の東}\quad\text{と}\quad 3\ \text{回の南}$

   からなり、移動は合計 $6$ 回である。これはすべての経路について同じであり、だからこそこの数え上げは純粋に組合せの問題になる。

2. 2

   経路を文字列に置き換える。 経路は移動の順序だけで完全に決まる。つまり E が 3 つ、S が 3 つからなる長さ $6$ の文字列、たとえば $EESESS$ に対応する。異なる文字列は異なる経路を与え、どの経路も 1 つの文字列を与えるので、経路を数えることは文字列を数えることに等しい。

3. 3

   東に進む位置を選ぶ。 $6$ 個の位置のうちどの $3$ 個に E を置くかを決めれば、残りは S で埋まる。その選び方の数は

   $\binom{6}{3}$

   である。

4. 4

   二項係数を計算する。

   $\binom{6}{3}=\frac{6!}{3!\,3!}=\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1}=20$

   $\boxed{20\ \text{通り}}$

5. 5

   格子上のパスカルの三角形で検算する。 各交差点に、$A$ からそこへ至る経路の数を書き込む。最上行と左端の列はすべて $1$ で、それ以外の点は「上の点」と「左の点」の和になる。こうして $1,1,1,1$ / $1,2,3,4$ / $1,3,6,10$ / $1,4,10,20$ という行が作られ、角 $B$ には $20$ が入る ✓。二項係数による数え上げと一致する。