【母関数マスター講座 第14回】カタラン数と最短経路〜「超えられない壁」の完全理解〜

前回（第13回）は、確率の連立漸化式を母関数で解く方法を学びました。

今回は、格子経路の問題で登場する「カタラン数」を母関数の視点から解明します。「対角線を超えてはいけない最短経路」は入試でも難問として知られますが、母関数を使うと、その構造が鮮やかに見えてきます。

母関数マスター講座の全体像、シラバスは以下の記事でご覧ください。

https://note.com/goukalize/n/ne5f45c351ab2

LINE追加でまとめPDF配布中！
ㅤ
公式LINEを追加して「母関数マスター講座」と送信していただいた方に、講座全体をまとめたPDF（全63ページ）を無料でお配りしています。
ㅤ
自動送信のため、送信文は 「母関数マスター講座」 と正確にお送りください。
ㅤ
https://line.me/R/ti/p/@965ezfgt?oat_content=url

1. 問題：対角線を超えない最短経路

次の有名な問題を考えます。

【問題】
原点 $${(0, 0)}$$ から点 $${(n, n)}$$ まで、右（R）と上（U）の1歩ずつで進む最短経路のうち、常に対角線 $${y = x}$$ の上側に出ない（つまりどの時点でも「Rの回数 ≧ Uの回数」を満たす）ものは何通りあるか？

制約なしなら $${{}_{ 2n}\mathrm{C}_n}$$ 通りですが、「対角線を超えない」という制約がつくと、数え上げが格段に難しくなります。この答えが「カタラン数」です。

$$
\begin{aligned}
C_n = \frac{1}{n+1} {}_{2n}\mathrm{C}_n \tag{①}
\end{aligned}
$$

2. カタラン数の漸化式

カタラン数には次の漸化式が成り立ちます。 $${C_0 = 1}$$ とし、

$$
\begin{aligned}
C_n = \sum_{k=0}^{n-1} C_k \, C_{n-1-k} \quad (n \geq 1) \tag{②}
\end{aligned}
$$

②の意味を経路で考えてみましょう。出発後、最初のステップは必ずR（右）です。そのあと、初めて再び対角線（Rの回数 = Uの回数）に戻る瞬間を考えます。その時点を $${(k+1, k+1)}$$ とすると、「出発からその瞬間まで」は $${(0,0) → (k+1, k+1)}$$ の対角線接触なしの経路で $${C_k}$$ 通り、「その後から $${(n, n)}$$ まで」は $${C_{n-1-k}}$$ 通りあります。 $${k}$$ を $${0}$$ から $${n-1}$$ まで動かして足し上げると②になります。

3. 母関数で閉じた形を求める

カタラン数の母関数を $${G(x) = \displaystyle \sum_{n=0}^{\infty} C_n x^n}$$ と定義します。②の右辺は $${G(x)}$$ の「自分自身との畳み込み」になっているので、

$$
\begin{aligned}
G(x) - 1 = x \cdot G(x)^2 \tag{③}
\end{aligned}
$$

（左辺の $${-1}$$ は $${n = 0}$$ の項 $${C_0 = 1}$$ を分離したもの、右辺の $${x}$$ は添字を1つずらすためのものです。）

③を整理すると、 $${G(x)}$$ についての2次方程式が現れます。

$$
\begin{aligned}
xG(x)^2 - G(x) + 1 = 0 \tag{④}
\end{aligned}
$$

④を解の公式で解きます。

$$
\begin{aligned}
G(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x} \tag{⑤}
\end{aligned}
$$

$${x \to 0}$$ のとき $${G(x) \to C_0 = 1}$$ でなければなりません。 $${+}$$ を選ぶと $${\frac{1 + \sqrt{1}}{0}}$$ と発散するので、

$$
\begin{aligned}
G(x) = \frac{1 - \sqrt{1 - 4x}}{2x} \tag{⑥}
\end{aligned}
$$

⑥がカタラン数の母関数の閉じた形です。

4. 一般項を読み取る

⑥から $${C_n}$$ を読み取るために、 $${\sqrt{1 - 4x} = (1 - 4x)^{1/2}}$$ を一般化二項定理で展開します。ここで、 $${r}$$ が実数（整数でなくてよい）のときの一般化二項係数を

