皆さん、こんにちは。
今回は、場合の数を考える題材で頻出する数列である「カタラン数」について紹介します。
0.カタラン数とは？
カタラン数とは、
上の図で、Aを出発して縦横１マスずつ動いてBにたどり着く最短経路のうち「対角線ABを一度も『跨ぐ』ことなく（※踏むだけならOK)、右下のエリアだけ通るもの」の個数です。
例えば、n=3の場合は下の図のような5通りが、n=3のカタラン数となります。
大学入試においては、九大が2008年後期第２問(3)で、n=6の状況がずばりそのまま出題されたことがあります。
平成の九大理系後期数学 -2008年- - ちょぴん先生の数学部屋 (hatenablog.com)
この場合の答えは、n=6のカタラン数、c6=132通りとなります。
このカタラン数、経路の個数の問題だけでなく実は結構汎用性が高いんです。
次のような中学入試の算数の問題がよく知られています。
「4匹のオオカミと4匹のヒツジを１匹ずつ檻に入れていきます。ただし、檻の中でオオカミがヒツジよりも多くなってしまうとヒツジが食べられてしまうので、常にヒツジの数がオオカミの数以上になるように檻に入れないといけません。このような入れ方は全部で何通りあるか求めましょう」
小学生であれば樹形図なりを描いて力づくで調べるのでしょうが、この問題、「ヒツジを入れたら右に１マス動く」「オオカミを入れたら上に1マス動く」点の経路の個数、と解釈すれば、n=4の場合のカタラン数を調べる問題に帰着できます。
図の斜線部は「オオカミ＞ヒツジ」となる領域なので通行禁止であり、対角線を含んだ右下を通るしかないというわけです。今回の場合は、c4=14通りが答えです。
このように、途中経過において「常に○○の個数・点数が××のそれ以上」という条件があるときの場合の数を調べるのに、カタラン数は有効な手段となります。
カタラン数そのものでなくとも、そこでの考え方を応用して解く確率の問題が、北大の1996年第１問(3)で出題されています（北大史上最強の難問で有名です）
平成の北大理系数学 -1996年- - ちょぴん先生の数学部屋 (hatenablog.com)
こんな感じで、時々難関大学の入試にも題材として登場するのが、カタラン数です。
この手のカタラン数絡みの問題は、正直やり方を知ってないと解けないタイプの問題なので、まずはカタラン数を直接計算する方法を紹介していきます。
1.カタラン数の一般項導出（解法1: 直接場合の数を調べる）
カタラン数の計算には、余事象の考え方を使います。つまり、
cn =「A→Bの全経路数an」ー「そのうち、対角線ABを最低1回は跨ぐ経路の数bn」
で計算します。考える上での補助として図１のようにxy座標を設定しておきます。
まず、全経路数anの計算は教科書レベルで、
と簡単に計算できます。要は、「右」をn個・「上」をn個横一列に並べる方法、ですね。
問題はbnの計算の方で、ここでこの問題ならではのユニークな考え方をします。
まずは「対角線AB(直線y=x)を跨ぐ」という状況を考えやすいように言い換えます。
それって、「点が１段上の直線y=x+1を通る」と同じ意味ですよね。
ということで、点Pi (i, i+1)で初めてこの直線を通ると考えて検討していくことにします（図２）
このとき、図３のように、Pi→Bの経路を直線y=x+1について対称に反転させます。
Piより後ではいくらでも対角線ABを跨いでも構わないので、Pi→Bの経路数は、Pi→B' (Bと対称な点）の経路数と全く同じだとわかります。
よって、今回考えたい「A→（途中y=x+1を通らず)Pi→B」の経路数は、「A→（途中y=x+1を通らず)Pi→B’」の経路数で求まることになります。
ところで、いったん俯瞰して考えると、AからB'へ行こうと思ったらどうあがいても直線y=x+1を通らざるを得ないですよね。Piがどこにあろうとこの状況は変わらないので、
結局、今まで考えてきた「A→（途中y=x+1を通らず)Pi→B’」の経路数をi=0,1,・・,n-1で全部足し上げれば「A→B'」の経路数そのものになります。これが求めたかったbnそのものということになるので、bnは、
と求まります。
あとは、cn =an - bnだったので、カタラン数cnの一般項は、
という綺麗な式で求まります！anをn+1で割ったものがカタラン数cnということで、A→Bの経路のうち対角線を跨がないものの割合は1/(n+1)しかないという興味深い結果になっています。
このカタラン数の一般項は、実は2021年の東工大第３問の題材になっていて、(3)ではカタラン数が素数になるnの条件を調べさせています。かなり難しい問題です。
2021年度 東工大数学 解いてみました。 - ちょぴん先生の数学部屋 (hatenablog.com)
ちなみに、以前紹介した階乗の近似式スターリングの公式（階乗を近似計算する式 ～スターリングの公式～ - ちょぴん先生の数学部屋 (hatenablog.com) )を使うと、より計算しやすい形にできます。
近似精度はn=13の時点で誤差1%未満で、n≦12でも実数値をみればかなり精度良く計算できてることが分かります。
話を戻すと、
『跨ぐ』の言い換え→直線に対して経路を対称反転→経路の言い換え
というこの問題でしか使わないようなユニークな発想がてんこ盛りなので、初見では対処不能で解き方を知ってないと解けない問題でした。
（九大の過去問のようにnが具体的な小さめの数字であれば、経路数の和を図に次々書き込んでいく形で力づくで解くことが可能ですが、北大の過去問のような一般的なケースでは、上のやり方を知ってないとまず無理でしょうね）
このようにカタラン数の一般項を直接導出するのは発想面でかなり厳しいので、もっと機械的に解けないか？と思いたくなります。
というわけで、次はカタラン数の一般項を漸化式を立てて求める方法を紹介します。
2.カタラン数の一般項導出（解法2: 漸化式を使う）
漸化式を使えばもっと機械的に簡単に解ける！と思いたいところですが、実はちゃんとその漸化式を解くには大学数学の手法が必要になっています。その上、工程もかなり長いです。
2-1. 漸化式の立式
とにもかくにも、まずは漸化式を立てます。
図４のように、Qi (i,i)で初めて経路が対角線ABを通る状況を考えると、前半のA→Qiで「i-1マスのカタラン数」が、後半のQi→Bで「n-iマスのカタラン数」が出現することになります。前半後半で経路は独立して考えられるので、
A→Qi→Bの経路数Niは
で計算できます。あとは、Niを全て足し上げれば「nマスのカタラン数」になるので、漸化式は、
と求まります。ただし、初期条件として
を課します。n=0ならAから不動なので1通り、n=1なら「右→上」だけなので1通りと、実際の状況ともマッチしています。
場合の数の問題を解いているとよくこの漸化式が出現するため、カタラン数は色んな場面で登場してくることになります（後述）。
さて、この漸化式、シグマの形になってて一見分かりにくいですが、「n+2項間漸化式」という化け物です。このタイプの漸化式は、残念ながら高校数学の範囲では解けません。（帰納法を使う手もなくはないですが、先ほど求めたあの一般項を実験で予想するのはかなり難しいでしょう）
というわけで、ここからは大学で初めて登場するであろう解法「母関数の構成」で解いていきたいと思います。
2-2. カタラン数の母関数
母関数とは次のようなものです。
cnをn次の係数として無限個項を足してできる関数（べき級数）です。
今から、漸化式を使ってこの母関数f(x)を作り、それを「テイラー展開」することでn次の係数cnを求める、という方針で解いていきたいと思います。
漸化式を適用するために、まずは母関数f(x)を2乗したものを考えます。
これを「畳み込み和」というテクニックでひとまとめにすると次のようになります。
（畳み込み和については、シグマ公式を生み出す数列 ～ベルヌーイ数～ - ちょぴん先生の数学部屋 (hatenablog.com)で説明しているので、そちらを参照してください）
すると、シグマの中身に先ほどの漸化式の右辺が登場したので、左辺に書き換えてしまいます。
あとは、係数の番号と次数が一致するように両辺にxをかけてあげれば、
のようにf(x)の関係式が求まります。これをf(x)について解けば母関数f(x)が求まります。
⑧はf(x)の２次方程式になっているので、2次の係数xが0か否かで場合分けする必要があります。
x=0のとき、⑧に代入すれば
が求まり、この結果は初期条件⑥と一致しています。
x≠0のとき、２次方程式を解くと、
のように２通りの解が出てしまうので、何らかの方法でどっちかに絞らないといけません。
ここで、そもそものf(x)の定義式
に戻ると、この式に不連続な点はないですね（※）。既にf(0)の値が分かってるのですから、x=0でf(x)が連続になってる方を選べばよいことになります。ということで、
となっているか否かを２通りの各々でチェックします。実際に調べると、
となり＋の方は発散、ーの方は1に収束してくれるので、－のほうを選びます。つまり、
です。これでカタラン数の母関数f(x)が求まりました。
（※厳密にいうと「各項に発散する成分がない」ということです。ただ、各項は発散せずとも、無限級数を取っているのでf(x)全体ではxの値によっては発散してしまったり定義できなくなってしまうことがあります。現に、今回求まったf(x)もx>1/4ではルートの中が虚数になって定義できなくなります。これは「収束半径」という話題なのですが、今回の記事では紹介すると長くなり本筋から外れてしまうので説明を省略します）
2-3. 母関数のテイラー展開
次に、求まった母関数f(x)を、「テイラー展開」を使ってべき級数に戻し、cnを調べていきます。テイラー展開については、バーゼル問題の証明その1 ～オイラーの証明～ - ちょぴん先生の数学部屋 (hatenablog.com)で簡単に触れているので、そちらを参照ください。
f(x)をいきなりテイラー展開の式に当てはめるのは式が複雑で難しいので、肝になるルートの部分のテイラー展開を考えることで、f(x)のテイラー展開を構築していきます。
ルートの部分を簡略化した次の関数g(t)をテイラー展開していきます。
実際に、g(t)のm次導関数を考えると、規則性から
がわかり、結果g(t)のテイラー展開が次のように求まります。
中身がだいぶカタラン数に近くなってきましたね。
この式を利用すると、最終的に知りたかったf(x)のテイラー展開は、
と計算でき、あとはn次の係数を比較することで
とカタラン数の一般項が求まりました！当然先ほどの「直接導出」と同じ結果になります。
このように、漸化式を用いた解法は、大学数学のテクニックをいくつも使う必要があり工程も長いため、高校生向けの参考書には載せられないわけです。
3.その他カタラン数の出現する場合の数
さて、最後に、場合の数の計算で「カタラン数の漸化式」が登場する題材を２つほど紹介します。
3-1. n人のトーナメントを作る方法
1つ目は、n人が参戦するトーナメントの山が何通り作れるか？という問題です。ただし、各山に誰を当てはめるかまでは考えません。
求める場合の数をan通りとして、n人のうちi人を左の山に、残りのn-i人を右の山に振り分ける山を作る状況を考えます。
すると、左の山のトーナメントの作り方がai通り、右の山のトーナメントの作り方がan-i通り作れて、左右は独立しているので、結局anの漸化式は
と書けて、カタラン数の漸化式と酷似したものになります。実際に、anはcn-1と等しくなります。
実際に、n=4の時に実験すると、確かに場合の数はc3=5通りあることが分かります。
3-2. 凸n多角形を対角線で三角形に分割する方法
2つ目は、凸n多角形を対角線で複数の三角形に分ける方法が何通りあるか？です。但し、対角線は多角形内部で交わらないようにとるものとします。
n=4の場合の例が下のような感じです。
左の２つがカウント対象で、右の対角線が交わる場合はNGということです。
今、凸n多角形の頂点A0, A1,・・・,An-1が時計回りに並んでるとし、求める場合の数をbnとします。
この中で、頂点An-1, An-2と三角形を作るような頂点Aiが0≦i≦n-3でただ１個だけ必ず存在しているはずです。
この三角形でn角形を分割すると、上半分にi+2角形が、下半分にn-i-1角形ができます。各々の多角形はそれぞれbi+2通り、bn-i-1通りに分割でき、その分け方は独立して決められるので、結局
と漸化式が求まり、これもカタラン数の漸化式に酷似しています。
実際に、bnはcn-2と等しく、具体的にn=5,6で実験すると下のようになります。
こんな風に、カタラン数は場合の数を計算する場面で頻繁に登場する奥の深い数列なのです。
ではでは。
