場合の数の問題

A から B までは、東へ 4 区画、北へ 3 区画進みます。

各交差点に「A からその交差点まで、遠回りしないで行く道順の数」を書きこんでいきます。ある交差点への道順の数は、その交差点の 西どなりの数と南どなりの数をたしたもの になります。ただし、通れない C には 0 を書きます。

交差点を「A から東へ何区画、北へ何区画」で表し、南の列から順に書くと次のようになります（左が西）。

• 北へ 0 区画の列: 1, 1, 1, 1, 1
• 北へ 1 区画の列: 1, 1+1=2, 0（C）, 0+1=1, 1+1=2
• 北へ 2 区画の列: 1, 1+2=3, 3+0=3, 3+1=4, 4+2=6
• 北へ 3 区画の列: 1, 1+3=4, 4+3=7, 7+4=11, 11+6=17

いちばん北の列のいちばん東が B なので、道順は 17 通りです。

（別の考え方）C を通ってもよいときの道順は、上と同じ書きこみで C に 0 を書かずに計算すると 35 通りです。A から C までは 3 通り、C から B までは東へ 2 区画・北へ 2 区画で 6 通りなので、C を通る道順は $3\times 6=18$ 通りです。よって $35-18=17$ 通りとなり、答えが一致します。

東西の道が 4 本、南北の道が 5 本なので、A から B までは東へ 4 区画、北へ 3 区画進む。
まず工事がないときの道順を、各交差点に行く道順の数を A から順に足して求める（A の北と東は 1 通りずつ、あとは「南の交差点の数＋西の交差点の数」）。A から B までは 東 4 回・北 3 回の並べ方なので 7 回のうち北の 3 回の位置を決めて $7\times 6\times 5÷(3\times 2\times 1)=35$ 通り。
次に C（東へ 2、北へ 1 の交差点）を通る道順を数える。
A から C まで: 東 2 回・北 1 回の並べ方で 3 通り。
C から B まで: 東 2 回・北 2 回の並べ方で $4\times 3÷(2\times 1)=6$ 通り。
C を通る道順は $3\times 6=18$ 通り。
C を通らない道順は $35-18=17$ 通り。
検算: 各交差点までの道順を書いていく。下の段（一番南）は 1,1,1,1,1。2 段目は 1,2,3,4,5。3 段目は 1,3,6,10,15。4 段目は 1,4,10,20,35。C（東へ 2、北へ 1）は 3 を持つので C を通れないとして 3 を 0 にすると、2 段目は 1,2,0,2,2。3 段目は 1,3,3,5,7。4 段目は 1,4,7,12,19。…ここで C を 0 にしただけでは正しくないので数え直す。C は 2 段目の左から 3 番目で、この交差点を 0 にすると 2 段目: 1,1,0,0+... と計算し直す。2 段目は左から 1, 2, 0, (0+1)=1, (1+1)=2。3 段目は 1, 3, 3, 4, 6。4 段目は 1, 4, 7, 11, 17。B の道順は 17 通りで、先の答えと一致する。