あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

括弧をカッコよく数えよう!

前回の話を踏まえて、今回は場合の数の数え上げを扱います。この種の問題の基本形は、ある条件が与えられたとき、それを満たす対象が全部でいくつあるかを数えよ、というものです。

最初に用語を紹介しておくと、今回紹介する数え上げの手法は、「母関数(generating function)」の方法と呼ばれています。それは、母関数という関数と微分積分を使うことによって数列の一般項を計算するという、一見するとかなり奇妙な方法です。そもそも離散的な数え上げに連続的な微分積分を使うということ自体、最初はちょっと想像がつかないでしょう。しかし、それによっていかにも手が出せないような数列の一般項を求めることができたりするのです。今回の例は初歩的なものですが、離散数学の奥深さに少しでも触れていただければと思います。

問題

今回取り上げる問題とは、次のようなものです。n+1 個の数が n 個の二項演算(例えば四則演算)で結ばれた式を考えます。具体的には、

1 + 2 - 3 \times 4\times 5 / 6 この場合 n = 5

のようなものです。このとき、式の計算順序の意味で異なる括弧の付け方は全部で何通りあるでしょうか?別の言い方をすれば、あらゆる括弧の付け方を考えるとき、式の計算順序は全部で何通りあるでしょうか。

例えば、上の式の場合は、先に乗除算をやって、続いて加減算をやると小学校で習ったはずです。また、式の値には影響しませんが、普通は左から右に計算を進めると思います。*1この順番を括弧で表すと、

( (1+2)-(((3\times 4)\times 5)/6))

となります。そして、異なる括弧の付け方を採用すれば、もちろん一般には計算順序が変わります。例えば、

( ( ( ( (1+2)-3)\times 4)\times 5)/6)

という括弧の付け方は、左から順番に計算することを意味します。一方で、異なる括弧の付け方でも同じ計算順序となる場合もあります。例えば、

1+2-(3\times 4\times 5)/6

は普通の計算順序となります。しかし、よくよく見れば、これは計算順序を完全に表すだけの括弧が足りてないだけで、ここから出発して括弧を付け加えていけば、先と同じ式

( (1+2)-(((3\times 4)\times 5)/6))

を得ることができます。これ以上括弧をつけ加えると必ず余計な括弧、例えば ( (1+2))、ができてしまうため、ここで打ち止めとします。少し考えれば、過不足なく括弧がつけられた式において、1つの括弧の組は、ちょうど1つの裸の(他の括弧に覆われていない)演算子を覆うことが解るでしょう。逆に、そのような式には、いかなる方法で括弧をつけても余計になってしまいます。すなわち、括弧が覆うべき裸の演算子が存在しないため、新たにつけ加えた括弧内に存在する裸の演算子が0個になってしまうのです。

極大括弧式

以上の例から、1つの括弧の組がちょうど1つの裸の(他の括弧に覆われていない)演算子を覆うとき、式の計算順序は括弧によって完全に表されます。このような式を「極大括弧式」と呼ぶことにしましょう。ここで言う「極大」とは、既に過不足なく括弧がつけられていて、それ以上は蛇足になるという意味です。

記号的に1つの括弧の組がちょうど1つの裸の演算子を覆うということを表すと、極大括弧式に現れる括弧は (\hat{A} + \hat{B}) の形(演算子は任意)のもので、オペランド \hat{A} および \hat{B} は一つの数かあるいは括弧で覆われた式となります。また、もし \hat{A} または \hat{B} が括弧で覆われた式であるならば、それ自体もまた極大括弧式です。もしそうでないならば、その内側で括弧が不足するためです。これを定義的に表すと、次のようになります。便宜上、単独の数も極大括弧式とします。

[極大括弧式] とは ( [極大括弧式] [演算子] [極大括弧式] ) という形式の列、および、一つの [数] である。

[演算子]には例えば四則演算の記号 +, -, \times, / が、[数]には簡単のため非負整数が入るとします。*2

与えられた式に対して、それから作られる極大括弧式と計算順序とが1対1で対応することから、この問題で数えるべきものは、与えられた数と演算子の並びから作り得る極大括弧式の数ということになります。すなわち、問題は次のように言い換えられます。

