カタラン数 
数学セミナー（２００９ ８月号）の特集で、寺尾宏明氏（北大・理）がカタラン数のことを取
り上げておられる。２００６オープンキャンパスで高校生や一般の方を対象に話されたもの
ということで興味深く読ませていただいた。
その中で、実は当HPで既に、「三角形分割」や「最短経路問題」で、「カタラン数」のことに
触れているということに気づかされた。
何でも、「カタラン数」の解釈の仕方にはいろいろあって、２００９年４月３日現在、１７０通
りもあるそうである。
「カタラン数」という名は、ベルギーの数学者 Ｅ．Ｃ．Ｃａｔａｌａｎ(1814〜1894) の名に由来す
るという。
ｎ 番目のカタラン数は、「 Ｃｎ 」と記される。
カタラン数の解釈として、私的には「トーナメント（勝ち抜き戦）表の場合の数」が一番分か
りやすいような気がする。
例 題 ｍ チームがトーナメント戦を行う。各試合に引き分けはないものとすると、
優勝チームが決まるまで全部で ｍ−１ 試合が必要であることは自明だろう。
それではその試合のやり方は何通りあるのだろうか。ただし、ｍ≧２ とする。
いま、 Ｃｎ ： ｎ＋１ チームによるトーナメント表の場合の数 とする。
（イ） ｍ＝２ のとき、
で、１種類しかない。 このとき、 Ｃ1＝１ となる。
（ロ） ｍ＝３ のとき、
で、２種類しかない。 このとき、 Ｃ2＝２ となる。
（ハ） ｍ＝４ のとき、
で、５種類しかない。 このとき、 Ｃ3＝５ となる。
ところで、上図の（イ）（ロ）（ハ）を眺めていると、演算の結合法則が関係していそうな雰囲
気が漂ってくる！実のところ、カタランの当初の考え方と聞く。
すなわち、（イ）の（１）は、「 ａ に ｂ を掛ける」とも理解される。（もちろん「足す」と考えてもよい。）
このことを、「 （ａｂ） 」 と書くことにすると、
（ロ）の（１）は、 （（ａｂ）ｃ） だし、 （ロ）の（２）は、 （ａ（ｂｃ）） という意味になる。
また、（ハ）の（１）は、 （（（ａｂ）ｃ）ｄ） だし、 （ハ）の（２）は、 （（ａ（ｂｃ））ｄ） となり、
（ハ）の（３）は、 （（ａｂ）（ｃｄ）） で、 （ハ）の（４）は、 （ａ（（ｂｃ）ｄ）） となり、
（ハ）の（５）は、 （ａ（ｂ（ｃｄ））） であるものと解釈できる。
この解釈は、さらに次のように考えると、道順の問題に翻訳される。
すなわち、「 （ａｂ） 」は、「 ａ に ｂ を掛ける」ということなので、「 ａｂ× 」と書くことにする。
このとき、 （（ａｂ）ｃ） は、 ａｂ×ｃ× 、（ａ（ｂｃ）） は、 ａｂｃ×× と書ける。
また、 （（（ａｂ）ｃ）ｄ） は、 ａｂ×ｃ×ｄ× 、（（ａ（ｂｃ））ｄ） は、 ａｂｃ××ｄ× 、
（（ａｂ）（ｃｄ）） は、 ａｂ×ｃｄ×× 、（ａ（（ｂｃ）ｄ）） は、 ａｂｃ×ｄ×× 、
（ａ（ｂ（ｃｄ））） は、 ａｂｃｄ××× と書ける。
以下では、（ハ）の場合について、道順の場合の数との対応を考えよう。
そこで、次のような３×３の格子状の道を準備する。
点Ａを出発し、点Ｂに至る道を考える。ただし、
ａｂ×ｃ×ｄ×などの順列の２番目以降において、
文字（ｂ、ｃ、ｄ）ならば、「−」（横に移動）、 掛け算「×」ならば、「｜」（縦に移動）
するものとする。このとき、
| ａｂ×ｃ×ｄ× |
|
ａｂｃ××ｄ× |
|
ａｂ×ｃｄ×× |
 |
|
 |
|
 |
|
|
|
|
|
| ａｂｃ×ｄ×× |
|
ａｂｃｄ××× |
|
|
 |
|
 |
|
|
上記の道順の方法は、ちょうど左図のような街路の最短
経路の場合の数に等しい。
その場合の数は、「最短経路問題」によれば、
4Ｃ2−１＝５（通り）
で、上記の結果と一致する。
一般に、ｎ＋１ チームによるトーナメント表を考え、それを道順の問題に翻訳すると、下図
の街路の点Ａから点Ｂまでの最短経路の場合の数が、カタラン数 Ｃｎ となる。
このとき、下図のような補助の街路を考えることにより、 Ｃｎ が求められる。
左図より、
Ｃｎ＝2ｎ-2Ｃｎ-1−2ｎ-2Ｃｎ-3
で、上式の右辺をさらに計算すると、
２（２ｎ−１）！/｛（ｎ＋１）！（ｎ−１）！｝
すなわち、
という公式が得られる。
この公式により、カタラン数を全て求めることが出来る。
| ｎ |
１ |
２ |
３ |
４ |
５ |
６ |
７ |
８ |
９ |
１０ |
・・・ |
| Ｃｎ |
１ |
２ |
５ |
１４ |
４２ |
１３２ |
４２９ |
１４３０ |
４８６２ |
１６７９６ |
・・・ |
ところで、カタラン数と組合せの式の関係と言えば、巷間では、
が広く知れ渡っているようである。これは、下図のような補助街路を用いて、最短経路を求
めることにより得られる。
左図より、
Ｃｎ＝2ｎＣｎ−2ｎＣｎ-1
で、何れも、
となるので等しいのは当然だが、素朴
な疑問で、どちらの方が覚えやすいの
かな？
上記では、最短経路問題として、 Ｃｎ＝2ｎＣｎ−2ｎＣｎ-1 を導いたが、別な視点で、こ
の公式の意味づけを考えてみよう。
例 ５００円硬貨を持つ人が ｎ 人、千円札を持つ人が ｎ 人の計 ２ｎ 人が一列に並ぶ。
各自より、５００円を集金するとき、集金する人がおつりを用意しなくても済むような並び
方は何通りあるか。
この問題で、例えば、ｎ＝３ とし、５００円硬貨を持つ人を○、千円札を持つ人を●で表し、
実際に並び方を書いてみよう。
まず、おつりのことを考えずに、並び方の全てを書きだしてみると、
| ○○○●●● |
|
○○●○●● |
|
○○●●○● |
|
○○●●●○ |
|
○●○○●● |
|
|
|
|
|
|
|
|
|
| ○●○●○● |
|
○●○●●○ |
|
○●●○○● |
|
○●●○●○ |
|
○●●●○○ |
|
|
|
|
|
|
|
|
|
| ●○○○●● |
|
●○○●○● |
|
●○○●●○ |
|
●○●○○● |
|
●○●○●○ |
|
|
|
|
|
|
|
|
|
| ●○●●○○ |
|
●●○○○● |
|
●●○○●○ |
|
●●○●○○ |
|
●●●○○○ |
の 6Ｃ3＝２０ 通りある。このうち、おつりを用意せずに済む並び方は、次の５通りである。
（上記の表の内の青色部分）
| ○○○●●● |
|
○○●○●● |
|
○○●●○● |
|
○●○○●● |
|
○●○●○● |
問題は、おつりが不足する場合の数の数え方である。次の１５通りが該当する。
| ○○●●●○ |
|
○●○●●○ |
|
○●●○○● |
|
○●●○●○ |
|
○●●●○○ |
|
|
|
|
|
|
|
|
|
| ●○○○●● |
|
●○○●○● |
|
●○○●●○ |
|
●○●○○● |
|
●○●○●○ |
|
|
|
|
|
|
|
|
|
| ●○●●○○ |
|
●●○○○● |
|
●●○○●○ |
|
●●○●○○ |
|
●●●○○○ |
上記の１５通りの内、おつり不足が最初に発生する位置は、それぞれ赤色の部分である。
この場合の数を数えるために、●までの○と●を入れかえる。
この操作により、●の直前までは、○と●は同数なので、必ず、○が１個増え、●が１個
減る。
| ●●○○○○ |
|
●○●○○○ |
|
●○○○○● |
|
●○○○●○ |
|
●○○●○○ |
|
|
|
|
|
|
|
|
|
| ○○○○●● |
|
○○○●○● |
|
○○○●●○ |
|
○○●○○● |
|
○○●○●○ |
|
|
|
|
|
|
|
|
|
| ○○●●○○ |
|
○●○○○● |
|
○●○○●○ |
|
○●○●○○ |
|
○●●○○○ |
このとき、上記の場合の数は、○４個と●２個の順列の総数に等しいので、
6Ｃ2＝１５ 通りである。
よって、求める場合の数は、 6Ｃ3−6Ｃ2＝５ （通り） である。
上記の考え方を一般化すると、
まず、５００円硬貨を持つ人が ｎ 人、千円札を持つ人が ｎ 人の計 ２ｎ 人が一列に並ぶ
場合の数は、 2ｎＣｎ 通りある。このとき、あるところでおつり不足が発生する場合の数は、
５００円硬貨を持つ人が ｎ＋１ 人、千円札を持つ人が ｎ−１ 人の計 ２ｎ 人が一列に並ぶ
場合の数に等しいので、 2ｎＣｎ-1 通りある。
よって、求める場合の数は、 2ｎＣｎ−2ｎＣｎ-1 通りある。
（コメント） 背景に最短経路問題を意識したので、ちょっとスッキリしないような意味づけで
した。読者の方で、「これは！」という意味づけをお持ちの方は是非ご教示下さい。
平成２１年８月１１日付けで、ＨＮ「凡人」さんよりカタラン数の漸化式の話題をいただいた。
トーナメント戦の考え方において、次のように考えると、カタラン数についての漸化式が得
られる。
「ｎ＋１ チームによるトーナメント戦の決勝の相手は、
ｎ チームによるトーナメント戦の優勝チームと、残り １ チーム
ｎ−１ チームによるトーナメント戦の優勝チームと、
残り ２ チームによるトーナメント戦の優勝チーム
ｎ−２ チームによるトーナメント戦の優勝チームと、
残り ３ チームによるトーナメント戦の優勝チーム
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
２ チームによるトーナメント戦の優勝チームと、
残り ｎ−１ チームによるトーナメント戦の優勝チーム
１ チームと、残り ｎ チームによるトーナメント戦の優勝チーム
の各場合が考えられるので、 Ｃ0＝１ として、
Ｃｎ＝Ｃｎ-1・Ｃ0＋Ｃｎ-2・Ｃ1＋Ｃｎ-3・Ｃ2＋・・・＋Ｃ0・Ｃｎ-1
が成り立つ。
（コメント） 凡人さん、ありがとうございます。とても分かりやすい導き方ですね！でも、この
漸化式を解くことは可能なのでしょうか？解はもう分かっているので、漸化式とい
うよりも、一つの性質ととらえておけばいいのかな？
カタラン数 Ｃｎ はまた、凸 （ｎ＋２）角形の三角形分割の個数としてもとらえられる。
次のように考えればよい。（ → 参考：「三角形分割」）
左辺以外の辺に時計回りに、ａ、ｂ、ｃ、・・・ と文字を割り当て、三角形の第３の辺に、他
の２辺の積を割り当てる。
例 三角形の場合
この場合、 Ｃ1＝１ となる。
例 四角形の場合
となり、演算結果 （（ａｂ）ｃ） 、（ａ（ｂｃ）） と三角形分割の方法とが関連づけられる。
この場合、 Ｃ2＝２ となる。
「三角形分割」において、次のことを示した。
凸 ｎ 角形（ ｎ≧３ ）において、三角形分割の方法の数が、Ｆ(ｎ) 通りあるものとする。
明らかに、Ｆ(３)＝１ である。 いま、ｎ≧４ とする。 ３＜ｋ＜ｎ において、凸
ｎ 角形は
３つの部分に分割される。
Ｆ(ｎ) の定義より、
Ｆ(ｎ) ＝１・Ｆ(ｎ−１)＋Ｆ(３)・Ｆ(ｎ−２)＋・・・
＋ Ｆ(ｋ−１)・Ｆ(ｎ−ｋ＋２) ＋・・・
＋ Ｆ(ｎ−２)・Ｆ(３) ＋Ｆ(ｎ−１)・１
が成り立つ。
この公式を用いて、カタラン数 Ｃｎ を計算してみよう。
Ｃ1＝Ｆ(３)＝１
Ｃ2＝Ｆ(４)＝１・Ｆ(３)＋Ｆ(３)・１＝２
Ｃ3＝Ｆ(５)＝１・Ｆ(４)＋Ｆ(３)・Ｆ(３)＋Ｆ(４)・１＝２＋１＋２＝５
Ｃ4＝Ｆ(６)＝１・Ｆ(５)＋Ｆ(３)・Ｆ(４)＋ Ｆ(４)・Ｆ(３) ＋Ｆ(５)・１＝５＋２＋２＋５＝１４
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
ここで、 Ｃ0＝１ とすれば、例えば、Ｃ4 は、
Ｃ4＝Ｃ0・Ｃ3＋Ｃ1・Ｃ2＋ Ｃ2・Ｃ1 ＋Ｃ3・Ｃ0
と書き直せるように、一般のカタラン数 Ｃｎ に関する漸化式
Ｃｎ＝Ｃｎ-1・Ｃ0＋Ｃｎ-2・Ｃ1＋Ｃｎ-3・Ｃ2＋・・・＋Ｃ0・Ｃｎ-1
の成り立つことが、Ｆ(ｎ) に関する漸化式より分かる。
「三角形分割」において、Ｆ(ｎ) に関する漸化式の一般項
を求めることができた。 Ｃｎ ＝ Ｆ(ｎ＋２) という関係から、Ｃｎ の一般項
が直ちに得られる。この式と最短経路の問題で得られた Ｃｎ の式
は、当然同じ値になる。（すなわち、 2ｎＣｎ-1＝2ｎＣｎ+1 より明らか！）
（コメント） 上記の話で、ＨＮ「凡人」さんの疑問に答えられたでしょうか．．．？
平成２１年８月１７日付けで、「凡人」さんがカタラン数の漸化式の解釈に取り組まれた。
（一部文言等を修正させていただきました！）
より、
Ｆ(ｎ＋２)＝2ｎＣｎ-1/ｎ＝Ｃｎ
一方
Ｆ(ｎ＋３)＝2ｎ+2Ｃｎ/（ｎ＋１）
なので、
Ｆ(ｎ＋３)/Ｆ(ｎ＋２)＝ｎ・2ｎ+2Ｃｎ/｛（ｎ＋１）・2ｎＣｎ-1｝＝２（２ｎ＋１）/（ｎ＋２）
よって、 Ｃｎ ＝ Ｆ(ｎ＋２) より、
（ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ
が成り立つ。この式は、三角形分割の個数 Ｆ(ｎ) から得られたが、最初から、
（ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ
という漸化式が導けないかというのが「凡人」さんの意図するところであろう。
例 ４・Ｃ3＝１０・Ｃ2 の解釈を考えてみよう。
Ｃ2＝２ は、次の２通りであった。
このうちの１通り、例えば、
に、新しい１チームを加えるために新しい試合を追加する方法を考える。
上記の通り、１０通りある。同様にして、
に、新しい１チームを加えるために新しい試合を追加する方法を考えると、
で、これも１０通りある。これらを、Ｃ3＝５ の場合
と比較すると、上記の２０通りの中には、４通りずつ同じものが出現していることが分かる。
（トーナメント表の番号が同じものは、同じトーナメント表！）
以上から、漸化式 ４・Ｃ3＝１０・Ｃ2 の成り立つことが分かる。
上記のことを一般化して、「凡人」さんは軽妙に次のように考えられた。
１．（ｎ＋１）チームによるトーナメント表の縦線の本数は「試合数×２＋１」本であるが、試
合数は、ｎ であるので、２ｎ＋１（本）の縦線がある。
このトーナメント表に新たに １チームを加えるには、２ｎ＋１（本）の縦線のうちの
１ 本
から横に線を出して張り出しのような形で １ チーム分の試合を追加する。
２．横線は左右どちらにも出す事ができて、それらは区別されるので、計 ２（２ｎ＋１）通り
の増やし方がある。
３．（ｎ＋１）チームでの全てのトーナメント表で同じことを行うと、２（２ｎ＋１）・Ｃｎ 通りにな
る。
４．ところで、（ｎ＋２）チームのトーナメント表で、新しく加えられた １
チームの入る場所を
区別して考えると、（ｎ＋２）・Ｃｎ+1 通りのトーナメント表が得られる。
５．上述の ３．と４．のトーナメント表の数は一致するので、漸化式
（ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ
が得られる。
（コメント） 「凡人」さんの非凡さに感動しました！ このような経験をさせていただいた「凡
人」さんに感謝します。この考え方をすれば、何も三角形分割を持ち出すことなく、
漸化式が作れますね。
漸化式 （ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ より、
（ｎ＋１）・Ｃｎ＝２（２ｎ−１）・Ｃｎ-1
ｎ・Ｃｎ-1＝２（２ｎ−３）・Ｃｎ-2
（ｎ−１）・Ｃｎ-2＝２（２ｎ−５）・Ｃｎ-3
・・・・・・・・・・・・・・・・・・・・・
４・Ｃ3＝１０・Ｃ2
３・Ｃ2＝６・Ｃ1
これらを辺々かけて、
（ｎ＋１）！・Ｃｎ/２＝２ｎ−1・（２ｎ−１）！/｛２ｎ−1・（ｎ−１）！｝
＝（２ｎ−１）！/（ｎ−１）！
よって、
Ｃｎ＝２（２ｎ−１）！/｛（ｎ＋１）！（ｎ−１）！｝
すなわち、
が得られる。
上記で、三角形分割と演算の順番の関係を見たが、円周上の互いに交差しない弦の引
き方にも関係することを以下に見てみよう。
円周上に ２ｎ 個の点があるものとする。
例 ｎ＝１ のとき
これは、 （ａｂ） に相当し、括弧のつけ方に注目すれば、
（）
で、その場合の数は、カタラン数 Ｃ1＝１ と一致する。
例 ｎ＝２ のとき
これらは、ａ を省いて考えると、 （ｂ（ｃｄ）） や （（ｂｃ）ｄ） となり、３文字
Ａ、Ｂ、Ｃ の場
合の演算の結合の仕方
（Ａ（ＢＣ）） や （（ＡＢ）Ｃ）
の場合の数に一致するので、カタラン数 Ｃ2＝２ となる。
例 ｎ＝３ のとき
これらは、ａ を省いて考えると、
（ｂ（ｃｄ）（ｅｆ）） 、（ｂ（ｃ（ｄｅ）ｆ）） 、（（ｂｃ）ｄ（ｅｆ）） 、 （（ｂ（ｃｄ）ｅ）ｆ） 、 （（ｂｃ）（ｄｅ）ｆ）
となり、さらに、ｂ を省いて、括弧のつけ方を考慮すると、４文字 Ａ、Ｂ、Ｃ、Ｄ の場合の演
算の結合の仕方
（（ＡＢ）（ＣＤ）） 、（（Ａ（ＢＣ））Ｄ） 、（Ａ（Ｂ（ＣＤ））） 、（（（ＡＢ）Ｃ）Ｄ） 、（Ａ（（ＢＣ）Ｄ））
の場合にそれぞれ対応するので、カタラン数 Ｃ3＝５ と一致する。
これらのことを一般化して、次の事実が成り立つ。
円周上の ２ｎ 個の点を互いに交差しない弦で結ぶ方法の数は、カタラン数 Ｃｎ
（証明）
円周上の ２ｎ 個の点を互いに交差しない弦で結ぶ方
法の数を Ｆ（ｎ）とおく。
点 １ と点 ｋ を結ぶ弦で、円周上の ２ｎ 個の点を２つ
のグループに分ける。点 ｋ は、点 １ と同じグループに
入るものとする。
このとき、題意より、ｋ の値が奇数になることはない。
ｋ＝２、４、６、・・・、２ｎ−２、２ｎ と場合分けして考える。
ｋ＝２ のとき、 円周上 ２ｎ−２ 個の点を互いに交差しない弦で結ぶ方法の数は、
Ｆ（ｎ−１）通りで、その１通りに対して、残りの２点の弦の引き方は、１通り。
よって、この場合の数は、 １・Ｆ（ｎ−１） 通り
ｋ＝４ のとき、 円周上 ２ｎ−４ 個の点を互いに交差しない弦で結ぶ方法の数は、
Ｆ（ｎ−２）通りで、その１通りに対して、点 １ と点
４ を除いた残りの２点の
弦の引き方は、Ｆ（１）通り。
よって、この場合の数は、 Ｆ（１）・Ｆ（ｎ−２） 通り
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
ｋ＝２ｎ−２ のとき、 点 １ と点 ２ｎ−２ を除いた残りの２点の弦の引き方は、Ｆ（１）通り
で、その１通りに対して、円周上 ２ｎ−４ 個の点を互いに交差しない弦で
結ぶ方法の数は、Ｆ（ｎ−２）通り。
よって、この場合の数は、 Ｆ（ｎ−２）・Ｆ（１） 通り。
ｋ＝２ｎ のとき、 点 １ と点 ２ｎ の弦の引き方は、１通りで、その１通りに対して、円
周上、２ｎ−２ 個の点を互いに交差しない弦で結ぶ方法の数は、Ｆ（ｎ−１）
通り。
よって、この場合の数は、 Ｆ（ｎ−１）・１ 通り
以上から、求める場合の数 Ｆ（ｎ）は、
Ｆ(ｎ) ＝１・Ｆ(ｎ−１)＋Ｆ(１)・Ｆ(ｎ−２)＋・・・＋ Ｆ(ｎ−２)・Ｆ(１)
＋Ｆ(ｎ−１)・１
となる。これは、カタラン数 Ｃｎ の漸化式
Ｃｎ＝１・Ｃｎ-1＋Ｃ1・Ｃｎ-2・＋・・・＋Ｃ1・Ｃｎ-2・＋Ｃｎ-1・Ｃ0
に一致するので、Ｆ（ｎ）は、カタラン数 Ｃｎ に一致する。 （証終）
当ＨＰがいつもお世話になっているＳ（Ｈ）さんが、平成２１年３月２１日付けで、数学的帰納
法の練習問題として、次のような問題を提起された。
集金問題 ある劇場の入場料は、５千円とする。５千円札しかもっていない ｎ(≧ １)人と、
１万円札しかもっていない ｎ 人の合計 ２ｎ 人が劇場前の広場で勝手に円形の
輪を作って開場を待っているとする。
このとき、劇場の入口の受付人は、ある適当な人から時計回りに集金すれば、
釣り銭に不足することがないようにできることを示せ。
（この集金問題が必ず可能であることは、カタラン数 Ｃｎ≧１ から明らかだろう。
→ 参考：「集金問題」）
命題 Ｐ ： 全ての自然数 ｎ に対して、劇場の入口の受付人は、ある適当な人から時計回
りに集金すれば、釣り銭に不足することがないようにできる
（証明） 数学的帰納法による。
ｎ＝１ のとき、 ５千円札しかもっていない人と、１万円札しかもっていない人の合計
２人
が劇場前の広場で待っているので、５千円札しかもっていない人から、５千円札を受け
取り、次に、１万円札しかもっていない人から１万円札を受け取り、５千円札を渡せば
よい。 よって、ｎ＝１ のとき成り立つ。
ｎ＝ｋ（ｋ≧１）のとき、命題 Ｐ が成り立つと仮定する。
すなわち、５千円札しかもっていない ｋ(≧ １)人と、１万円札しかもっていない
ｋ 人の合
計 ２ｋ 人が劇場前の広場で勝手に円形の輪を作って開場を待っていて、劇場の入口の
受付人は、ある適当な人から時計回りに集金すれば、釣り銭に不足することがないよう
にできる。
今、５千円札しかもっていない ｋ＋１人と、１万円札しかもっていない
ｋ＋１ 人の合計
２ｋ＋２ 人が劇場前の広場で勝手に円形の輪を作って開場を待っているものとする。
この中には、５千円札しかもっていない人がいて、しかも、時計回りで隣の人が、１万円
札しかもっていない人である組合わせが必ず存在する。
この２人を除くと、残りは、５千円札しかもっていない ｋ(≧ １)人と、１万円札しかもってい
ない ｋ 人の合計 ２ｋ 人が劇場前の広場で勝手に円形の輪を作って開場を待っていて、
劇場の入口の受付人は、ある適当な人から時計回りに集金すれば、釣り銭に不足する
ことがないようにできる。途中で、最初に見つけた２人からは、５千円札しかもっていない
人から、５千円札を受け取り、次に、１万円札しかもっていない人から１万円札を受け取り、
５千円札を渡せばよい。
よって、 ｎ＝ｋ＋１ のときも、命題 Ｐ は成り立つ。
以上から、全ての自然数 ｎ に対して、劇場の入口の受付人は、ある適当な人から時計
回りに集金すれば、釣り銭に不足することがないようにできることが示された。 （証終）
さて、次は、カタラン数の生成関数の話題に移ろう。
カタラン数については、上記の計算で、
| ｎ |
１ |
２ |
３ |
４ |
５ |
６ |
７ |
８ |
９ |
１０ |
・・・ |
| Ｃｎ |
１ |
２ |
５ |
１４ |
４２ |
１３２ |
４２９ |
１４３０ |
４８６２ |
１６７９６ |
・・・ |
であることを見た。そこでは、カタラン数そのものは、バラバラな感じであったが、これら全て
のカタラン数を係数とする１つの多項式を考え、カタラン数の持つ性質を追究しようというの
が、生成関数の考え方である。
生成関数には、カタラン数に関する情報が全て含まれると言っても過言ではないだろう。
カタラン数 Ｃｎ の生成関数とは、 Ｃ0＝１ として、
Ｆ（ｘ）＝Ｃ0＋Ｃ1・ｘ＋Ｃ2・ｘ2＋Ｃ3・ｘ3＋・・・＋Ｃｎ・ｘｎ＋・・・
と書けるものを言う。
具体的には、 Ｆ（ｘ）＝１＋ｘ＋２ｘ2＋５ｘ3＋１４ｘ4＋・・・ という多項式である。
ここで、 Ｃｎ＝Ｃｎ-1・Ｃ0＋Ｃｎ-2・Ｃ1＋Ｃｎ-3・Ｃ2＋・・・＋Ｃ0・Ｃｎ-1 から、
Ｆ（ｘ）2＝Ｃ02＋（Ｃ1・Ｃ0＋Ｃ0・Ｃ1）ｘ＋（Ｃ2・Ｃ0＋Ｃ1・Ｃ1＋Ｃ0・Ｃ2）ｘ2＋・・・
＝Ｃ1＋Ｃ2ｘ＋Ｃ3ｘ2＋・・・
なので、 １＋ｘ・Ｆ（ｘ）2＝Ｃ0＋Ｃ1・ｘ＋Ｃ2・ｘ2＋Ｃ3・ｘ3＋・・・＝Ｆ（ｘ） であると言える。
すなわち、 Ｆ（ｘ）は、等式 ｘ・Ｆ（ｘ）2−Ｆ（ｘ）＋１＝０ を満たす。
これを、Ｆ（ｘ）に関する２次方程式と考えれば、その解は、
となるが、Ｆ（０）＝１ なので、
と書ける。これが、カタラン数 Ｃｎ の生成関数となる。
ここで、Ｔａｙｌｏｒ 展開のことを考えれば、
Ｃｎ＝Ｆ(ｎ)（０）/ｎ！
が成り立つ。
例
なので、 Ｆ’（０）＝１ より、 Ｃ1＝Ｆ’（０）/１！＝１ となる。
２項定理というと、（ａ＋ｂ）ｎ の展開公式だが、実は、ｎ の値は自然数に限らず任意の実
数においても成り立つことが知られている。
（ → 参考「超越数を手計算で求める」における二項級数の項）
を二項級数に展開して、ｘｎ+1 の項を求めると、
となる。したがって、
を二項級数に展開したときの ｘｎ の項は、
となる。よって、カタラン数 Ｃｎ の値は、
すなわち、
となる。
以下、工事中