$$
\begin{aligned}
\binom{r}{k} = \frac{r(r-1)(r-2)\cdots(r-k+1)}{k!}
\end{aligned}
$$

と定義すると、形式的冪級数として $${(1+u)^r = \displaystyle \sum_{k=0}^{\infty} \binom{r}{k} u^k}$$ が成り立ちます（ $${r}$$ が正の整数のとき、この式は通常の二項定理と一致します）。

$$
\begin{aligned}
(1 - 4x)^{1/2} = \sum_{k=0}^{\infty} \binom{1/2}{k} (-4x)^k \tag{⑦}
\end{aligned}
$$

⑦を⑥に代入して $${x^n}$$ の係数を取り出すと、 $${\binom{1/2}{n+1}(-4)^{n+1}}$$ を $${2}$$ で割り $${-1}$$ で掛けた形になり、整理すると

$$
\begin{aligned}
C_n = \frac{1}{n+1} {}_{2n}\mathrm{C}_n \tag{⑧}
\end{aligned}
$$

が得られ、①の公式が母関数から導出されました。

最初のいくつかの値を確認すると、 $${C_0 = 1, \, C_1 = 1, \, C_2 = 2, \, C_3 = 5, \, C_4 = 14}$$ となり、実際に経路を数え上げた結果と一致します。

まとめ

カタラン数は「畳み込み型の漸化式」という形をしていて、これが母関数の世界では「 $${G(x)}$$ の2次方程式」に翻訳されます。2次方程式を解いて展開するだけで、一般項の閉じた公式が手に入る。格子経路だけでなく、括弧の対応、二分木の数え上げなど、カタラン数が顔を出す問題はすべてこの母関数で統一的に理解できます。

次回、第15回では「整数の分割」を母関数で扱います。オイラーの五角数定理の世界への入り口です。

【無料相談受付中】医学部・獣医学部受験対策はゴウカライズにおまかせを！

「一般入試の勉強だけでも大変なのに、面接や小論文までどう準備すればいいかわからない…」
「医学部や獣医学部のような専門性の高い入試に、本当に今の対策で足りるのか不安…」

そんな悩みをお持ちの受験生・保護者の皆様、医学部・獣医学部専門塾 ゴウカライズにご相談ください！

医学部受験・獣医学部受験は、学科試験だけでなく、面接、小論文、志望理由書など学部特有の対策が必要になる入試です。
ゴウカライズでは、それぞれの志望校や受験方式に合わせて、合格に必要なすべてをトータルサポートします。

【一般入試】完全オーダーメイドの学習計画 ：
医学部・獣医学部の一般入試は、わずかな失点が合否を分けることもあります。
あなたの現状と志望校の出題傾向を分析し、合格ラインに到達するための最短ルートを設計します。
日々の進捗管理で、学習の遅れも見逃さず、適宜ルートを最適に修正します。

【推薦・総合型選抜】面接・小論文もプロが対応 ：
推薦入試や総合型選抜で必須となる「面接・小論文・志望理由書」の対策もお任せください。
医学部・獣医学部特有のテーマに対応できるプロ講師が、合格レベルの答案作成と受け答えを指導します。

プロ講師・優秀学生講師の個別指導 ：
学習管理だけでなく、経験豊富なプロ講師や、高倍率から選抜された優秀な学生講師による完全個別指導も提供。
苦手科目の克服や過去問解説など、あなたのニーズに合わせた1対1の指導が可能です。

【医学部・獣医学部対策】特殊な対策に完全対応 ：
医学部入試、獣医学部入試は、どちらも特殊な対策が必要です。
面接などがある入試形式の場合、学科試験以外の準備も侮れません。
そんな入試に精通したプロがゴウカライズには多数在籍しています。
ゴウカライズ代表の大北も医学部・獣医学部受験の指導経験は15年を超える大ベテランです。

まずは無料相談で、あなたの合格までのロードマップを一緒に描きませんか？
無理な勧誘は一切ありません。
予備校選びに迷っているなどの相談でも、客観的にアドバイスを行います。

公式LINEでいつでも無料相談を受け付けています！

https://goukalize.com/

https://line.me/R/ti/p/@965ezfgt?oat_content=url

#医学部専門予備校 #入試数学 #大学受験 #オンライン塾