カタラン数とは？考え方と最短経路問題の解き方を解説！

「カタラン数なんて初めて聞いた」という方や、「カタラン数について知りたい」と思っている方も多いのではないでしょうか。

カタラン数は、数学の中でも特に興味深いテーマの一つであり、多くの受験生にとって理解が難しいと感じることがあるかもしれません。

本記事では、カタラン数の正体と実際にどのような問題で現れるのかについて詳しく説明していきます。これを読めば、カタラン数がもっと身近に感じられ、最短経路問題などの解き方がぐっと簡単になることでしょう。

[高校生から始められる]
↓税理士になる方法・勉強方法をチェック！↓

1.カタラン数とは？

カタラン数は、場合の数の分野で登場する特別な数列です。カタラン数は大学入試だけでなく、中学受験でも出てくることがあり、その重要性は非常に高いです。具体的には、数学の様々な問題、特に組み合わせや最短経路問題で頻繁に利用されます。

1-1.一般項で表す数列

カタラン数の一般項は、次のように表されます：

ここで、は2n個の要素からn個を選ぶ組み合わせの数を表します。具体的には、次のように計算されます：

カタラン数の計算は一見複雑に見えますが、この一般項を知っていると簡単に求めることができます。例えば、n=3の場合、

1-2.場合の数の問題を解く時に使用すると便利

カタラン数を理解することで、場合の数の問題を効率的に解くことが可能になります。

例えば、3×3のグリッド上で、赤の斜線よりも上にはみ出ることなく、左下から右上まで移動する最短経路の総数を考えるとしましょう。
この場合、以下のように色分けで具体例を書き出すと5つの最短経路が現れます。

1.右→右→右→上→上→上
2.右→右→上→右→上→上
3.右→右→上→上→右→上
4.右→上→右→右→上→上
5.右→上→右→上→右→上

ちょうど先ほどのカタラン数でC₃＝5であることと一致します。「Cの添字」と「3×3のグリッド」とが対応していますね。

と、カタラン数の計算法を利用すれば、全部の場合を書き出さなくとも答えを得ることができます。

一般にカタラン数は、この形状の格子状の道を、y＞x（いわゆる対角線）の部分を通らないで行ける最短経路の本数の総数と一致しています。

したがって、この類の問題を解く場合、カタラン数を知っていると、nが大きくなっても経路の総数を一瞬で求められ、非常に便利です。

カタラン数の理解は最短経路問題だけでなく、その他の多くの組み合わせ問題にも応用できるため、数学の試験対策としても非常に有用です。カタラン数をしっかりと理解し、その応用範囲を広げていきましょう。

[高校生から始められる]
↓税理士になる方法・勉強方法をチェック！↓

2.カタラン数の一般項の導き方

カタラン数の一般項を導く方法は、大学数学レベルの知識を要する方法と、もう少し簡単に理解できる方法があります。

例えば、母関数やマクローリン展開を使った導き方は大学数学の知識が必要です。しかし、「難しいことは聞きたくない」という方は、理解できそうな方法だけを読んでいただければ十分です。

2-1.定理①　経路を数えて解く

基本となる考え方は、余事象を考えることと、xy座標上で問題を考えることです。カタラン数は、最短経路問題において、対角線y＝xを超えない（つまりつねにy≦xの領域を通る）経路の数を求める際に使われます。具体的な例として、4×4のグリッドの場合を考えてみましょう。

1. xy座標系において、左下（0,0）から右上（4,4）までの経路を考えます。
2. 経路が対角線y＝xを超えないようにするためには、y≦xを保ちながら移動する必要があります。

もし「y≦xをつねに保ちながら」という制約がなく、単純に下の図のような道であるなら

で、70通りと計算できます。

今回求めたい道の本数の総数は、この数値を利用します。

ただ、この70通りの中には、条件を満たさない通り方も含まれているので、それを差し引く必要があります。

求められる条件が「y≦ｘをつねに保ちながら」ですので、差し引く場合とは、その余事象である「y＞xとなる場所を通る」場合のことです。
問題の性質上、格子点を通っていくことを考え、これを言い換えると、「y≧x＋1を通る」となります。

たとえば、下の図のオレンジ色で表示された通り方は、その一例です。

赤のラインを越えてはいけなかったので、この方法は差し引かなければならない方のケースです。

そのようなケースの場合の数を計算する方法として、まずy＝x＋1と最初にぶつかる点をＰとして、ＡからＰまでのルートを、直線y=x+1に関して対称移動させることとします。出発点である点Aが対称移動した点をA’とします。A’の座標は(-1,1)となります。

上の図では、点Aから点Pまでの本来の移動ルートをオレンジ色の点線としています。

その部分が対称移動されたルートが、A’からPまでのオレンジ色の実線部分と変わります。この元のルートと対称移動されたルートは1対1の対応となります。

それを考えると、触れてはならないy=x+1を通り、点Aから点Bまでを行く最短経路は、点A’から点Bまでの最短経路と総数が一致するのです。それは、点A’と点Bの2点は、直線y=x+1に関して互いに反対側にあるため、点A’から点Bへ移動する際は、必ず直線y=x+1と交わるからです。