問題: n+1 個の非負整数が n 個の二項演算(例えば四則演算)で結ばれた式を考える。このとき、与式に括弧を足して作り得る極大括弧式は何通り存在するか?

少し考えれば、数えるべき場合の数は演算子の個数 n だけに依存することが分かります。そこで、以後では演算は + だけに固定し、それに括弧を足して作られる極大括弧式の総数を C_n で表すことにします。つまり問題は

問題: C_n の一般項を求めよ。

となります。

n = 0, 1 については

C_0 = C_1 = 1

であることが分かります。なぜなら、

1 に対しては 1 そのものだけが極大括弧式であり、

1+2 に対しては (1+2) だけが極大括弧式であるからです。

C_2 については、

( (1+2)+3)(1+(2+3))

だけが極大括弧式となることが解るので、C_2 = 2 です。

それでは一般の n についてはどうなるでしょうか?というのが問題です。

さて、この問題をなぜ取り上げたかというと、カッコいい(かどうかは個人の主観によりますが、筆者はそう思っています)数え上げの手法を紹介するためです。(ダジャレという説もあります。)また、この問題は、実質的には二分順序木の数え上げそのものであり、凸多角形の三角形分割の数え上げのような様々な問題を含むという意味で、応用上も重要な例となっています。

漸化式を作る

数列 C_n を求めるためには、漸化式を作ると良さそうです。というのも、極大括弧式は必ず (\hat{A} + \hat{B}) の形であり、\hat{A} および \hat{B} もまた極大括弧式であるという、再帰的な構造を持つためです。ここでは、C_{n+1}C_0, C_1, \dots,C_n を用いて表すことを考えます。

漸化式を求めるにはより小さい部分問題に落とせばいいので、まずは与えられた式(この時点では括弧がついていない)を A+B と分解してみます。ただし、式全体は n+1 個の+を含むとします。このとき、AB の部分には合わせて n 個の+があることに注意してください。引かれている1個は AB の間のものです。ここで、k=0,1,\dots,n について、A の部分の式が演算子k 個含んでいる(k=0 の場合は単独の数)します。k=0,1,\dots,n と変化させれば、すべての場合を尽くすことができることは明らかでしょう。

最初に、k を1つ決めたときの極大括弧式の総数を求めます。まず、A の中での極大括弧式の作り方は C_k 通りあります。一方、B の部分の式は残りの n-k 個の演算子を含んでいることが確定しますので、B の中での極大括弧式の作り方は C_{n-k} 通りあります。さて、AB のそれぞれの部分で作られた極大括弧式が \hat{A}\hat{B} であったならば、全体の極大括弧式は (\hat{A}+\hat{B}) と1つに確定します。AB で極大括弧式は独立に作られるので、それらの場合の数を掛けあわせれば、k を1つ決めたときの全体の極大括弧式の総数が C_k C_{n-k} 通りと求まります。

次に、異なる k について、同じ極大括弧式が出てくることがない(つまり k に関して排反である)ことを見ましょう。極大括弧式 (\hat{A} + \hat{B}) の外側の括弧を一旦外して \hat{A} + \hat{B} とします。このとき、k+1 番目の演算子は裸になっています。一方、\hat{A}\hat{B} は必ず外側が括弧で覆われているので、裸の演算子はその中にはありません。よって、裸の演算子の場所と k とが1対1に対応するので、異なる k に対して \hat{A} + \hat{B} が同じ形になることはありません。従って、極大括弧式もまた、異なる k に対して同じになることはありません。

以上から、極大括弧式の総数は、k について和をとって

\displaystyle C_{n+1} = \sum_{k=0}^n C_k C_{n-k}

となります。これが求める漸化式です。C_{n+1}C_0, \dots, C_n によって決まるので、C_0 = 1 が与えられれば任意の n \geq 1 に関する C_n の値が決まります。例えば、

C_1 = C_0 \times C_0 = 1\times 1 = 1
C_2 = C_0 \times C_1 + C_1 \times C_0 = 1 \times 1 + 1 \times 1 = 2

で、先に求めた値と一致しています。

後はこれから一般項を求めればいいのですが…ちょっとそうそう簡単には求まりそうにない形をしていますね。これを解決する方法こそが今回の主題である母関数の方法なのです。

母関数の方法

