カタラン数の公式｜C_n=2nCn/(n+1) の鏡像法による証明・漸化式・対角線をこえない道とかっこの並べ方【大学数学・東大京大レベル】

カタラン数の公式｜C_n=2nCn/(n+1) の鏡像法による証明・漸化式・対角線をこえない道とかっこの並べ方【大学数学・東大京大レベル】

合格大作戦 算数・数学公式辞典 › 場合の数・確率

大学受験

Cn=1n+1 2nCn=2nCn−2nCn−1C_n=\frac{1}{n+1}\,{}_{2n}\mathrm{C}_n={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}

C0, C1, C2, …=1, 1, 2, 5, 14, 42, 132, …C_0,\ C_1,\ C_2,\ \ldots=1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ \ldots

この公式のポイント

  • 対角線より上に出ない道の数が CnC_n
  • 悪い道はy=x+1y=x+1 で折り返す（鏡像法）
  • 漸化式 Cn+1=∑CkCn−kC_{n+1}=\sum C_kC_{n-k}
  • かっこの並び・三角形分割・開票も同じ答え
うかるくん

うかるくん

対角線より上に出る悪い道って、どうやって数えるの？

合格先生

合格先生

y=x+1y=x+1 に初めて触れた点から後を折り返すんだ。すると (n−1, n+1)(n-1,\ n+1) への道と1対1に対応するぞ。

カタラン数の公式

「対角線より上に出ない道」「正しいかっこの並べ方」「多角形の三角形分割」など、ちがう問題の答えが、同じ数の列 1, 1, 2, 5, 14, 42, 132, … になります。これをカタラン数といいます（19世紀の数学者カタランの名前にちなむ）。

カタラン数 CnC_n

Cn=1n+1 2nCn=2nCn−2nCn−1C_n=\frac{1}{n+1}\,{}_{2n}\mathrm{C}_n={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}

漸化式：C0=1C_0=1、Cn+1=C0Cn+C1Cn−1+⋯+CnC0=∑k=0nCkCn−kC_{n+1}=C_0C_n+C_1C_{n-1}+\cdots+C_nC_0=\displaystyle\sum_{k=0}^{n}C_kC_{n-k}

C0=1, C1=1, C2=2, C3=5, C4=14, C5=42, C6=132, C7=429C_0=1,\ C_1=1,\ C_2=2,\ C_3=5,\ C_4=14,\ C_5=42,\ C_6=132,\ C_7=429

CnC_n が答えになる問題：

  • (0, 0)(0,\ 0) から (n, n)(n,\ n) まで、右か上に進み、直線 y=xy=x より上に出ない道の数
  • かっこ nn 組の正しい並べ方（「(」と「)」が正しく対応する並べ方）
  • 凸 (n+2)(n+2) 角形を対角線で三角形に分ける方法の数
  • A、B が nn 票ずつ得票し、開票の途中でいつも A の票が B の票以上である開票順
11112213551491414スタートゴールy＝x右か上に1つずつ進み対角線より上に出ない各点の数＝左の点＋下の点C₄＝14 通り
(0, 0) から (4, 4) まで対角線より上に出ない道。各点の数は「左の点＋下の点」で、ゴールは C4=14C_4=14

証明①：鏡像法（折り返し）

(0, 0)(0,\ 0) から (n, n)(n,\ n) まで右か上に1つずつ進む道は、右 nn 回・上 nn 回の並べ方なので全部で 2nCn{}_{2n}\mathrm{C}_n 通り（同じものを含む順列）。このうち、y=xy=x より上に出る道（悪い道）を数えて引きます。

  • 悪い道は、どこかで直線 y=x+1y=x+1 に触れます。最初に触れた点を P とします。
  • P から後の部分だけを y=x+1y=x+1 について折り返すと（右と上を入れかえる）、ゴールの (n, n)(n,\ n) は (n−1, n+1)(n-1,\ n+1) に移ります。
  • 逆に、(0, 0)(0,\ 0) から (n−1, n+1)(n-1,\ n+1) への道は必ず y=x+1y=x+1 に触れるので、最初に触れた点から後を折り返すと悪い道にもどります。

よって、悪い道と「(n−1, n+1)(n-1,\ n+1) への道」は1対1に対応し、その数は 2nCn−1{}_{2n}\mathrm{C}_{n-1}。したがって