したがって、点Aから点Bへの最短経路のうち、y>xを通ってしまう通り方は、点A’から点Bへの最短経路の総数となるので、それは₈C₃通りです。

ゆえに、y≦xの部分を通る最短経路の総数は

で、14通りとなります。

この場合、カタラン数を使って計算すると、最短経路の数は次のように求められます。

計算結果が一致しますね。

2-2.定理②　母関数で漸化式を解く

母関数とは数列を一つの式で表現するための関数を指します。

母関数を使ったカタラン数の導き方もあります。ここで説明します。
まず、母関数f(x)を次のように定義します：

ここで、C_nはカタラン数、xは変数です。

カタラン数には次のような漸化式が存在します。

この母関数を使って漸化式を解くと、カタラン数の一般項が得られます。具体的には、次のように計算します。

{f(x)}²におけるxⁿの係数はとなることに注意をすると

さらに、

3.カタラン数が活用できる問題例

カタラン数は、最短経路問題以外にも様々な問題で活用されます。以下に、その具体例をいくつか紹介します。
ここでポイントとなるのが、

を満たすことが、カタラン数を活用できる状態であるということです。

3-1.最短経路の場合の数

前述しましたように、縦横nマスの碁盤目状の道があって、対角線y≦xの領域しか通れないような最短経路の本数は、n番目のカタラン数C_nと一致します。

3-2.トーナメントのパターン数

n+1人で行われるトーナメントのトーナメント表の作り方は、n番目のカタラン数C_nになります。

これは、トーナメント表の作成がカタラン数の規則性に従っているためです。具体的な例を以下に示します。

• n+1=2人の場合：1試合（C₁=1）
• n+1=3人の場合：2試合（C₂=2）
• n+1=4人の場合：5試合（C₃=5）
• n+1=5人の場合：14試合（C₄=14）

このように、トーナメントの参加者数が増えるにつれて、トーナメント表のパターン数もカタラン数に従って増加します。これにより、トーナメント表の作成方法を効率的に計算できます。

一般には、次の考え方となります。
n+1人でトーナメントを行うときの試合の組み合わせの総数をa_nとします。
これがカタラン数を表すことが知られています。これを証明します。

n+2人でトーナメントを行う際、左側のトーナメントにi+1人、右側のトーナメントにn-i+1人がいるとします。
このとき、左右両サイドでのトーナメントの組み方はそれぞれa_i通りとa_n-i通りとなります。

この場合の左右合わせたトーナメントの試合の総数はa_ia_n-i通りであり、このiの値を0からnまで変化させた数値の総計が求める試合数であり、これはカタラン数を表します。

3-3.多角形を三角形によって分割する方法の数

へこんでいないn+2角形の対角線をn-1本引いて三角形に分割する方法の数は、n番目のカタラン数C_nになります。これは、多角形の分割がカタラン数の規則性に基づいているためです。具体的な例を以下に示します。

• 4角形（四角形）の場合：2通り（C₂=2）
• 5角形の場合：5通り（C₃=5）
• 6角形の場合：14通り（C₄=14）

このように、多角形を三角形に分割する方法の数は、カタラン数に基づいて計算されます。これにより、複雑な多角形の分割方法を効率的に求めることができます。

4．カタラン数を使う問題にチャレンジ！

4-1.最短経路を求める問題

【例題1】
xy平面上で格子状の道があり、原点を学校、(7,7)を家とする。このとき以下の問いに答えなさい。

（1）学校から家まで帰る最短経路の数は何通りか？
(2)y>xが工事中のため通れないとき、家に帰るまでの最短経路の数は何通りか？

 

【解答・解説】
（1）縦横合計14回進むうち、7回横に進まなければならないので、
₁₄C₇=3432（通り）
（2）カタラン数が使える状況であるため、n=7を代入する
C₇＝₁₄C₇/(7+1)＝429通り

4-2.トーナメントのパターン数を求める問題

【例題2】
あなたは高校サッカーの大会の運営である。出場高校数が6校とき、トーナメント表は合計で何パターン作れるか答えなさい。なお、シードの個数に限りはないものとする。

【解答・解説】
6=5+1なので、n=5のときのカタラン数と等しい。したがって、
C₅=₁₀C₅/(5+1)=42（通り）

4-3.多角形の対角線を結んで三角形に分割する方法の数を求める問題

【例題3】
へこんでいない7角形の対角線を4本結び、三角形に分割する方法は何通りあるか？

【解答・解説】
n=5のときのカタラン数と一致するので、
C₅=₁₀C₅/(5+1)=42（通り）

まとめ

カタラン数は、場合の数の問題や最短経路問題、トーナメントのパターン数、多角形の分割方法など、様々な数学の問題に応用できる強力なツールです。

その一般項の導き方や具体的な活用例を理解することで、数学の試験対策として大いに役立ちます。この記事を通してカタラン数の魅力を感じ、様々な問題に応用してみてください。

これをきっかけに、数学の問題をより効率的に解くことができるようになるでしょう。