トーナメントの総数とカタラン数と円周率

カタラン数 (Catalan number) とは整数 $n \geq 0$ に対して定まる自然数 $C_n$ で、以下の式で定まるものです。

$$C_0 = 1, \quad C_n = \sum_{k = 1}^n C_{k-1} C_{n-k}$$

これを使って円周率を求める方法を紹介したのが以下の動画です。

この動画のまとめと補足を行います。この記事では基本的に図を描かないので、図が必要な場合は動画を見てください。

カタラン数

冒頭でも述べましたが、カタラン数とは

$$C_0 = 1, \quad C_n = \sum_{k = 1}^n C_{k-1} C_{n-k}$$

で定められる数のことです。カタラン数の性質について簡単にまとめます。

トーナメントの総数とカタラン数

$n$ 人のトーナメントの (あるルールのもとでの) 組み方の総数がカタラン数 $C_{n-1}$ に一致することを説明します。図があった方がわかりやすいですが、図を書くのが面倒なので全て言葉のみで記述します。図が欲しい場合は動画を見てください

トーナメントの組み方、数え方のルール

トーナメントの組み方、数え方は

  1. 不釣り合いなトーナメントも許す
  2. 左から順番に $1, 2, \cdots n$ と番号付け、当たり方が異なれば異なるトーナメントとみなす
  3. 数を跨いでトーナメントを組むことは禁止する

という条件のもとで考えることとします。

(3) については、例えば $n = 4$ のとき、普通は $1$ と $2$ が対戦し、$3$ と $4$ が対戦し、それぞれの勝者が対戦する、というトーナメントになりますが、それだけではなく、例えば $1$ と $2$ が対戦し、その勝者と $3$ が対戦し、その勝者と $4$ が対戦する、という不釣り合いなトーナメントも数えるということです。

(2) については、例えば $n = 3$ のとき、$1$ と $2$ が対戦しその勝者と $3$ が対戦するトーナメントと、$2$ と $3$ 対戦しその勝者と $1$ が対戦するトーナメントは、数字を無視して左右をひっくり返せば形が一致しますが、対戦の当たり方が異なるので別のトーナメントとみなします。

(1) については、例えば $n = 3$ のとき、一回戦は $1$ 対 $2$ または $2$ 対 $3$ のいずれがありうるが、$1$ 対 $3$ が一回戦で行われることはないということです。

トーナメントの総数とカタラン数

まず、$1$ 人のトーナメントの数は $1$ 個なので $C_0 = 1$ と一致します。$n \geq 2$ のとき、$n-1$ までは正しいとして帰納法で証明します。$n$ 人のトーナメントを一番上の分岐で二つに分けると、片方は $k$ 人のトーナメント $(k \geq 1)$、もう片方は $n -k$ 人のトーナメント $(n -k \geq 1)$ になります。従って $n$ 人のトーナメントの総数は

$$\sum_{k = 1}^{n-1} C_{k-1} C_{n-k-1} = C_{n-1}$$

となり、トーナメントの総数がカタラン数に一致することがわかりました。

カタラン数と二項係数

カタラン数 $C_n$ は二項係数 $\binom{2n}{n}$ を用いて

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

と表すことができます。これを示しましょう。

$n$ 人のトーナメントの縦線は $2n -1$ 個あります。これは選手が $n$ 人いて、対戦が $n-1$ 回行われることからわかります。縦線のどれか一つに右か左の印をつけたものを、左右印付きトーナメントと呼びます。左右印付きトーナメントは、$C_{n-1}$ を $2 (2n-1)$ 倍した数存在します。一方、トーナメントの選手に印をつけたものを選手印つきトーナメントと呼びます。選手は $n$ 人いるので、選手印つきトーナメントの数は $n C_{n-1}$ 個存在します。

$n$ 人の左右印付きトーナメントを、印がついた縦線から、左右どちらかに印の通りに選手を追加し (番号は適当にシフトする)、その選手に印をつけると $n+1$ 人の選手印付きトーナメントが得られます。逆に $n+1$ 人の選手印付きトーナメントに対して、その選手を棄権させ、適当な部分の縦線に、棄権させた選手が右にいたなら右、左にいたなら左と印をつけると、$n$ 人の左右印付きトーナメントが得られます。この対応は互いに逆になっています。