母関数は一種の便法なので、細かいことは考えずに天下り的に定義を与えてしまいましょう。

定義:数列 \{ a_n \}_{n=0}^{\infty} に対して、「母関数」とは、

\displaystyle G(z) := \sum_{n=0}^{\infty} a_n z^n

で定義される形式的べき級数である。

形式的べき級数

「形式的」べき級数というのは、べき級数の収束を一切考慮しないという意味で形式的なものです。形式的べき級数には形式的な和と積の演算が入ります。

定義:形式的べき級数 \displaystyle A(x) = \sum_{n=0}^{\infty} a_n x^n\displaystyle B(x) = \sum_{n=0}^{\infty} b_n x^n に関して、それらの和と積は次で定義される。

\displaystyle (A+B)(x) = \sum_{n=0}^{\infty} (a_n + b_n) x^n
\displaystyle (AB)(x) = \sum_{n=0}^{\infty} \left( \sum_{k=0}^n a_k b_{n-k} \right) x^n

積が少し解りにくいですが、k=0,1,\dots,n について x^nx^kx^{n-k} の積であることを考えれば、それをすべての k について足すことで係数が出ます。

さらに、\displaystyle (-A)(x) := \sum_{n=0}^{\infty} (-a_n) x^n とすれば差も定義されます。

このように、形式的べき級数には足し算、引き算、掛け算の3つの演算が入ります。*3一方で、商は一般には定義されません。ただし、a_0 \neq 0 の場合には、逆数を

\displaystyle A^{-1}(x) = \frac{1}{a_0} \frac{1}{1 - (1 - A(x) / a_0)}= \sum_{k=0}^{\infty} \frac{(1 - A(x) / a_0)^k}{a_0}

によって定義することができるので、これによる割り算を考えることができます。上の式は級数展開

\displaystyle \frac{1}{1-x} = \sum_{k=0}^{\infty} x^k

を形式的に用いて得られたものです。

もう一つ重要な演算は、形式的な微分積分です。これは普通の級数の項別微分積分と同じものですが、例によって収束性は考慮しません。今回は微分だけを扱うので、それだけ定義しておきます。

定義: 形式的べき級数 \displaystyle A(x) = \sum_{n=0}^{\infty} a_n x^n に関して、その微分は次で定義される。

\displaystyle A'(x) = \sum_{n=1}^{\infty} n a_n x^{n-1}

ここで、A'(x) の定数項の係数は a_1 であることに注目します。すなわち、

a_1 = A'(0)

です。他の項は0を代入したことによって消えます。

一般に、A(x)n 次の微分 A^{(n)}(x)を考えると、定数項は x^n の項を n微分したものなので、n! a_k となります。よって、先の一般化として

\displaystyle a_n = \frac{A^{(n)}(0)}{n!}

が得られます。

数列と母関数の対応

さて、母関数に話を戻すと、数列 \{a_n\}_{n=0}^{\infty} から母関数は

\displaystyle G(z) := \sum_{n=0}^{\infty} a_n z^n

で与えられました。逆に、母関数が与えられると、

\displaystyle a_n = \frac{G^{(n)}(0)}{n!}

によって数列 \{a_n\}_{n=0}^{\infty} を復元することができます。あるいは、極限を用いて

\displaystyle a_n = \frac{1}{n!} \lim_{z \to 0} G^{(n)}(z)

とすることもできます。極限は \lim_{z \to +0} などでも構いません。ただし、母関数が0で連続な導関数を持つとは限らないので、極限が同じ値になる保証は一般にはありません。

ともかく細かいことを考えなければ、上の関係式より、母関数を利用して数列の一般項を求められる可能性が見えてきます。

母関数の方法の例

それでは、簡単な例を通して母関数の使い方を見てみましょう。

数列 \{a_n\}_{n=0}^{\infty} は次の漸化式で定義されるとします。

a_n + a_{n-1} - 6 a_{n-2} = 0 (n \geq 2), a_0=1, a_1=7

このような数列の一般項を求めるのは高校で散々やられたかと思いますが、今回は母関数を使って求めることを考えます。まず、いきなり母関数を作ります。

\displaystyle G(z) = \sum_{n=0}^{\infty} a_n z^n

まず、漸化式を適用するために、最初の2項を外に出して