Cn=2nCn−2nCn−1=(2n)!n! n!−(2n)!(n−1)! (n+1)!=(2n)!n! (n+1)!{(n+1)−n}=1n+1 2nCnC_n={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}=\frac{(2n)!}{n!\,n!}-\frac{(2n)!}{(n-1)!\,(n+1)!}=\frac{(2n)!}{n!\,(n+1)!}\{(n+1)-n\}=\frac{1}{n+1}\,{}_{2n}\mathrm{C}_n
P(4, 4)(3, 5)Oy＝x＋1青：y＝x＋1 に触れる道橙：P から後を折り返した道悪い道＝(3, 5) への道＝₈C₃＝56 通り70−56＝14
n=4n=4 の鏡像法。y=x+1y=x+1 に触れた道を P から後だけ折り返すと、(3, 5) への道になる

証明②：漸化式

かっこ n+1n+1 組の正しい並べ方で、先頭の「(」に対応する「)」に注目します。その間に kk 組、その後ろに n−kn-k 組の正しい並びが入り、「( kk 組 ) n−kn-k 組」の形になります（k=0, 1, …, nk=0,\ 1,\ \ldots,\ n）。間の並べ方が CkC_k 通り、後ろが Cn−kC_{n-k} 通りなので

Cn+1=∑k=0nCkCn−kC_{n+1}=\sum_{k=0}^{n}C_kC_{n-k}

例：C3=C0C2+C1C1+C2C0=2+1+2=5C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5、C4=C0C3+C1C2+C2C1+C3C0=5+2+2+5=14C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0=5+2+2+5=14。

凸五角形の三角形分割：5通り((()))(()())(())()()(())()()()かっこ3組の正しい並べ方：5通り（どちらも C₃＝5）
凸五角形の三角形分割も、かっこ3組の並べ方も、どちらも C3=5C_3=5 通り

大学受験での使い方

大学受験

例題1（対角線をこえない道）

座標平面で、点 (0, 0) から点 (4, 4) まで、xx 軸方向か yy 軸方向に1ずつ進みます。直線 y=xy=x より上（y>xy>x の部分）に出ない道は何通りですか。

解き方

全部の道は 8C4=70{}_8\mathrm{C}_4=70 通り。悪い道は、最初に y=x+1y=x+1 に触れた点から後を折り返すと (3, 5) への道と1対1に対応するので 8C3=56{}_8\mathrm{C}_3=56 通り。

70−56=1470-56=14 通り。（図1のように、各点に数を書いて足していっても14になります。）

答え　14 通り

大学受験

例題2（かっこの並べ方）

かっこ「(」と「)」を3個ずつ並べるとき、正しく対応する並べ方をすべて書き出し、その数を答えなさい。

解き方

((()))、(()())、(())()、()(())、()()() の5通り。

公式でも C3=14⋅6C3=204=5C_3=\dfrac14\cdot{}_6\mathrm{C}_3=\dfrac{20}{4}=5。「(」を右へ1歩、「)」を上へ1歩とすれば、例題1と同じ「対角線より上に出ない道」になります。

答え　5 通り

大学受験

例題3（六角形の三角形分割）

凸六角形を、交わらない対角線で三角形に分ける方法は何通りですか。凸 mm 角形の分け方を tmt_m（t3=1, t4=2, t5=5t_3=1,\ t_4=2,\ t_5=5）として求めなさい。

解き方

頂点を順に 1〜6 とし、辺 1-6 をふくむ三角形の残りの頂点 kk（k=2, 3, 4, 5k=2,\ 3,\ 4,\ 5）で場合分けします。三角形の両側に kk 角形と (7−k)(7-k) 角形が残ります（2角形は「何もない」として t2=1t_2=1）。

t6=t2t5+t3t4+t4t3+t5t2=5+2+2+5=14t_6=t_2t_5+t_3t_4+t_4t_3+t_5t_2=5+2+2+5=14。

これはカタラン数の漸化式と同じ形で、t6=C4=14t_6=C_4=14 です。

答え　14 通り

高校の範囲をこえる内容と入試での使い方