よって、$n$ 人の左右印付きトーナメントの集合と、$n+1$ 人の選手印付きトーナメントの集合の間に全単射が存在し

\begin{align} (n+1) C_{n} &= 2 (2n-1) C_{n-1} \\ C_{n} &= \frac{2 (2n-1)}{n+1} C_{n-1} \\ &= \frac{2^n (2n-1)!!}{(n+1)!} \\ &= \frac{(2n)!}{(n+1)!n!} \\ &= \frac{1}{n+1} \binom{2n}{n} \end{align}

が成り立ちます。

母関数

$n$ 次の項が $C_n$ である冪級数

$$g(x) = \sum_{n=0}^{\infty} C_n x^n$$

をカタラン数 $C_n$ の母関数といいます。

\begin{align} \frac{C_{n+1}}{C_n} &= \frac{n+1}{n+2} \frac{(2n+2)!}{(n+1)!^2} \frac{n!^2}{(2n)!} \\ &= \frac{(2n+1)(2n+2)}{(n+1)(n+2)} \\ &= 2\left(2 -\frac{3}{n+2}\right) \\ & \to 4 \quad (n \to \infty) \end{align}

なので、ダランベールの判定法から収束半径は $\frac{1}{4}$、つまり $|x| < \frac{1}{4}$ で $g(x)$ は収束します。

母関数が満たす関数方程式

ここで

$$C_n x^n = x\sum_{k = 1}^n (C_{k-1}x^{k-1}) (C_{n-k} x^{n-k})$$

なので、

\begin{align} \sum_{n =1}^{\infty}C_n x^n &= x \sum_{n =1}^{\infty}\sum_{k = 1}^{n} (C_{k-1}x^{k-1}) (C_{n-k} x^{n-k})\\ &= x \sum_{n =1}^{\infty}\sum_{k = 0}^{n-1} (C_{k}x^{k}) (C_{n-k-1} x^{n-k-1})\\ &= x \sum_{n =0}^{\infty}\sum_{k = 0}^{n} (C_{k}x^{k}) (C_{n-k} x^{n-k})\\ &= x C(x)^2 \end{align}

となります。従って

$$g(x) -1 = x g(x)^2$$

が成り立ちます。$g(x)$ について解くと

\begin{align} g(x) &= \frac{1 \pm \sqrt{1 -4x}}{2x} \\ &= \frac{1 -(1-4x)}{2x (1 \mp \sqrt{1 -4x}} \\ &= \frac{2}{1 \mp \sqrt{1 -4x}} \end{align}

となりますが、$g(0) = C_0 = 1$ であることから

$$g(x) = \frac{1 -\sqrt{1 -4x}}{2x}$$

であることがわかります。

母関数を用いたカタラン数と二項係数の関係の証明

母関数 $g(x)$ を再びテイラー展開します。一般二項定理から

$$\sqrt{1 -4x} = \sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n}(-4)^n x^n$$

が成り立ちます。ここで $\binom{\frac{1}{2}}{n}$ は、$n=0$ のときは $1$、$n \geq 1$ のときは

$$\binom{\frac{1}{2}}{n} = \frac{\frac{1}{2} (\frac{1}{2}-1) \cdots (\frac{1}{2} -n +1)}{n!}$$

を意味します。よって

\begin{align} g(x) &= \frac{1}{2x} \left(1 -\sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n}(-4)^n x^n \right) \\ &= -\frac{1}{2}\sum_{n=1}^{\infty} \binom{\frac{1}{2}}{n}(-4)^n x^{n-1} \\ &= -\frac{1}{2}\sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n+1}(-4)^{n+1} x^{n} \end{align}

となります。特に

\begin{align} C_n &= -\frac{1}{2}\binom{\frac{1}{2}}{n+1}(-4)^{n+1} \\ &= -\frac{1}{2}\frac{\frac{1}{2} (\frac{1}{2}-1) \cdots (\frac{1}{2} -n)}{(n+1)!}(-4)^{n+1} \\ &= \frac{(1-\frac{1}{2}) \cdots (n-\frac{1}{2})}{(n+1)!} 4^{n} \\ & = \frac{(2n-1)!!}{(n+1)!} 2^n \\ & = \frac{(2n)!}{(2n)!!} \frac{1}{n!(n+1)} 2^n \\ & = \frac{1}{n+1}\frac{(2n)!}{n!n!} \\ &= \frac{1}{n+1} \binom{2n}{n} \end{align}

となります。

カタラン数と円周率

カタラン数 $C_n$ に対して以下の極限が成り立ちます。

$$\pi = \lim_{n\to\infty} \frac{16^n}{n^3 C_n^2}$$

これを示しましょう。

ウォリスの公式

証明にはウォリスの公式を用いるので、ウォリスの公式について簡単に説明します。詳しくは以下の動画で解説しているので、気になる方はこちらをご覧ください。

まず、$\sin^n x$ または $\cos^n x$ の積分

$$I_n = \int_{0}^{\frac{\pi}{2}} \sin^n x dx = \int_{0}^{\frac{\pi}{2}} \cos^n x dx$$

を考えます。後ろの等式は $\sin x$ と $\cos x$ の対称性

$$\sin x = \cos \left(\frac{\pi}{2} -x\right)$$

を使って、適当に変数変換すればわかります (動画では $\cos x$ の積分を考えています)。

部分積分により

$$I_{n} = \frac{n-1}{n}I_{n-2} \quad (n \geq 2)$$

がわかり、$I_0 = \frac{\pi}{2}$, $I_1 = 1$ から $I_n$ が求まります。$\sin^{n+1} x \leq \sin^n x$ から $I_{2n+2} \leq I_{2n+1} \leq I_{2n}$ なので

\begin{gather} \frac{(2n+1)!!}{(2n+2)!!}\frac{\pi}{2} \leq \frac{(2n)!!}{(2n+1)!!} \leq \frac{(2n-1)!!}{(2n)!!}\frac{\pi}{2} \\ \frac{2n+1}{2n+2}\frac{\pi}{2} \leq \frac{(2n)!!^2}{(2n-1)!!(2n +1)!!} \leq \frac{\pi}{2} \end{gather}

が成り立ち、極限を取ると

$$\lim_{n \to \infty} \frac{(2n)!!^2}{(2n-1)!!(2n +1)!!} = \frac{\pi}{2}$$

となります。これがウォリスの公式です。

また

$$W_n =\frac{(2n)!!^2}{(2n-1)!!(2n +1)!!} $$

とおくと、$I_{2n+1} \leq I_{2n} \leq I_{2n-1}$ から

\begin{gather} \frac{(2n)!!}{(2n+1)!!} \leq \frac{(2n-1)!!}{(2n)!!}\frac{\pi}{2} \leq \frac{(2n-2)!!}{(2n-1)!!} \\ 2W_n \leq \pi \leq \left(\frac{2n+1}{n}\right) W_n \end{gather}

がわかり、$W_n$ を計算することで円周率が計算できます。

円周率の計算方法

先ほど、カタラン数 $C_n$ は

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

を満たすことを示しました。これとウォリスの公式を用いて円周率の計算方法を紹介します。

\begin{align} \frac{1}{n+1} \binom{2n}{n} &= \frac{1}{n+1} \frac{(2n)!}{n! n!}\\ &= \frac{1}{n+1} \frac{(2n-1)!! (2n)!!}{n! n!} \\ &= \frac{1}{n+1} \frac{(2n-1)!! (2^n n!)}{n! n!} \\ &= \frac{4^{n}}{n+1} \frac{(2n-1)!!}{(2n)!!} \\ &= \frac{4^{n}}{n+1} \sqrt{\frac{1}{\frac{(2n)!!^2}{(2n-1)!!^2 (2n+1)}(2n+1)}} \\ &= \frac{4^{n}}{(n+1)\sqrt{2n+1}} \frac{1}{\sqrt{W_n}} \end{align}

