カタラン数を鏡像法で理解する

概要

この記事の内容は [1] の解説の一部を抜き出して説明したものです。 カタラン数 が と等しいことを、鏡像法 *1 で説明します。

本文

は、グリッド上を右上方向に、 から まで、 を満たすように移動する方法の数と一致します。

の条件を一旦忘れて、 から までの経路の本数を数えることを考えます。 これは以下のような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

を、 を通らない、と言い換えます。 するとカタラン数は、先ほどの例において 上で にするような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr 0 &\quad ( i + 1 = j ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

この 上で にする操作を陽に行わずに表現する方法として、 に対して と対称な位置に の重みをもつスタート地点を置くという方法があります。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr -1 &\quad ( (i, j) = (-1, 1) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

対称性から、対称軸上では となることが分かるので、普通の経路数の動的計画法の更新式で、上手くカタラン数が求まっています。 一方で を始点とする経路の数と を始点とする経路の数は独立ですから、単に足し合わせれば

\begin{align} \text{カタラン数} &= \lbrace (0, 0) \text{から} (N, N) \text{への経路の数} \rbrace + (-1) \cdot \lbrace (-1, 1) \text{から} (N, N) \text{への経路の数} \rbrace \cr C(N) &= \binom{2N}{N} - \binom{2N}{N-1} \end{align}

が従います。

参考文献

• [1]

  ネタバレ注意

  yukicoder 1241 Eternal Tours

*1:鏡像法は物理学の用語のようですが、発想が非常に似ているので、名前を借りています。