カタラン数とは？
かたらんすう
カタラン数とは、組み合わせ論に現れる自然数の数列で、様々な数え上げ問題に共通して登場する重要な数です。
カタラン数（Catalan numbers）は、組み合わせ数学において非常に多くの異なる数え上げ問題の答えとして現れる自然数の数列です。19世紀のベルギーの数学者ウジェーヌ・カタランにちなんで命名されました。
n番目のカタラン数 Cₙ は次の公式で計算できます。Cₙ = (2n)! / ((n+1)! · n!) = C(2n,n) / (n+1)。最初の数項を並べると 1, 1, 2, 5, 14, 42, 132, 429, 1430, … となります。
カタラン数が答えとなる問題は非常に多岐にわたり、代表的なものには以下があります。
- n+2角形を三角形に分割する方法の数
- n組の括弧の正しい並べ方の数
- 2n個の要素を持つ二分木の形の数
- 格子路において対角線を越えない経路の数
- n個の要素のスタックソート可能な順列の数
このように、一見まったく異なる問題が同じ数列で記述されるという点が、カタラン数の数学的な魅力です。コンピューターサイエンスのアルゴリズム設計や、構文解析（パーサーの設計）にも応用されています。組み合わせ論の入門から研究レベルまで、広く登場する重要な数列です。
使い方・例文
3組の括弧を正しく並べる方法（例：()()()、(())() など）は全部でカタラン数 C₃ = 5 通りあります。プログラムの括弧対応チェックなどを考える際に自然と現れます。
この用語をシェア
最終更新: