カタルーニャ語の数字

カタラン数は、様々な数え上げ問題に現れる自然数の数列であり、多くの場合、再帰的に定義された対象が関係する。ウジェーヌ・カタランにちなんで名付けられたが、実際には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}={\binom {2n}{n}}-{\binom {2n}{n+1}}\quad {\text{for }}n\geq 0\,,}$$ これは上記の式と同等です。${\textstyle {\binom {2n}{n+1}}={\frac {n}{n+1}}{\binom {2n}{n}}}$この式は、C _nが整数であることを示しており、これは最初に与えられた式からはすぐには明らかではありません。この式は、式の正しさを証明する基礎となります。

別の表現としては $${\displaystyle C_{n}={\frac {1}{2n+1}}{\binom {2n+1}{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。}$$

漸近的に、カタロニアの数は次のように増加する。 $${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}\,,}$$n番目のカタラン数と右辺の式の商が、n が無限大に近づくにつれて 1 に近づく という意味で。これは、中心二項係数の漸近的増加、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 ₂₅₅のみです。奇数のカタロニア数C _n ( n = 2 ^k − 1の場合) は、 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.}$$ すぐに $$\sum_{n=0}^{\infty}{\frac{C_{n}}{4^{n}}}=2.}$$

これは単純な確率論的解釈ができます。整数直線上のランダムウォークを考えます。出発点は0です。−1を「トラップ」状態とします。つまり、ウォーカーが−1に到達すると、そこに留まります。ウォーカーは時刻1、3、5、7、…でトラップ状態に到達する可能性があり、時刻2k +1でトラップ状態に到達する方法はCkです_。1次元ランダムウォークは再帰的であるため、ウォーカーが最終的に−1に到達する確率は $$\displaystyle \sum _{n=0}^{\infty }{\frac {C_{n}}{2^{2n+1}}}=1.}$$

組み合わせ論には、カタラン数によって解ける数え上げ問題が数多く存在します。組み合わせ論学者リチャード・P・スタンレーの著書『列挙的組み合わせ論：第2巻』には、カタラン数の66種類の異なる解釈を解説した演習問題が収録されています。以下に、C ₃ = 5およびC ₄ = 14の場合の例を示します。

• C _nは長さ2 nのDyck ワード^{[ 6 ]}の数です。Dyck ワードとは、 n個のX とn個の Yからなる文字列で、文字列のどの先頭セグメントも X の数より Y の数が多くありません。例えば、長さ 6 までの Dyck ワードは次のようになります。

• 記号 X を括弧の開始、Y を括弧の終了と再解釈すると、C _{n は、}正しく対応しているn組の括弧を含む式の数を数えます。たとえば、n = 3の場合、これらは次のようになります。

• 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個の正方形セルからなるグリッドの辺に沿って、対角線より上を通らない単調な格子経路の数です。単調な経路とは、左下隅から始まり、右上隅で終わり、すべて右方向または上方向を向いた辺で構成される経路のことです。このような経路を数えることは、ディック語を数えることと同じです。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は、図が 2 × n の長方形となる標準ヤング表の数です。言い換えれば、 1、2、...、2 nの数を、各行と各列が増加するように2 × n の長方形に配置する方法の数です。したがって、この式はフックの長さの公式の特殊な場合として導出できます。

123 124 125 134 135 456 356 346 256 246 

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

その公式がなぜ成り立つのかを説明する方法はいくつかある。 $${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}}$$ 上記に挙げた組み合わせ論的な問題を解決します。最初の証明では生成関数を使用しています。その他の証明は全単射証明の例であり、何らかのオブジェクトの集合を文字通り数えることで正しい式を導き出します。

第二の証明

( x , y ) = (0, 0)から始まり、 ( n , n )で終わり、単調で、直線y = xより上の点を含むパスを不良パスと呼びます。 (0, 0)から始まり、( n − 1, n + 1)で終わり、単調であるパスとの全単射を確立することにより、不良パスの数を数えます。

与えられた不良パスに対して、次のように反射パスを構築します。不良パス上で直線y = x + 1と交差する最初の点をPとします。 (0, 0)からPまでの不良パスが反射パスの始点となります。P から( n , n )までの不良パスのうち、直線y = x + 1 を横切って反射した部分が反射パスの残りの部分となります。例については図を参照してください。黒線は 2 つのパスで共有される点、点線の赤線は不良パスの残りの部分、実線の赤線は反射パスの残りの部分です。

これは全単射です。なぜなら、(0, 0)から( n − 1, n + 1)へのすべての単調パスは悪いパスから構成可能であり、すべての反射パスは一意の点Pを見つけることで一意に可逆であり、そのようなパスはすべてy = x + 1と交差する必要があるため、必ず存在するはずです。

反射経路のステップ数は( n − 1) + ( n + 1) = 2nです。経路は単調で、y = 0から始まりy = n + 1で終わるため、上方向のステップ数はn + 1です。

反射経路の数は、通常の方法で、全ステップに分配できる上向きステップの数を数えることによって数えることができます。${\textstyle {\binom {2n}{n+1}}}$、カタランパス（良いパス）の数は、元のグリッドの単調パスの総数から悪いパスの数を差し引くことによって得られます。

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

この証明は、ディック語を用いて言い換えることができる。まず、n個のXとn個のYからなる（ディック語ではない）シーケンスを用意し、ディック条件に違反する最初のY以降のすべてのXとYを入れ替える。

第三の証拠

この全単射の証明は、 C _nの公式の分母に現れる項n + 1に対する自然な説明を提供する。この証明の一般化されたバージョンは、Rukavicka (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 からnまでの可能な超過度に対応するn + 1 個の等しいサイズのクラスに分割しました。${\textstyle {\binom {2n}{n}}}$単調経路により、目的の式が得られます。 $${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}.}$$

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

Dyckの単語を使って、次のシーケンスから始めます。${\textstyle {\binom {2n}{n}}}$. X _{d を}、初期部分列を等号にする最初のXとし、数列を( F ) X _d ( L )と構成する。新しい数列はLXFである。

( i , j )の要素がカタラン数C _{i + j −2である}n × nハンケル行列の行列式は、 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.}$$

これら二つの条件を総合すると、カタルーニャの数字は独自に定義される。

カタラン・ハンケル行列に特有のもう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}$$

その他。

カタラン数列は、多角形を三角形に分割する異なる方法の数に興味を持っていたレオンハルト・オイラーによって1751年に記述されました。この数列は、ハノイの塔パズルを研究中に括弧付き式との関連性を発見したウジェーヌ・シャルル・カタランにちなんで名付けられました。ディック語の反射計数トリック（第2証明）は、 1887年にデジレ・アンドレによって発見されました。

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

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

例えば、ミンガントゥはカタラン数列を用いて級数展開を表現した。${\displaystyle \sin(2\alpha )}$そして${\displaystyle \sin(4\alpha )}$に関しては${\displaystyle \sin(\alpha )}$。

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

2つのパラメータを持つ非負整数の数列${\displaystyle {\frac {(2m)!(2n)!}{(m+n)!m!n!}}}$ これはカタラン数の一般化です。イラ・ゲッセルによれば、これらはスーパーカタラン数と呼ばれています。これらは、時にスーパーカタラン数と呼ばれるシュレーダー・ヒッパルコス数と混同してはなりません。

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

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

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

互いに素な正の整数rとsに対して、有理カタラン数は${\displaystyle {\frac {1}{r+s}}{\binom {r+s}{r}}}$(0,0)から( r , s )まで右方向と上方向に単位長さのステップを持つ格子経路のうち、線ry = sxを超えることのないものを数える。^{[ 21 ]}

カタランk重畳み込みは次のとおりです。

$${\displaystyle \sum _{i_{1}+\cdots +i_{k}=n \atop i_{1},\ldots ,i_{k}\geq 0}C_{i_{1}}\cdots C_{i_{k}}={\dfrac {k}{2n+k}}{\binom {2n+k}{n}}}$$

• スタンレー、リチャード P. (2015)、カタルーニャ語の数。ケンブリッジ大学出版局、ISBN 978-1-107-42774-7。
• コンウェイとガイ（1996）『数字の書』ニューヨーク：コペルニクス、 96-106頁。
• ガードナー、マーティン（1988）『タイムトラベルとその他の数学的困惑』ニューヨーク：WHフリーマン社、253～266ページ（第20章）、Bibcode：1988ttom.book.....G、ISBN  0-7167-1924-X
• Koshy, Thomas (2008), Catalan Numbers with Applications , Oxford University Press, 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-6MR 1676282​ 
• Egecioglu, Omer (2009),カタロニア・ハンケル行列式の評価(PDF)
• Gheorghiciuc, Irina; Orelowitz, Gidon (2020), Super-Catalan Numbers of the Third and Fourth Kind , arXiv : 2008.00133

• スタンレー、リチャード P. (1998)、列挙的組み合わせ論へのカタロニア語補遺、第 2 巻(PDF)
• ワイススタイン、エリック・W. 「カタラン数」 . MathWorld .
• デイビス、トム：カタロニア数字。さらに多くの例。
• Wolfram Demonstrations Project の「3 つのカタラン数解釈の等価性」
• Wikiversityにある分割関連の数三角形に関する学習教材