カタラン数ってなんだかよく分からない。カタラン数の式はどうやって導くの？簡単な具体例で理解したい。
このような悩みを解決します。
本記事では、カタラン数の具体例として「最短経路」と「玉入れ問題」の２つ紹介し、それらが対応していることを解説します。さらに、簡単な最短経路の問題でカタラン数を実際に求め、それを一般化した
\[ c_n=\frac{_{2n}\mathrm{C}_n }{n+1} \]
を導きます。
カタラン数を求める際の実践的な方法についても解説していますので、ぜひ最後までお読みください。
✔︎本記事の内容
１．カタラン数の例として「最短経路」と「玉入れ問題」について解説します
２．「最短経路」と「玉入れ問題」が一対一に対応していることを解説します
３．カタラン数を求める実践的な方法をご紹介します
４．カタラン数の求め方を解説します（一般化）
ちなみにこの記事を書いている私の経歴は以下の通りです。
- 数学講師歴２０年以上
- 大学院の修士課程終了（専門は情報幾何学）
- 数学検定１級取得
カタラン数は場合の数を求める場面で登場します
・最短経路の問題
・トーナメントの問題
・凸多角形の三角形分割
カタラン数を理解するには、「最短経路の問題」と「玉入れ問題」から入るのがおすすめです。
ちなみにカタラン数は中学受験問題にもしばしば登場します。様々なタイプの問題が出題されていますが、最短経路の問題に対応させると考えやすくなります。
それでは本記事を読んでカタラン数の基礎の身につけていきましょう。
カタラン数が分かる２つの例「最短経路」と「玉入れ問題」
カタラン数は次の式で表されます。
\[ c_n=\frac{_{2n}\mathrm{C}_n }{n+1} \]
この式は後ほど導くとして、\(n=5\)の場合について、具体例をみていきましょう。
まずは最短経路の問題を考えます。
次のような最短経路の個数がカタラン数と呼ばれる数になっています。
（１）最短経路の問題
図において、AからBまで行く最短経路のうち、対角線ABを突き破らないものの個数を求めよ。
答え\(c_5\)通り
５×５マスの場合はこの経路の個数が\(c_5\)となります。（理由は後述）
（１）は次の図において、ＡからＢまで行く最短経路と同じであることも確認しておきましょう。
続いて、玉入れ問題を考えます。
次のような問題における玉の入れ方の総数がカタラン数になっています。
（２）玉入れ問題
赤玉5個、白玉5個の計10個の玉を、１個ずつ袋に入れていく。
ただし、袋の中の玉の数は常に
（赤玉の数）≧（白玉の数）
となるようにする。このときの玉の入れ方の総数を求めよ。
答え\(c_5\)通り
赤玉と白玉の個数がともに５個の場合、玉の入れ方の総数が\(c_5\)となります。（理由は後述）
全く別の題材である（１）と（２）ですが、これらは１対１に対応し、実質的に同じです。後ほど解説しますが（１）と（２）の答えはともに\(c_5＝42\)（通り）となります。
最短経路の問題と玉入れ問題が１対１に対応する理由
「最短経路の問題」と「玉入れ問題」が１対１に対応する理由を解説します。
玉入れ問題（２）において、赤玉をR、白玉をWで表し、次のような対応を考えてみます。
「赤玉を袋に入れる・・・右に１マス進む」
「白玉を袋入れる・・・左に1マス進む」
例えば、袋に次の順番で玉を入れたとします。
RRWRWWRRWW
これを、次の経路に対応させます。
このような対応を考えると（２）の玉入れ問題は、（１）の対角線ＡＢを突き破らない最短経路の場合の数に対応します。
つまり、「最短経路の問題」と「玉入れ問題」が１対１に対応していることが分かります。
ちなみに（２）の玉入れ問題では、袋の中の玉の数が
Ｒの数≧Ｗの数
となるような場合の数ですので、次のように対角線ABを突き破るものは不適です。
Rの数が２、Wの数が３ですので、明らかに
Ｒの数＜Ｗの数
となってしまうからです。
したがって、（２）の玉入れ問題は、（１）の対角線ABを突き破らない最短経路の個数に完全に対応しています。
カタラン数\(c_5\)を求める実践的な方法
それでは実際に\(c_5\)を求めてみましょう。
\(c_5\)のようなカタラン数は様々な場面で登場しますが、（１）のような最短経路の問題に対応させると考えやすくなります。
\(c_5\)のように\(n\)が小さい場合の最短経路を求める際の実践的方法は「書き込み」です。
次の図は、Aからスタートして、各交差点までの最短経路の個数を順に書き込んだものです。各交差点の左側の数字と下側の数字を足していきます。
この図から\(c_5=42\)と求まります。
このような書き込みは地味ですが、\(n\)が小さいカタラン数を求める場合は、一番実践的です。
対称性に着目すると、さらに簡単に計算することも可能ですので、考えてみて下さい。
\(c_5\)の別の数え方からカタラン数の式を導く
\(n\)が大きい場合の対応方法について考えます。少し難易度が上がります。
まず（１）の対角線ＡＢの１つ上側に直線ℓを引きます。
このとき
\begin{align*}
c_5&=「AからＢへの最短経路」\\
& -「ＡからＢまでの最短経路のうちℓ上の点を通る経路・・・(☆)」\\
&=_{10}\mathrm{C}_5-(☆)
\end{align*}
となります。ここで、
(☆)は図の「ＡからＢ’までの最短経路・・・(☆☆）」と１対１に対応しています。
理由は以下の通りです。
【理由】
（☆）の１つについて、最初にℓと交わる点をＰとし、経路Ｐ以降の部分をℓに関して折り返します。するとこれは「ＡからＢ’までの最短経路・・・(☆☆）」の１つになっています。
逆に（☆☆）は図より、必ずℓと交わるので、最初にℓと交わる点以降をℓに関して折り返すと（☆）が得られます。
以上の理由から
\begin{align*}
c_5&=_{10}\mathrm{C}_5-(☆)\\
&=_{10}\mathrm{C}_5-(☆☆)\\
&=_{10}\mathrm{C}_5-_{10}\mathrm{C}_4\\
&=252-210\\
&=42
\end{align*}
\(c_n\)の計算【一般化】
先ほどは\(n=5\)の場合について、カタラン数\(c_5\)の求め方を解説しました。
ここでは、一般化して\(c_n\)の式を導いてみましょう。
上で解説した方法と同様に考えると
\begin{align*}
c_n=_{2n}\!\mathrm{C}_n-_{2n}\!\mathrm{C}_{n-1}
\end{align*}
となりますね。あとは、この式を変形して
\[ c_n=\frac{_{2n}\mathrm{C}_n }{n+1} \]
を導きます。
\begin{align*}
c_n&=_{2n}\!\mathrm{C}_n-_{2n}\!\mathrm{C}_{n-1}\\
&=_{2n}\!\mathrm{C}_n-\cfrac{(2n)!}{(n-1)!(n+1)!}\\
&=_{2n}\!\mathrm{C}_n-\cfrac{(2n)!}{1}\cdot \cfrac{n}{n!}\cdot \cfrac{1}{(n+1)n!}\\
&=_{2n}\!\mathrm{C}_n-\cfrac{(2n)!}{n!n!}\cdot \cfrac{n}{n+1}\\
&=_{2n}\!\mathrm{C}_n-_{2n}\!\mathrm{C}_n\cdot \cfrac{n}{n+1}\\
&=_{2n}\!\mathrm{C}_n \left(1-\cfrac{n}{n+1}\right) \\
&=\frac{_{2n}\mathrm{C}_n }{n+1}
\end{align*}
この結果は（１）の問題において「対角線ABを突き破らない最短経路\(c_n\)」は「ＡからＢまで行く最短経路\(_{2n}\mathrm{C}_n\)」の\(\cfrac{1}{n+1}\)であるということを意味しています。
この結果は興味深いですね。
まとめ
今回はカタラン数について解説しました。
ポイントは以下の通りです。
・カタラン数に関する問題は最短経路の問題と対応させる
・\(n\)が小さいときは書き込みが実践的
・\(n\)が大きい場合に対応するために
\(c_n=_{2n}\!\mathrm{C}_n-_{2n}\!\mathrm{C}_{n-1}=\cfrac{_{2n}\mathrm{C}_n }{n+1}\)
を導けるようにしておく。
多くのカタラン数に関する問題は最短経路の問題と対応させて考えるのがおすすめです。
大学入試問題を解くとき
\begin{align*}
c_n=\frac{_{2n}\mathrm{C}_n }{n+1}
\end{align*}
の式を使う場面は少ないと思いますが、背景としてカタラン数の導出過程を知っておくことをおすすめします。
最後にカタラン数の記述がある本をご紹介します。
大学への数学シリーズには、今回解説した「直線ℓに関して折り返す方法」が詳しく記載されています。
次の本では、トーナメントの問題や凸多角形の三角形分割についても、解説があります。
今回は以上です。
最後までお読みいただき、ありがとうございました。
