別解を解説

$\mathrm{A}$ 以外の地点を $2$ 度通ることのない経路は交差のないループを作りますが、そのループに沿って歩く方法には時計回りのもの（下図　青）と反時計回りのもの（下図　赤）の $2$ つがあります。そこで反時計回りのものだけを数えることにしましょう。 $\fbox{$\mathsf{エオ}$}$ の答はその $2$ 倍ということになります。

　反時計回りの非交差経路は必ず $\mathrm{A \to X \to Y \to B \to Z \to W \to A}$ と移動します。それは例えば最初に$\mathrm{A \to W}$と進んでしまうと、反時計回りに $\mathrm{A}$ に戻ってくることが出来なくなるからです。他の部分についても同様です。さらに $\mathrm{X \to Y}$ 部分と $\mathrm{Z \to W}$ 部分が同じ点を通ってはいけません。そのような経路の総数を数えたいのです。

　まずは途中で交差してはいけないというルールを外して、つまり $\mathrm{A}$ 以外の点を $2$ 回通ってもよい（通らなくてもよい）として、 $\mathrm{A \to X \to Y \to B \to Z \to W \to A}$ と移動する経路の数を考えてみましょう。この場合、自由に動けるのは $\mathrm{X \to Y}$ の部分と $\mathrm{Z \to W}$ の部分です。

　よく知られた計算方法により、$\mathrm{X}$ から $\mathrm{Y}$ に至る最短経路は $\dfrac{4!}{2!2!}=6$ 通り存在します。 $\mathrm{Z}$ から $\mathrm{W}$ に至る最短経路も同じく $6$ 通りです。従って交差してもよい経路の総数は、 ($\mathrm{X}$ から $\mathrm{Y}$ に至る最短経路、 $\mathrm{Z}$ から $\mathrm{W}$ に至る最短経路) の組合せとして $6\times 6=36$ 通りとわかります。

　ただしこれは交差する経路も含めての総数ですから、交差しない経路の数を求めるためには交差する経路の数を引かねばなりません。そして、なんとこれが巧妙に計算出来てしまうのです。

　そのために、 ($\mathrm{X}$ から $\mathrm{Y}$ に至る最短経路、 $\mathrm{Z}$ から $\mathrm{W}$ に至る最短経路) の組合せに代えて、 ($\mathrm{X}$ から $\mathrm{Y}$ に至る最短経路、 $\mathrm{W}$ から $\mathrm{Z}$ に至る最短経路) の組合せを考えることにします。もちろんこれは $\mathrm{Z \to W}$ 部分を逆にたどって $\mathrm{W \to Z}$ と考えるだけですから、経路の数としては違いはありません。 総数は先程計算したように $36$ です。そして除くべき経路はやはり、これらのペアのうちその両方が同一の点を通るものの数です。

　ここで驚くべきことに次が成り立ちます。

　もしもこれが成り立つのであれば、 $36$ 通りの経路のうち同一の点を通るため排除すべき経路の総数が、「( $\mathrm{X}$ から $\mathrm{Z}$ に至る最短経路の総数)$\times$( $\mathrm{W}$ から $\mathrm{Y}$ に至る最短経路の総数)」 として $\dfrac{4!}{1!3!}\times \dfrac{4!}{3!1!}=16$ 通りと計算され、結果として反時計回りの非交差経路が $36-16=20$ 通りだとわかります。従って $\fbox{$\mathsf{エオ}$}$ の答はその $2$ 倍の $40$ 通りと求められるのです。そのからくりを以下で解説します。

　 $\mathrm{X}$ から $\mathrm{Y}$ に至る最短経路 $p$（左図の赤線） と $\mathrm{W}$ から $\mathrm{Z}$ に至る最短経路 $q$（左図の青線） が同一の点を通るとしましょう。イメージしやすいように次のような状況を設定してみます。

$\mathrm{P}$ さんは $p$ の描かれた地図を持っていて、その指示に従って $\mathrm{X}$ から $\mathrm{Y}$ へ、 $1$ 分につき $1$ 区間ずつ、トータル $4$ 分で移動します。同様に $\mathrm{Q}$ さんは $q$ の描かれた地図を持っていて、その指示に従って $\mathrm{W}$ から $\mathrm{Z}$ へ、 $1$ 分につき $1$ 区間ずつ、トータル $4$ 分で移動します。 $p, q$ は同一の点を通るので、 $\mathrm{P}$ さんと $\mathrm{Q}$ さんはどこかで出会うはずです。最初に出会う点を $\mathrm{C}$ とおきます。