\displaystyle G(z) = a_0 + a_1 z + \sum_{n=2}^{\infty} a_n z^n
\displaystyle = 1 + 7z + \sum_{n=2}^{\infty} a_n z^n

とします。ここに漸化式を適用して a_n = -a_{n-1} + 6 a_{n-2} とすると、

\displaystyle G(z) = 1 + 7z + \sum_{n=2}^{\infty} (-a_{n-1} + 6a_{n-2}) z^n
\displaystyle = 1 + 7z - z \sum_{n=2}^{\infty} a_{n-1} z^{n-1} + 6z^2  \sum_{n=2}^{\infty} a_{n-2} z^{n-2}

と変形できます。ここで、和の中にある z をくくりだして a_{n-1} z^{n-1} のように添字を合わせていることに注意してください。これより、最後の和は

\displaystyle \sum_{n=2}^{\infty} a_{n-2} z^{n-2} = \sum_{n=0}^{\infty} a_n z^n = G(z)

となります。また、その前の和は

\displaystyle \sum_{n=2}^{\infty} a_{n-1} z^{n-1} = \sum_{n=1}^{\infty} a_n z^n
\displaystyle =\sum_{n=0}^{\infty} a_n z^n - a_0 = G(z) - 1

となります。以上から、母関数の関係式

G(z) = 1 + 7z - z (G(z) - 1) + 6z^2 G(z)

が得られます。これを整理すれば

(1 + z - 6z^2) G(z) = 1 + 8z

から(G(z) の係数が漸化式と同じ形になっていることに注意)

\displaystyle G(z) = \frac{1 + 8z}{1 + z - 6z^2}

が得られます。1 + z - 6z^2 = (1 - 2z)(1 + 3z) から右辺を部分分数分解すると、

\displaystyle G(z) = \frac{2}{1 - 2z} - \frac{1}{1 + 3z}

となります。ここで形式的な展開

\displaystyle \frac{1}{1 - 2z} = \sum_{n = 0}^{\infty} (2z)^n
\displaystyle \frac{1}{1 + 3z} = \sum_{n = 0}^{\infty} (-3z)^n

を用いると、

\displaystyle G(z) = \sum_{n = 0}^{\infty} \left( 2 \times 2^n - (-3)^n \right) z^n

が得られます。ここでは第 n 項は明示的に出ているので、一般項は

a_n = 2^{n+1} - (-3)^n

と出ます。

念のため条件式を満たすかどうかを確かめてみましょう。まず、a_0=1, a_1=7 はすぐに計算できます。漸化式の方は、

a_n + a_{n - 1} - 6 a_{n-2} = (4 + 2 - 6) \times 2^{n-1} + (-9 +3 + 6) \times (-3)^{n-2} =0

で満たします。これより、求める一般項は

a_n = 2^{n+1} - (-3)^n

であることが確認できました。

一般に母関数の方法は、収束するとは限らないべき級数を扱うために、必ずしも正しい答えを導かない可能性があり得ますが、そのような危険な場合でも、得られた式を直接漸化式に代入してその正当性を確かめることができる場合があります。

母関数の方法の一般的な説明はこれで終わります。

漸化式を解く

それでは、本題の漸化式

C_{n+1} = \sum_{k=0}^n C_k C_{n-k}, C_0 = 1

の一般項を求めましょう。

まずいきなり母関数を書きます。

\displaystyle G(z) := \sum_{n=0}^{\infty} C_n z^n

ここで、先に出てきた形式的べき級数の積

\displaystyle (AB)(x) = \sum_{n=0}^{\infty} \left( \sum_{k=0}^n a_k b_{n-k} \right) x^n

x^n の係数において a_n=b_n=C_n と置けば C_{n+1} の漸化式となることに注目します。よって、A(z)=B(z)=G(z) と置けば、

\displaystyle (G(z))^2 = \sum_{n=0}^{\infty} \left( \sum_{k=0}^n C_k C_{n-k} \right) z^n
= \sum_{n=0}^{\infty} C_{n+1} z^n

が得られます。和を変形すると

\displaystyle \sum_{n=0}^{\infty} C_{n+1} z^n = \frac{1}{z} \sum_{n=0}^{\infty} C_{n+1} z^{n+1}
\displaystyle =\frac{1}{z} \sum_{n=1}^{\infty} C_n z^n = \frac{\sum_{n=0}^{\infty} C_n z^n - C_0}{z}
\displaystyle = \frac{G(z) - 1}{z}

となります。これより、母関数の関係式

z (G(z))^2 - G(z) + 1 = 0

が得られます。

ここまで来たら、これを二次方程式の解の公式に入れて解いてしまいましょう。すると、母関数は

\displaystyle G(z) = \frac{1 \pm \sqrt{1 - 4z}}{2z}

のどちらかということになります。\lim_{z \to 0} G(z) = C_0 = 1 であることを考慮すると、

\displaystyle \lim_{z \to +0}\frac{1 + \sqrt{1 - 4z}}{2z} = +\infty

なので、これを除外できます。よって、母関数は

\displaystyle G(z) = \frac{1 - \sqrt{1 - 4z}}{2z}

であると判りました。

ここまで来ればあと一歩です。この式から C_n の一般項を求めるには、前回説明した一般化二項定理を用います。すなわち、\sqrt{1 - 4z} を展開するのです。公式に当てはめると、

\displaystyle \sqrt{1 - 4z} = (1-4z)^{1/2} = \sum_{k = 0}^{\infty} \left( \begin{matrix} 1/2 \\ k \end{matrix} \right) (-4z)^k
\displaystyle = 1 + \sum_{k = 1}^{\infty} \left( \begin{matrix} 1/2 \\ k \end{matrix} \right) (-4)^k z^k

となるので、これを母関数の式に代入すれば

\displaystyle G(z) = -\frac{1}{2z} \sum_{k = 1}^{\infty} \left( \begin{matrix} 1/2 \\ k \end{matrix} \right) (-4)^k z^k
\displaystyle = -\frac{1}{2z} \sum_{k = 0}^{\infty} \left( \begin{matrix} 1/2 \\ k+1 \end{matrix} \right) (-4)^{k+1} z^{k+1}
\displaystyle = 2 \sum_{k=0}^{\infty} \left( \begin{matrix} 1/2 \\ k+1 \end{matrix} \right) (-4)^k z^k

となります。ここで kn と読み替えて第 n 項の係数を取ると、求めたかった一般項の式

C_n = 2 \left( \begin{matrix} 1/2 \\ n+1 \end{matrix} \right) (-4)^n

が得られます。実際、

\displaystyle C_0 = 2 \times \frac{1}{2 \times 1!} = 1
\displaystyle C_1 = 2 \times \frac{1\times (-1)}{2^2 \times 2!} \times (-4) = 1
\displaystyle C_2 = 2 \times \frac{1 \times (-1) \times (-3)}{2^3 \times 3!} \times (-4)^2 = 2

となります。

しかし、この形のままだと少々汚いので、もう少し整形しましょう。\left( \begin{matrix} 1/2 \\ n+1 \end{matrix} \right)(-4)^n でともに n 個の負号が出るので、それらはキャンセルされることを先に断っておきます。すると、

\displaystyle C_n = 2 \times \frac{\prod_{k=1}^n (2k - 1)}{2^{n+1} (n+1)!} \times 4^n
\displaystyle =\frac{2^n}{(n+1)!} \prod_{k=1}^n (2k - 1)

という形にできます。ここで、

\displaystyle \prod_{k=1}^n (2k - 1) = \frac{(2n)!}{\prod_{k=1}^n (2k)} = \frac{(2n)!}{2^n n!}

となることに注意すると、

\displaystyle C_n = \frac{(2n)!}{n! (n+1)!} = \frac{1}{n+1} \frac{(2n)!}{(n!)^2}
\displaystyle = \frac{1}{n+1} \left( \begin{matrix} 2n \\ n \end{matrix} \right)

と変形できます。ここまで来ればこれ以上の整形は必要ないでしょう。

かくして、一般項

\displaystyle C_n = \frac{1}{n+1} \left( \begin{matrix} 2n \\ n \end{matrix} \right)

が得られました。

最初の問題に戻ると、n+1 個の数が n 個の二項演算(例えば四則演算)で結ばれた式において、式の計算順序の意味で異なる括弧の付け方は全部で上の C_n 通りある、ということになります。