なので、

$$C_n = \frac{4^{n}}{(n+1)\sqrt{2n+1}} \frac{1}{\sqrt{W_n}}$$

が成り立ちます。$W_n$ について整理すると

$$W_n = \frac{16^n}{(n+1)^2(2n+1)C_n^2}$$

となり、極限を取ると

\begin{align} \pi &= \lim_{n\to\infty} 2 \frac{16^n}{(n+1)^2(2n+1)C_n^2}\\ &= \lim_{n\to\infty} \frac{16^n}{n^3C_n^2} \end{align}

また、円周率を正確に求めたいならば

$$2W_n \leq \pi \leq \left(\frac{2n+1}{n}\right) W_n$$

から

\begin{align} \frac{2 \cdot 16^n}{(n+1)^2(2n+1)C_n^2} \leq \pi &\leq \frac{2n+1}{n} \frac{16^n}{(n+1)^2(2n+1)C_n^2} \\ &= \frac{16^n}{n(n+1)^2C_n^2} \end{align}

となるので、これで $C_n$ から円周率を計算することができます。分母が複雑なので、$\frac{2}{2n+1} > \frac{1}{n+1}$, $\frac{1}{n + 1} < \frac{1}{n}$ を用いて

$$\frac{16^n}{(n+1)^3C_n^2} \leq \pi \leq \frac{16^n}{n^3C_n^2}$$

とすると少しすっきりします。

カタラン数が現れる例

トーナメント以外にもカタラン数が現れる例をいくつか紹介します。

括弧の付け方

記号の列

$$a_1a_2 \cdots a_n$$

に $()$ をつける付け方の総数は $n \geq 3$ で $C_{n-1}$ になります。$n = 3$ のときは

$$(a_1 a_2) a_3, \ a_1 (a_2 a_3)$$

の二つで、$C_2 = 2$ なので一致します。$n = 4$ のときは

$$((a_1 a_2) a_3) a_4, \ (a_1 (a_2 a_3)) a_4, \ (a_1 a_2) (a_3 a_4), \ a_1 ((a_2 a_3) a_4), \ a_1 (a_2 (a_3 a_4))$$

の 5 つです。一番小さい括弧からペアにしていくとトーナメントが出来上がります。

凸多角形の三角形分割

凸 $n+2$ 角形の頂点を適当に番号付け、異なる頂点同士を結んだ対角線が交わらないように凸多角形を三角形分割することを考えます。隣り合う頂点は結ばないこととします。この分割の仕方の数が $n \geq 2$ のときに $C_n$ に一致します。ただし、結んだ頂点のペアの集合が等しい時に三角形分割が等しいとします。特に回転して一致するものは別の分割と数えます。

$n = 2$ のとき、四角形の頂点に $1 \sim 4$ の番号をつけると、対角線の引き方は

$$\{\{1, 3\}\}, \ \{\{2, 4\}\}$$

の $2$ 通りなので $C_2$ に一致します。五角形の場合は対角線を 2 つ引け、ある 1 つの頂点から 2 つの対角線が引かれるので

\begin{align} & \{\{1, 3\}, \{1, 4\}\}, \ \{\{2, 4\}, \{2, 5\}\}, \ \{\{1, 3\}, \{3, 5\}\} \\ & \{\{1, 4\}, \{2, 4\}\}, \ \{\{2, 5\}, \{3, 5\}\} \end{align}

の $5$ 通りで $C_3$ に一致します。

$n+2$ 角形の三角形分割の数を $T_n$ とおき、$n+2$ 角形の頂点を $a_1, a_2, \cdots, a_{n+2}$ とします。任意の三角形分割に対して、底辺を $a_{n+1} a_{n+2}$ とする三角形はただ一つ存在します。その頂点を $a_k$ とおくと、$1 < k < n$ のとき $n+2$ 角形はその三角形を除いて $k +1$ 角形と $n-k+2$ 角形に分かれ、$k = 1, n$ のときは $n + 1$ 角形が残ります。$T_0 = T_1 = 1$ とおけば、