さて、点 $\mathrm{C}$ で $\mathrm{P}$ さんと $\mathrm{Q}$ さんが持っている地図を交換したらどうなるでしょうか？
$\mathrm{P}$ さんは点 $\mathrm{C}$ 以降地図 $q$ に従って歩き、最終的に $\mathrm{Z}$ にたどり着きます。全体として $\mathrm{X}$ から $\mathrm{Z}$ へ最短距離を歩いたことになります。（右図の赤線 $r$）
$\mathrm{Q}$ さんは点 $\mathrm{C}$ 以降地図 $p$ に従って歩き、最終的に $\mathrm{Y}$ にたどり着きます。全体として $\mathrm{W}$ から $\mathrm{Y}$ へ最短距離を歩いたことになります。（右図の青線 $s$）
この二人の経路を合わせると、 ( $\mathrm{X}$ から $\mathrm{Z}$ に至る最短経路、 $\mathrm{W}$ から $\mathrm{Y}$ に至る最短経路) のある $1$ 組が決まります。
この手順によって、 $(\mathrm{X \to Y、\ W \to Z})$ の共有点を持つ経路の組合せから $(\mathrm{X \to Z、\ W \to Y})$ の（無条件の）経路の組合せを対応させる操作を、 操作 $1$ と名付けておきましょう。

逆に、 $\mathrm{X}$ から $\mathrm{Z}$ に至る最短経路 $r$（右図の赤線） と $\mathrm{W}$ から $\mathrm{Y}$ に至る最短経路 $s$（右図の青線） が与えられたとしましょう。この場合、位置関係から考えて $2$ つの経路は必ず共通点を待つことがわかります。やはり初めて出会う点を $\mathrm{C}$ とおきます。

　$\mathrm{R}$ さんが地図 $r$ に従って、 $\mathrm{X}$ から $\mathrm{Z}$ に移動し $\mathrm{S}$ さんが地図 $s$ に従って $\mathrm{W}$ から $\mathrm{Y}$ に移動するのですが、 点 $\mathrm{C}$ で地図を交換すると、 $\mathrm{R}$ さんは $\mathrm{X}$ から $\mathrm{Y}$ への最短経路 $p$ を動き、$\mathrm{S}$ さんは $\mathrm{W}$ から $\mathrm{Z}$ への最短経路 $q$ を動きます。そしてその $2$ つの経路はもちろん共通の点を通るのです。
　この手順によって、 $(\mathrm{X \to Z、W \to Y})$ の（無条件の）経路の組合せから $(\mathrm{X \to Y、W \to Z})$ の共有点を持つ経路の組合せを対応させる操作を、操作 $2$ と名付けておきましょう。

　明らかに、操作1と操作2は逆操作になっています。つまり $(\mathrm{X \to Y、W \to Z})$ の共有点を持つ経路の組合せに操作1を施し、それによって得られた $(\mathrm{X \to Z、W \to Y})$ の経路の組合せに操作 $2$ を施すと、元の経路に戻ります。
　また、$(\mathrm{X \to Z、W \to Y})$ の（無条件の）経路の組合せに操作 $2$ を施し、それによって得られた $(\mathrm{X \to Y、W \to Z})$ の共有点を持つ経路の組合せに操作 $1$ を施すと、やはり元の経路に戻ります。

　これら $2$ つの操作によって、$(\mathrm{X \to Y、W \to Z})$ の経路の組合せのうちの共有点を持つものと、$(\mathrm{X \to Z、W \to Y})$ の経路の（無条件の）組合せが完全に対応付けられることがわかるでしょう。つまり同数存在するわけです。

　以上によって問題は完全に解決しました。挑戦問題、つまり街路図が $3\times 3$ でなく $6\times 6$ であった場合も、 この考え方により反時計回りの非交差経路 $\mathrm{A \to X \to Y \to B \to Z \to W \to A}$ の総数は、

時計回りの非交差経路も同数ありますから、挑戦問題の答は $19404\times 2=38808$ です。場合分けや数え上げではちょっとできそうにありませんね。数学的発想の勝利といえるのではないでしょうか。

補遺：カタラン数の計算方法を知っている方は、この方法との類似性に気付くと思います。この考え方のその先を数学的にもっと深く知りたい方は、「LGV 公式」でネットを検索してみるといいでしょう。

医学部進学予備校メビオ 数学科 講師 亀井