Catalan 数

ようやくやっと求められた数

C_n = \frac{1}{n+1} \left( \begin{matrix} 2n \\ n \end{matrix} \right)

は、世の中では「Catalan(カタラン)数」と呼ばれています。この数は様々な数え上げに現れるとても重要な数です。例えば、凸n 角形の三角形分割の総数は C_{n-2} 通りあります。詳しくは Catalan number で検索してみてください。

n が小さいところでの値は次のようになります。

n  C_n
0  1
1  1
2  2
3  5
4  14
5  42
6  132
7  429
8  1430
9  4862
10  16796
11  58786
12  208012
13  742900
14  2674440
15  9694845
16  35357670
17  129644790
18  477638700
19  1767263190
20  6564120420


最後に、Catalan 数の近似式を与えておきます。これは n が大きいときの評価に用いられます。

\displaystyle C_n \approx \frac{2^{2n}}{\sqrt{\pi} n^{3/2}}

これを示すには、直接的には Wallis(ウォリス)の公式を用いますが、より一般に適用できる方法として Stirling の公式を用いて計算してみましょう。

(2n)! \approx 2 \sqrt{\pi n} ( 2n / e )^{2n}
n! \approx \sqrt{2 \pi n} ( n / e )^n

を二項係数の部分に代入すれば

\displaystyle C_n \approx \frac{1}{n+1} \frac{2 \sqrt{\pi n} ( 2n /e )^{2n}}{2 \pi n ( n /e )^{2n}} =\frac{1}{n+1} \frac{2^{2n}}{\sqrt{\pi n}}
\displaystyle \approx \frac{2^{2n}}{\sqrt{\pi} n^{3/2}}

となり、目的の近似式が得られました。

おわりに

今回は、括弧をカッコよく数えよう!というダジャレそのもののタイトルで、母関数を用いた数え上げをやってみました。その結果として、式の計算順序を指定する括弧の付け方の総数が Catalan 数という重要な数で表されることが分かりました。

ちなみに、この話をやろうと思った動機は、とある界隈で流行していた「ひきたし」というゲームにあります。問題は

26,59,23,34,95,85,21,87,53の中の数字で引き算を使わずに61を作ってください。

の形で与えられます。ただし、同じ数を2回使ってはいけません。使ってもいい演算は基本的には足し算、掛け算、割り算の3つですが、べき乗、対数を使ってもよいとすることもあります。例えば、上の問題の答えとして

53 + (26 + 23 + 34 + 85) / 21

を与えることができます。

筆者が思ったのは、これを全数探索するにはどれだけの場合を調べる必要があるだろう、ということです。例えば、演算子を加乗除の3つに限るとして、それを5個使う場合は、演算子を3個の中から5個重複を許して、数を9個の中から6個重複を許さずに、かつ順番を考慮して選ぶので、数と演算子の並びは

3^5 \times _9 \mathrm{P}_6 = 14696640

通りあります。これに対する括弧の付け方の総数は

C_5 = 42

通りあるので、これらを掛けあわせて得られる場合の数は全部で617258880通りとなります。あれ?意外と少ないな…

さて、つなぎの小話として考えたつもりが結構かかってしまいました。普段も遅筆で何度も迷惑をかけているので、もっとちゃんとしたいところであります。なお、次回の更新は未定です。

*1:右書き文化圏ではひょっとすると逆かもしれません。

*2:一般に、このような規則で定められる文法を「文脈自由文法(context-free grammer)」と言います。これは理論的にも実用的にも重要な概念です。例えば、世の中で使われているプログラム言語は、原則として文脈自由文法によって定義されています。(ちなみに、context-free grammer は意味的には「文脈非依存文法」と訳すべきです。この free は duty free などと同じ使い方で、これを「自由」と訳すのは誤訳と言っていいでしょう。ただ、文脈自由文法という用語は、慣例として今でも普通に使われています。)

*3:このように足し算、引き算、掛け算を備えた代数構造を「環」と言います。これに対して、最初の頃に出てきた「体」は、それらに加えて0以外での割り算を備えているという意味で、環の部分クラスとなっています。実際、この(0以外で)自由に割り算ができるという条件は大変強いもので、それによって体は特別な性質を多く持ちます。