$$T_n = 2T_{n-1} + \sum_{k = 2}^{n-1} T_{k-1} T_{n-k} = \sum_{k = 1}^{n}T_{k-1} T_{n-k}$$

となり、カタラン数と一致します。

格子点を辿る最短経路の数え上げ

xy平面上の格子点を辿る経路で、$(0, 0)$ を始点、$(n, n)$ を終点とするものを考えます。最短で、$x \geq y$ の部分のみを通る経路の数がカタラン数と一致します。経路の数を $p_n$ とおくと、$p_1 = 1 = C_1$ となります。始点 $(0, 0)$ と終点 $(n, n)$ 以外で対角線と交わらない $(x > y)$ 経路の数は、$(1, 0)$ から $(n, n-1)$ までの $x + 1 \geq y$ を満たす経路の数と同じなので $p_{n-1}$ であり、$p_n$ を最初に対角線と交わる点 $(k, k)$ で分類すると、$(k, k)$ までは $p_{k-1}$, そこからは $p_{n-k}$ パターンあるので、$p_0 = 1$ とすれば

$$p_n = p_{n-1} +\sum_{k =1}^{n-1} p_{k-1} p_{n-k} = \sum_{k =1}^{n} p_{k-1} p_{n-k}$$

なので $p_n = C_n$ となります。

ちなみに、単なる最短経路の数は、$n$ 個の ↑ と $n$ 個の → の並べ方と一致するので

$$\frac{(2n)!}{n! n!} = \binom{2n}{n}$$

に一致します。少なくとも 1 回対角線より上にいく経路の数は、最初に対角線を超えた点以降を $y = x+1$ を中心に反転させることで、$(0,0)$ から $(n -1, n+1)$ に向かう最短経路と 1 対 1 に対応するので

\begin{align} C_n &= \frac{(2n)!}{n! n!} -\frac{(2n)!}{(n-1)! (n+1)!} \\ &= \left(1 -\frac{n}{n+1}\right)\frac{(2n)!}{n! n!} \\ &= \frac{1}{n+1} \binom{2n}{n} \end{align}

となります。

$1$ 次元ランダムウォーク

原点を出発点として、1 秒ごとに正の方向に確率 $p$ で進み、負方向に $1 -p$ で進むランダムウォークを考えます。$2n$ 秒後に初めて原点に戻る戻り方は、格子点を辿る $(0,0)$ から $(n, n)$ までの最短経路のうち、対角線に触れないものの数と同じで、これは $2C_{n-1}$ なので (対角線の上を通るのと下を通るので 2 倍)、$2n$ 秒後に初めて原点に戻る確率は

$$2C_{n-1}p^n(1 -p)^n$$

で与えられます。よって $2N$ 秒後までに少なくとも一度原点に戻る確率は

$$P(N) = \sum_{n = 1}^N 2C_{n-1}p^n(1 -p)^n$$

であり、母関数を用いると

\begin{align} \lim_{N \to \infty}P(N) &= \sum_{n = 1}^{\infty} 2C_{n-1}p^n(1 -p)^n \\ &= 2p(1-p) \sum_{n = 0}^{\infty} C_{n}p^n(1 -p)^n \\ &= 2p(1-p) \frac{1 -\sqrt{1 -4p(1-p)}}{2 p(1-p)} \\ &= 1 -\sqrt{(1 -2p)^2} \\ &= 1 -|1 -2p| \\ \end{align}

となることがわかります。

参考文献

[Wiki] wikipedia (en). Catalan number.

[大島] 大島利雄 Japanese Theorem とカタラン数.


ご支援のお願い

記事を読んで、「支援してもいいよ」と思っていただけましたら、ご支援いただけると幸いです。サーバー維持費などに充てさせていただきます。登録不要で、100円から寄付でき、金額の90%がクリエイターに届きます。

支援する (100円~)


シェアする