カタロニア語の数字

カタラン数は、さまざまな計数問題に現れる自然数の列であり、多くの場合、再帰的に定義されたオブジェクトが関係します。カタラン数はウジェーヌ・カタランにちなんで名付けられましたが、1730年代にミンガトゥによって発見されていました。

n番目のカタラン数は、中心二項係数を使って次の ように直接表すことができます。

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\text{for }}n\geq 0.}$

n = 0, 1, 2, 3, ...の最初のカタラン数は

1、1、2、5、14、42、132、429、1430、4862、16796、58786、... （ OEISの配列A000108）。

C _nの別の表現は次のようになる。

${\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}}$のために${\displaystyle n\geq 0\,,}$

これは、 であるため、上記の式と同等です。この式は、C _{n が}整数であることを示していますが、これは、最初に示された式からはすぐには明らかではありません。この式は、式の正しさを証明するための基礎となります。 ${\displaystyle {\tbinom {2n}{n+1}}={\tfrac {n}{n+1}}{\tbinom {2n}{n}}}$

もう一つの表現は

${\displaystyle C_{n}={\frac {1}{2n+1}}{2n+1 \choose n}\,,}$

これはサイクル補題の観点から直接解釈することができます。以下を参照してください。

カタラン数は再帰関係を満たす

${\displaystyle C_{0}=1\quad {\text{および}}\quad C_{n}=\sum _{i=1}^{n}C_{i-1}C_{ni}\quad {\text{n>0の場合}$

そして

${\displaystyle C_{0}=1\quad {\text{かつ}}\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}\quad {\text{n>0の場合}$

漸近的に、カタラン数は 、 n番目のカタラン数と右側の式の商がn が無限大に近づくにつれて 1 に近づく という意味で、増加します。 $${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}\,,}$$

これは、中心二項係数の漸近的成長、のスターリング近似、または生成関数を使用することによって証明できます。 ${\displaystyle n!}$

カタロニア数C _{n の}うち奇数となるのは、n = 2 ^k − 1となる数だけです。それ以外はすべて偶数です。素数となるカタロニア数は、C ₂ = 2とC ₃ = 5だけです。^[1]より一般的には、素数p がC _{n を}割り切る重複度は、まずn + 1 をp基数で表すことで決定できます。p = 2の場合、重複度は 1 のビットの数から 1 を引いた値です。p が奇数の素数の場合、( p + 1) / 2より大きいすべての桁を数えます。また、最終桁でない限り、 ( p + 1) / 2に等しい桁も数えます。最終桁でない場合は、 ( p − 1) / 2に等しい桁を数え、次の桁を数えます。^[2]最後の桁が5でない奇数カタロニア数は、 C ₀ = 1、C ₁ = 1、C ₇ = 429、C ₃₁、C ₁₂₇、C ₂₅₅の5つだけである。n = 2 ^k − 1のときの奇数カタロニア数C _{n は}、 n + 1が最下位桁を除いて0、1、2のみを含む5進表現である場合、最後の桁が5にならない。最下位桁は3になることもある^。[3]

カタラン数は整数表現を持つ^{[4] [5]}

${\displaystyle C_{n}={\frac {1}{2\pi }}\int _{0}^{4}x^{n}{\sqrt {\frac {4-x}{x}}}\,dx\,={\frac {2}{\pi }}4^{n}\int _{-1}^{1}t^{2n}{\sqrt {1-t^{2}}}\,dt.}$

すると、すぐに が得られます。 ${\displaystyle \sum _{n=0}^{\infty }{\frac {C_{n}}{4^{n}}}=2}$

これには単純な確率的解釈があります。0 から始まる整数線上のランダム ウォークを考えてみましょう。-1 を「トラップ」状態とします。つまり、ウォーカーが -1 に到達したら、そこにとどまります。ウォーカーは、1、3、5、7... の時点でトラップ状態に到達できます。ウォーカーがトラップ状態に到達する方法の数はです。1D ランダム ウォークは再帰的であるため、ウォーカーが最終的に -1 に到達する確率は です。 ${\displaystyle 2k+1}$${\displaystyle C_{k}}$${\displaystyle \sum _{n=0}^{\infty }{\frac {C_{n}}{2^{2n+1}}}=1}$

組合せ論にはカタラン数で解ける数え上げ問題が数多くあります。組合せ論者Richard P. Stanleyの著書Enumerative Combinatorics: Volume 2には、カタラン数の 66 通りの解釈を説明する演習問題集が含まれています。以下に、 C ₃ = 5およびC ₄ = 14の場合の例を示します。

• C _{n は}長さ2 nのDyck 語^[6]の数です。Dyck 語はn 個のX とn個の Yで構成される文字列で、文字列の最初のセグメントには Y が X より多く含まれません。たとえば、長さ 6 までの Dyck 語は次のとおりです。

• シンボル X を開き括弧、Y を閉じ括弧として再解釈すると、C _{n は}正しく一致するn組の括弧を含む式の数を数えます。

• C _{n は}、 n + 1 個の因数を完全に括弧で囲むことができる異なる方法の数です（または、行列連鎖乗算問題のように、二項演算子のn 回の適用を関連付ける 方法の数です）。たとえば、 n = 3の場合、4 つの因数には次の 5 つの異なる括弧があります。

• 二項演算子の連続的な適用は、各葉にa、b、c、dというラベルを付けることによって、完全な二分木で表すことができます。したがって、C _{n は}n + 1 個の葉を持つ完全な二分木の数、または同等に、合計n 個の内部ノードを持つ完全な二分木の数になります。

• C _{n は}、 n + 1 個の頂点を持つ非同型順序木（または平面木）の数です。 ^[7]一般的な木を二分木としてエンコードする方法を参照してください。たとえば、 C _{n は}、自然言語処理における文の可能な構文解析木の数です
• C _{n は、} n × n の正方形セルを持つグリッドのエッジに沿った、対角線より上を通らない単調な格子パスの数です。単調なパスとは、左下隅から始まり、右上隅で終わり、右または上向きのエッジのみで構成されるパスです。このようなパスを数えることは、Dyck ワードを数えることと同じです。X は「右へ移動」、Y は「上へ移動」を表します。

次の図はn = 4の場合を示しています。

これはカタロニア語の要素を列の高さでリストすることで表すことができます。^[8]

• n + 2辺の凸多角形は、交差しない線分で頂点を結ぶことによって三角形に分割できます(多角形の三角形分割の一種)。形成される三角形の数はnで、これを実現できる異なる方法の数はC _nです。次の六角形は、 n = 4の場合を示しています。

• C _{n は}、{1, ..., n }のスタックソート可能な順列の数です。順列wがスタックソート可能と呼ばれるのは、 S ( w ) = (1, ..., n )の場合です。ここで、 S ( w ) は次のように再帰的に定義されます。w = unv と書きます。ここで、 nはwの最大要素で、 uとv はより短いシーケンスです。また、 S ( w ) = S ( u ) S ( v ) nと設定します。ここで、 Sは 1 要素シーケンスの単位元です。
• C _{n は}、順列パターン 123 (または、長さ 3 の他のパタ​​ーンのいずれか)を回避する{1, ..., n }の順列の数です。つまり、3 項増加部分列を持たない順列の数です。 n = 3の場合、これらの順列は 132、213、231、312、および 321 です。 n = 4 の場合、これらの順列は 1432、2143、2413、2431、3142、3214、3241、3412、3421、4132、4213、4231、4312、および 4321 です。
• C _{n は}、集合{1, ..., n }の非交差分割の数です。さらに、 C _nがn番目のベル数を超えることはありません。 C _{n は}、すべてのブロックのサイズが 2 である集合{1, ..., 2 n }の非交差分割の数でもあります
• C _{n は}、高さnの階段形状をn 個の長方形でタイル張りする方法の数です。対角線を横切ってエッジのみを見ると、完全な二分木が得られます。次の図は、 n = 4の場合を示しています。

• C _{n は}、 n 回の上昇ストロークとn 回の下降ストロークがすべて水平線より上にある「山脈」を形成する方法の数です。山脈の解釈では、山々が地平線より下に下がることはありません。

• C _{n は}、図が 2 行n列の長方形である標準的なヤングの図の数です。言い換えると、 1、2、...、2 n の数字を 2 行n列の長方形に並べる方法の数で、各行と各列は増加します。したがって、式はフック長さの公式の特殊なケースとして導出できます。

123 124 125 134 135
456 356 346 256 246

• ${\displaystyle C_{n}}$は、で始まり、または ずつ増加するか、任意の数だけ減少する（少なくとも まで）長さnのシーケンスの数です。これらは です。Dyck パスから、カウンタを0から開始します。X はカウンタを1増やし、Y はカウンタを1減らします。X のみの値を記録します。ベル数の同様の表現と比較すると、のみが欠落しています。${\displaystyle 1}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle n=4}$${\displaystyle 1234,1233,1232,1231,1223,1222,1221,1212,1211,1123,1122,1121,1112,1111}$${\displaystyle 1213}$

この式がなぜ成り立つのかを説明する方法はいくつかある。

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}}$

は、上記の組み合わせの問題を解決します。以下の最初の証明では、生成関数を使用します。その他の証明は、全単射の証明の例です。つまり、正しい式に到達するために、文字通り何らかのオブジェクトのコレクションを数える必要があります。

まず、上に挙げたすべての組み合わせ問題は、セグナー^[9]の 再帰関係を満たすことに気づく。

${\displaystyle C_{0}=1\quad {\text{かつ}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{ni}\quad {\text{n\geq 0の場合}$

例えば、長さが2以上のすべてのDyck語wは、次のように一意に表すことができます。

w = X w ₁ Y w ₂

Dyck ワードw ₁とw ₂ (空の場合もある) を持つ。

カタラン数の 生成関数は次のように定義される。

${\displaystyle c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}.}$

上記の再帰関係は、生成関数の形で次の関係式によって要約できる。

${\displaystyle c(x)=1+xc(x)^{2};}$

言い換えれば、この式は、両辺をべき級数に展開することによって漸化式から導かれる。一方で、漸化式はカタラン数を一意に決定する。他方、xc ² − c + 1 = 0をcの二次方程式として解釈し、二次方程式の公式を使用すると、生成関数関係を代数的に解くことができ、2つの解の可能性が得られる。

${\displaystyle c(x)={\frac {1+{\sqrt {1-4x}}}{2x}}}$  または  。${\displaystyle c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}}$

2つの可能性のうち、2番目を選ぶ必要があるのは、2番目だけが

${\displaystyle C_{0}=\lim _{x\to 0}c(x)=1}$。

平方根項は二項級数を使ってべき級数として展開できる。

$${\displaystyle {\begin{aligned}1-{\sqrt {1-4x}}&=-\sum _{n=1}^{\infty }{\binom {1/2}{n}}(-4x)^{n}=-\sum _{n=1}^{\infty }{\frac {(-1)^{n-1}(2n-3)!!}{2^{n}n!}}(-4x)^{n}\\&=-\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n-1)!!}{2^{n+1}(n+1)!}}(-4x)^{n+1}=\sum _{n=0}^{\infty }{\frac {2^{n+1}(2n-1)!!}{(n+1)!}}x^{n+1}\\&=\sum _{n=0}^{\infty }{\frac {2(2n)!}{(n+1)!n!}}x^{n+1}=\sum _{n=0}^{\infty }{\frac {2}{n+1}}{\binom {2n}{n}}x^{n+1}\,.\end{aligned}}}$$ したがって、 $${\displaystyle c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}x^{n}\,.}$$

n × nグリッドの対角線上で始まり、対角線上で終わるパスの数を数えます。このようなパスにはすべて、 n個の右ステップとn個の上ステップがあります。2 nステップのうちどれを上または右にするかを選択できるため、このタイプの単調パスは合計で存在します。悪いパスは、主対角線を横切り、次の高い対角線に接します (図では赤)。 ${\displaystyle {\tbinom {2n}{n}}}$

次に、赤い点線で示されているように、高い対角線の後のパスの部分がその対角線を中心に反転されます。これにより、すべての右ステップが上ステップに、またその逆の順序で入れ替わります。パスの反転されていないセクションでは、上ステップが右ステップより 1 つ多いため、不良パスの残りのセクションでは、右ステップが上ステップより 1 つ多くなります。パスのこの部分が反転されると、上ステップが右ステップより 1 つ多くなります。

まだ2 nステップあるので、 n + 1の上りステップとn − 1 の右ステップがあります。したがって、 ( n、n )に到達する代わりに 、反射後のすべての不良パスは( n − 1、n + 1)で終了します。( n − 1) × ( n + 1)グリッド内のすべての単調パスはより高い対角線と交差し、反射プロセスは可逆的であるため、反射は元のグリッドの不良パスと新しいグリッドの単調パスの間の一対一になります。

したがって、不良パスの数は次のようになります。

${\displaystyle {n-1+n+1 \choose n-1}={2n \choose n-1}={2n \choose n+1}}$

カタランパス（つまり良いパス）の数は、元のグリッドの単調パスの総数から悪いパスの数を除いたものとなる。

${\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}={\frac {1}{n+1}}{2n \choose n}.}$

Dyck ワードでは、n 個のX とn 個のY の (非 Dyck) シーケンスから開始し、Dyck 条件に違反する最初の Y の後の X と Y をすべて交換します。この Y の後には、X の数より Y の数がちょうど 1 つ多いことに注意してください。

この全単射の証明は、 C _nの式の分母に現れる 項n + 1に対する自然な説明を提供します。この証明の一般化されたバージョンは、Rukavicka Josef (2011) の論文に記載されています。^[10]

単調なパスが与えられた場合、パスの超過は対角線の上にある垂直エッジの数として定義されます。たとえば、図 2 では、対角線の上にあるエッジは赤でマークされているため、このパスの超過は 5 です。

超過がゼロではない単調なパスが与えられた場合、次のアルゴリズムを適用して、超過が最初のパスより 1少ない新しいパスを構築します。

• 左下から始めて、対角線の上を通過するまでパスをたどります。
• 再び対角線に触れるまで経路をたどり続けます。到達した最初のエッジをXで表します。
• X の前に発生するパスの部分とX の後に発生する部分を交換します。

図 3 では、黒い点はパスが最初に対角線と交差する点を示しています。黒いエッジはXで、赤い部分の最後の格子点を右上隅に、緑の部分の最初の格子点を左下隅に配置し、それに応じて X を配置して、2 番目の図に示すように新しいパスを作成します。

超過は3から2に減少しました。実際、アルゴリズムを適用すると、どのパスでも超過が1減少します。これは、アルゴリズムを適用したときに、対角線から始まる最初の垂直ステップ (黒い点でマークされたポイント) が、対角線の上から下に変化する唯一の垂直エッジであるためです。他のすべての垂直エッジは、対角線の同じ側にとどまります。

このプロセスは可逆的であることがわかります。つまり、超過がn未満の任意のパスPに対して、アルゴリズムを適用したときにP を生成するパスが 1 つだけ存在します。実際、元々は対角線で終わる最初の水平ステップであった(黒い) エッジX は、対角線で始まる最後の水平ステップになっています。または、元のアルゴリズムを逆にして、対角線の下を通過する最初のエッジを探します。

これは、超過パスの数nは超過パスの数n − 1に等しく、超過パスの数n − 2に等しく、以下同様に 0 まで続くことを意味します。言い換えると、すべての単調パスの集合を、 0 からnまでの可能性のある超過に対応するn + 1 個の均等なサイズのクラスに分割したことになります。単調パスが存在するため、目的の式が得られます。${\displaystyle \textstyle {2n \choose n}}$${\displaystyle \textstyle C_{n}={\frac {1}{n+1}}{2n \choose n}.}$

図 4 は、 n = 3の状況を示しています 。20 個の可能な単調なパスのそれぞれが、表のどこかに表示されます。最初の列には、対角線より完全に上にある、超過 3 のすべてのパスが表示されます。右側の列には、アルゴリズムを連続して適用した結果が表示され、超過は一度に 1 単位ずつ減少します。行は 5 つあり、つまり C ₃ = 5で、最後の列には対角線より高くないすべてのパスが表示されます。

Dyck 語を使用して、 のシーケンスから始めます。を初期サブシーケンスを等式にする最初のXとし、シーケンスを として構成します。新しいシーケンスは です。 ${\displaystyle \textstyle {\binom {2n}{n}}}$${\displaystyle X_{d}}$${\displaystyle (F)X_{d}(L)}$${\displaystyle LXF}$

この証明では、カタラン数の三角測量定義を使用して、 C _nとC _{n +1}の関係を確立します。

n + 2辺と三角形分割を持つ多角形Pが与えられた場合、その辺の 1 つを底辺としてマークし、合計2 n + 1辺のうちの 1 つを方向付けます。与えられた底辺に対して、 (4 n + 2) C _n通りのマークされた三角形分割が存在します。

n + 3辺を持つ多角形Qと (異なる) 三角形分割が与えられた場合、再びその辺の 1 つを底辺としてマークします。底辺以外の辺の 1 つ (三角形の内側の辺ではない) をマークします。与えられた底辺に対して、このようなマークされた三角形分割は( n + 2) C _{n + 1}通りあります。

これら 2 つのマークされた三角形分割の間には、単純な一対一の関係があります。つまり、辺がマークされているQの三角形を折りたたむ(2 つの方法で、底辺を折りたたむことができない 2 つの方法を減算する) か、逆に、Pの向き付けられた辺を三角形に拡張して、その新しい辺をマークすることができます。

したがって

${\displaystyle (4n+2)C_{n}=(n+2)C_{n+1}}$。

書く${\displaystyle \textstyle {\frac {4n-2}{n+1}}C_{n-1}=C_{n}.}$

なぜなら

${\displaystyle (2n)!=(2n)!!(2n-1)!!=2^{n}n!(2n-1)!!}$

我々は持っています

${\displaystyle {\frac {(2n)!}{n!}}=2^{n}(2n-1)!!=(4n-2)!!!!.}$

再帰を適用すると結果が得られます。 ${\displaystyle C_{0}=1}$

この証明はカタラン数のダイク語解釈に基づいており、 n組の括弧を正しくマッチさせる方法の数も同様である。正しい文字列（空でもよい）をcで表し、その逆をc'で表す。任意のc はに一意に分解できるため、 の可能な長さを合計すると、すぐに再帰定義が得られる。 ${\displaystyle C_{n}}$${\displaystyle c=(c_{1})c_{2}}$${\displaystyle c_{1}}$

${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0}$。

b を長さ2 nのバランスのとれた文字列とします。つまり、b には と が同数含まれているので です。バランスのとれた文字列は または に一意に分解することもできるのでです。 ${\displaystyle (}$${\displaystyle )}$${\displaystyle \textstyle B_{n}={2n \choose n}}$${\displaystyle (c)b}$${\displaystyle )c'(b}$

${\displaystyle B_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}.}$

正しくない（カタルーニャ語以外の）バランスの取れた文字列は で始まり、残りの文字列はより1つ多いので、 ${\displaystyle c)}$${\displaystyle (}$${\displaystyle )}$

${\displaystyle B_{n+1}-C_{n+1}=\sum _{i=0}^{n}{2i+1 \choose i}C_{n-i}}$

また、定義から次のようになります。

${\displaystyle B_{n+1}-C_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}-\sum _{i=0}^{n}C_{i}\,C_{n-i}=\sum _{i=0}^{n}(2B_{i}-C_{i})C_{n-i}.}$

したがって、これはすべてのnに対して成り立つので、

${\displaystyle 2B_{i}-C_{i}={\binom {2i+1}{i}}}$

${\displaystyle C_{i}=2B_{i}-{\binom {2i+1}{i}}}$

${\displaystyle C_{i}=2{\binom {2i}{i}}-{\binom {2i+1}{i}}}$

${\displaystyle C_{i}={\frac {1}{i+1}}{\binom {2i}{i}}}$

この証明はカタラン数のダイク語解釈に基づいており、ドヴォレツキーとモツキンのサイクル補題を使用している。 ^{[11] [12]}

左から右に読んで、X の数が常に Y の数より厳密に大きい場合、X と Y のシーケンスは優勢であると呼びます。サイクル補題^[13]は、 である任意のXと Y のシーケンスには、正確に優勢な円シフトが存在すると述べています。これを確認するには、与えられたX と Y のシーケンスを円状に配置します。XY ペアを繰り返し削除すると、X が正確に 個残ります。これらの各 X は、何かが削除される前に、優勢な円シフトの始まりでした。たとえば、 を考えます。このシーケンスは優勢ですが、その円シフト、、およびはどれも優勢ではありません。 ${\displaystyle m}$${\displaystyle n}$${\displaystyle m>n}$${\displaystyle m-n}$${\displaystyle m+n}$${\displaystyle m-n}$${\displaystyle {\mathit {XXYXY}}}$${\displaystyle {\mathit {XYXYX}}}$${\displaystyle {\mathit {YXYXX}}}$${\displaystyle {\mathit {XYXXY}}}$${\displaystyle {\mathit {YXXYX}}}$

文字列がX とYの Dyck 語である場合、かつその場合のみ、Dyck 語の前に X を追加するとX とY の支配シーケンスが生成されるため、後者を数える代わりに前者を数えることができます。特に、のとき、支配的な循環シフトは 1 つだけです。XとY のシーケンスが正確に1つ存在します。これらのそれぞれについて、循環シフトの 1 つだけが支配的です。したがって、支配的なX とYの明確なシーケンスが存在し、それぞれが 1 つの Dyck 語に対応します。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle m=n+1}$${\displaystyle \textstyle {2n+1 \choose n}}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle 2n+1}$${\displaystyle \textstyle {\frac {1}{2n+1}}{2n+1 \choose n}=C_{n}}$${\displaystyle n+1}$${\displaystyle n}$

n × nハンケル行列の( i , j )要素がカタラン数C _{i + j −2である}場合 、 nの値に関係なく行列式は 1 になり ます。たとえば、n = 4の場合、

${\displaystyle \det {\begin{bmatrix}1&1&2&5\\1&2&5&14\\2&5&14&42\\5&14&42&132\end{bmatrix}}=1.}$

さらに、インデックスが「シフト」されて( i , j )エントリがカタラン数C _{i + j −1}で埋められる 場合、 nの値に関係なく、行列式は 1 のままです。たとえば、n = 4の場合、

${\displaystyle \det {\begin{bmatrix}1&2&5&14\\2&5&14&42\\5&14&42&132\\14&42&132&429\end{bmatrix}}=1.}$

これら 2 つの条件を組み合わせることで、カタロニア語の数字が一意に定義されます。

カタラン-ハンケル行列に特有のもう1つの特徴は、2から始まるn × nの部分行列に行列式n + 1があることです。

${\displaystyle \det {\begin{bmatrix}2\end{bmatrix}}=2}$

${\displaystyle \det {\begin{bmatrix}2&5\\5&14\end{bmatrix}}=3}$

${\displaystyle \det {\begin{bmatrix}2&5&14\\5&14&42\\14&42&132\end{bmatrix}}=4}$

${\displaystyle \det {\begin{bmatrix}2&5&14&42\\5&14&42&132\\14&42&132&429\\42&132&429&1430\end{bmatrix}}=5}$

などなど。

カタラン数列は、多角形を三角形に分割する方法の多様さに興味を持っていたレオンハルト・オイラーによって 18 世紀に説明されました。この数列は、ハノイの塔パズルの探求中に括弧付きの式との関連性を発見したウジェーヌ・シャルル・カタランにちなんで名付けられました。ダイク語の反射カウントトリック (2 番目の証明) は、1887 年に デジレ・アンドレによって発見されました。

「カタロニア数字」という名前はジョン・リオーダンに由来する。^[14]

1988年、カタロニア数列が1730年までにモンゴルの数学者ミンガントによって中国で使用されていたことが明らかになりました。 ^{[15] [16]}それは彼が著書『円周の正確な比を得るための迅速な方法』を書き始めたときであり、それは彼の弟子である陳継新によって1774年に完成されましたが、60年後に出版されました。ピーター・J・ラーコム（1999）は、1700年代初頭に3つの無限級数を中国にもたらしたピエール・ジャルトゥーへの刺激を含め、ミンガントの研究の特徴のいくつかを概説しました。

たとえば、ミンはカタラン数列を使用して、との級数展開を で表現しました。 ${\displaystyle \sin(2\alpha )}$${\displaystyle \sin(4\alpha )}$${\displaystyle \sin(\alpha )}$

カタラン数は、ベルトランの投票定理の特殊なケースとして解釈できます。具体的には、n + 1票の候補者 A がn票の候補者 B をリードする方法の数です。 ${\displaystyle C_{n}}$

2 パラメータの非負整数列は カタラン数の一般化です。これらは、 Ira Gesselによれば、スーパーカタラン数と呼ばれます。これらは、スーパーカタラン数と呼ばれることもある シュレーダー-ヒッパルコス数と混同しないでください。${\displaystyle {\frac {(2m)!(2n)!}{(m+n)!m!n!}}}$

の場合、これは通常のカタラン数のちょうど2倍であり、 の場合、これらの数は簡単な組み合わせ記述を持ちます。しかし、他の組み合わせ記述はと の場合のみ知られており^[17]、^[18] 、一般的な組み合わせ解釈を見つけることは未解決の問題です。 ${\displaystyle m=1}$${\displaystyle m=n}$${\displaystyle m=2,3}$${\displaystyle 4}$

セルゲイ・フォミンとネイサン・リーディングは、任意の有限結晶学コクセター群に関連付けられた一般化されたカタラン数、すなわち群の完全に可換な元の数を与えた。関連付けられたルートシステムに関して言えば、それは正のルートの半集合における反鎖（または順序イデアル）の数である。古典的なカタラン数は、タイプ のルートシステムに対応する。古典的な再帰関係は一般化される：コクセター図のカタラン数は、そのすべての最大の適切な部分図のカタラン数の合計に等しい。^[19]${\displaystyle C_{n}}$${\displaystyle A_{n}}$

カタラン数はハウスドルフモーメント問題の一種の解である。^[20]

カタランk畳み込み（k = m）は次のように表される。^[21]

${\displaystyle \sum _{i_{1}+\cdots +i_{m}=n \atop i_{1},\ldots ,i_{m}\geq 0}C_{i_{1}}\cdots C_{i_{m}}={\begin{cases}{\dfrac {m(n+1)(n+2)\cdots (n+m/2-1)}{2(n+m/2+2)(n+m/2+3)\cdots (n+m)}}C_{n+m/2},&m{\text{ even,}}\\[5pt]{\dfrac {m(n+1)(n+2)\cdots (n+(m-1)/2)}{(n+(m+3)/2)(n+(m+3)/2+1)\cdots (n+m)}}C_{n+(m-1)/2},&m{\text{ odd.}}\end{cases}}}$

• スタンリー、リチャード P. (2015)、「カタロニア語の数」。ケンブリッジ大学出版局、ISBN 978-1-107-42774-7。 
• コンウェイとガイ（1996）『数の書』ニューヨーク：コペルニクス、pp.96-106。
• ガードナー、マーティン（1988）、タイムトラベルとその他の数学的驚異、ニューヨーク：WHフリーマンアンドカンパニー、pp. 253–266（第20章）、Bibcode：1988ttom.book.....G、ISBN 0-7167-1924-X
• コシー、トーマス（2008）、カタロニア語の数とその応用、オックスフォード大学出版局、ISBN 978-0-19-533454-8
• Koshy、Thomas、Zhenguang Gao (2011)「カタラン数のいくつかの割り切れる性質」、Mathematical Gazette 95:96–102。
• Larcombe, PJ (1999). 「18 世紀中国におけるカタラン数の発見」(PDF) . Mathematical Spectrum . 32 : 5–7.
• スタンレー、リチャード P. (1999)、列挙的組合せ論。第 2 巻、ケンブリッジ高等数学研究、第 62 巻、ケンブリッジ大学出版局、ISBN 978-0-521-56069-6、MR  1676282
• Egecioglu, Omer (2009)、カタラン-ハンケル行列式評価(PDF)
• ゲオルギチウク、イリーナ; オレロウィッツ、ギドン (2020)、第 3 種および第 4 種の超カタラン数、arXiv : 2008.00133

• スタンレー、リチャード P. (1998)、列挙的組合せ論第 2 巻のカタロニア語補遺(PDF)
• Weisstein、Eric W.「カタラン数」。MathWorld。
• デイビス、トム: カタロニア語の数字。さらに例を挙げます。
• Wolfram Demonstrations Project の「3 つのカタラン数解釈の同値性」[1]
• Wikiversity のパーティション関連数三角形に関する学習教材