教科書での位置：道の数え方や組合せは数学Aで習いますが、「カタラン数」という名前と公式は高校の教科書の範囲外（発展）です。ただし、証明に使う鏡像法も漸化式も、数学A・数学Bの考え方で説明できます。

入試での使い方：

  • 答案に「カタラン数より 1n+1 2nCn\dfrac{1}{n+1}\,{}_{2n}\mathrm{C}_n」とだけ書くのは避けましょう。折り返しで1対1に対応することを説明してから使います。
  • 小さい nn では、図1のように各点に数を書いて足す方法が確実で、検算にも使えます。
  • 難関大の入試では、道の数・開票の順・かっこの並びなど、見た目はちがっても背景にカタラン数がある問題があります。「1, 2, 5, 14」が出てきたらカタラン数を疑いましょう。

よくある間違い

腕でバツを作る合格先生

合格先生

折り返す線は y=xy=x ではなく y=x+1y=x+1 だ。対角線の上を通るだけの道は悪い道ではないぞ。

  • 折り返す線をまちがえる：折り返すのは y=xy=x ではなく y=x+1y=x+1。「y=xy=x に触れる」道は対角線上を通るだけで、悪い道とはかぎりません。
  • 引く数をまちがえる：引くのは 2nCn−1{}_{2n}\mathrm{C}_{n-1}（2nCn+1{}_{2n}\mathrm{C}_{n+1} と同じ値）。ゴールが (n−1, n+1)(n-1,\ n+1) に移ることから確かめましょう。2nCn−2{}_{2n}\mathrm{C}_{n-2} などにするのはまちがいです。
  • 1n+1\dfrac{1}{n+1} を 1n\dfrac1n にする：n=3n=3 で確かめると 14⋅20=5\dfrac14\cdot20=5。13⋅20\dfrac13\cdot20 は整数になりません。

練習問題

○の札を持つうかるくん

うかるくん

小さい数は書き出して確かめるぞ。

  1. 大学受験 カタラン数 C5C_5 を公式で求めなさい。
    答えと解説を見るC5=16⋅10C5=2526=42C_5=\dfrac16\cdot{}_{10}\mathrm{C}_5=\dfrac{252}{6}=42
  2. 大学受験 A、B の2人の候補が4票ずつ得票しました。1票ずつ開票するとき、開票の途中でいつも A の票数が B の票数以上である開票の順（票の並び）は何通りですか。
    答えと解説を見るA を右へ1歩、B を上へ1歩とすると、(0, 0) から (4, 4) への道で y=xy=x より上に出ないもの。C4=8C4−8C3=70−56=14C_4={}_8\mathrm{C}_4-{}_8\mathrm{C}_3=70-56=14 通り
  3. 大学受験 漸化式 Cn+1=∑k=0nCkCn−kC_{n+1}=\sum_{k=0}^{n}C_kC_{n-k} を使って C6C_6 を求めなさい。
    答えと解説を見るC6=1⋅42+1⋅14+2⋅5+5⋅2+14⋅1+42⋅1=132C_6=1\cdot42+1\cdot14+2\cdot5+5\cdot2+14\cdot1+42\cdot1=132

関連する公式

よくある質問

カタラン数とは？

C_n=2nCn/(n+1) で表される数の列 1, 1, 2, 5, 14, 42, 132, … のことです。対角線より上に出ない道の数や、正しいかっこの並べ方の数などになります。

カタラン数の公式はどうやって証明しますか？

すべての道 2nCn 通りから、y=x+1 に触れる悪い道を引きます。悪い道は最初に触れた点から後を折り返すと (n−1, n+1) への道と1対1に対応するので 2nC(n−1) 通りです。

カタラン数の漸化式は？

C_0=1、C_{n+1}=C_0C_n+C_1C_{n−1}+…+C_nC_0 です。かっこの並びで、先頭の「(」に対応する「)」の位置で場合分けすると導けます。

カタラン数は入試で使えますか？

名前と公式は高校の範囲外です。答案では鏡像法による1対1対応を説明してから使い、小さい数では書き出して検算するのが安全です。

あわせて読みたい

出典・参考

  • 文部科学省「高等学校学習指導要領（平成30年告示）」数学A（場合の数と確率）
  • 高校の範囲外の発展内容（組合せ論）

最終更新：2026年10月11日／作成：大学受験合格大作戦