対角線を越えない道だけを数えると……カタラン数が現れる

$4\times 4$ の格子を最短で進む道は 70 本。そのうち対角線を越えないものは 14 本だけです。

この 14 という数には名前が付いています。カタラン数といい、括弧の対応や多角形の分割など、まったく別の見た目の問題にも同じ数が現れる^[1]。

条件を式にする

出発点を原点、目的地を $(n,n)$ とします。右へ 1 進むと $x$ が 1 増え、上へ 1 進むと $y$ が 1 増える。

「対角線を越えない」とは、途中のどの点でも $y\le x$ が成り立つということ。上に進みすぎてはいけない、という条件です。

言いかえると、どの時点でも上に進んだ回数が右に進んだ回数を超えない。

悪い道を数えて引く

条件を満たす道を正面から数えるのは大変です。そこで、条件を破る道のほうを数えます。

破る道は、どこかで $y=x+1$ の線に届いています。はじめて届いた点に注目する。

その点から先の道を、$y=x+1$ の線について折り返します。右と上を入れかえる操作にあたる。

折り返した道は、$(4,4)$ ではなく $(3,5)$ に着きます。逆に $(3,5)$ への道はすべて $y=x+1$ の線に届くので、折り返せば悪い道に戻る。

悪い道と $(3,5)$ への道が 1 対 1 に対応しました。この対応を反射法といいます^[1]。

引き算で式にする

$(n,n)$ への道は ${}_{2n}{\mathrm{C}}_n$ 本。悪い道は $(n-1,n+1)$ への道と同じ数なので ${}_{2n}{\mathrm{C}}_{n+1}$ 本です。

$$C_n={}_{2n}{\mathrm{C}}_n-{}_{2n}{\mathrm{C}}_{n+1}$$

$n=4$ なら ${}_8{\mathrm{C}}_4-{}_8{\mathrm{C}}_5=70-56=14$。整理すると次の形にもなります^[2]。

$$C_n=\frac{1}{n+1}{}_{2n}{\mathrm{C}}_n$$

$\frac{70}{5}=14$ で、同じ値です。

小さい場合で確かめる

$n=2$ で書き出します。$2\times 2$ の格子で全体は 6 本。

対角線を越えないのは、右右上上と右上右上の 2 本。式でも ${}_4{\mathrm{C}}_2-{}_4{\mathrm{C}}_3=6-4=2$ で合いました。

$n=3$ なら 5 本。$20-15=5$ です。書き出せる大きさで一度確かめておくと、式を信用できます。

例：括弧の対応

$n$ 組の括弧を、開きと閉じが正しく対応するように並べる並べ方も $C_n$ 通りです^[2]。

3 組なら $((()))$、$(()())$、$(())()$、$()(())$、$()()()$ の 5 通り。

開き括弧を右へ進む、閉じ括弧を上へ進むと読み替えると、格子の道になります。どの時点でも閉じの数が開きの数を超えない、という条件が $y\le x$ にあたる。

例：おつりの問題

500 円の切符を売る窓口に、500 円玉だけを持つ人が 4 人、1000 円札だけを持つ人が 4 人、合わせて 8 人が並びます。

おつり用の 500 円玉は最初 0 枚。1000 円札の人には 500 円玉を 1 枚返すので、その時点で手元に 500 円玉がなければ困ります。

どの時点でも 500 円玉の人の数が 1000 円札の人の数以上、という条件です。並び方は 14 通り。

格子の道とまったく同じ条件になっています。

例：多角形を三角形に分ける

凸多角形を、交わらない対角線で三角形に分ける分け方の総数も、カタラン数になります^[2]。

五角形なら 5 通り、六角形なら 14 通り。$n+2$ 角形の分け方が $C_n$ 通りです。

五角形は手で描けます。5 つの頂点それぞれから 2 本の対角線を引く形で、ちょうど 5 通りに分かれる。

例：投票の問題

候補 A が 5 票、候補 B が 4 票を得たとします。開票の途中で A の得票が B を下回らない開き方は何通りか。

これも同じ形の問題です。A を右、B を上と読めば、どの時点でも $y\le x$ という条件になる。

$C_4=14$ 通りです。この形は投票の問題として古くから知られています^[1]。

例：対角線に触れてもよいかどうか

$y\le x$ なら対角線の上を通ってよく、答えは $C_n$ です。

$y<x$ を最初から最後まで求めると、出発点と目的地が対角線上にあるので、そもそも成り立ちません。

条件が付くのは途中の点だけ、という読み方をします。出発点と目的地は数えない。

高校での扱い

カタラン数という名前は、教科書には出てきません。ただ、反射法で悪い道を数える手順は入試で問われます。

覚えるべきは名前ではなく、次の 2 点です。悪い道を折り返すと行き先が 1 つずれること。そして、ずれた先への道と 1 対 1 に対応すること。

この 2 点さえ出せれば、$n$ がいくつでも答えが書けます。

よくある誤り

悪い道を折り返して、行き先のずれた経路に置きかえる。この 1 手で、難しく見えた条件が引き算に変わります。

参考文献

^[1] が反射法と投票の問題、^[2] が公式と括弧や多角形の分割との対応、^[3] が格子の上の経路、^[4] と ^[5] が組合せと順列の公式です。