カタロニア語の数字

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

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

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$ の別の表現は次の通りである。

C_{n}={2n \choose n}-{2n \choose n+1}

のために

n\geq 0\,,

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

もう一つの表現は

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

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

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

C_{0}=1\quad {\text{and}}\quad C_{n}=\sum _{i=1}^{n}C_{i-1}C_{n-i}\quad {\text{for }}n>0

そして

C_{0}=1\quad {\text{and}}\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}\quad {\text{for }}n>0.

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

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

$カタラン数C n の$ うち奇数は $n = 2 k - 1$ となる数のみで、それ以外は偶数です。素数となるカタラン数は $C 2 = 2$ と $C 3 = 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 0 = 1$ 、 $C 1 = 1$ 、 $C 7 = 429$ 、 $C 31$ 、 $C 127$ 、 $C 255$ $のみである。n = 2$ $k$ $- 1$ $の$ 奇数カタラン数 $C n$ は、 $n$ $+ 1$ が5進表現で0、1、2のみを含む場合、末尾の数字が5にならない。ただし、最下位桁は3になる場合もある^。[3]

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

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…の時点でトラップ状態に到達する可能性があり、その時点でのトラップ状態に到達する方法の数はです。1次元ランダムウォークは再帰的であるため、歩行者が最終的に-1に到達する確率はです。 $2k+1$ $C_{k}$ $\sum _{n=0}^{\infty }{\frac {C_{n}}{2^{2n+1}}}=1$

組合せ論への応用

組合せ論には、カタラン数によって解が与えられる数え上げ問題が数多く存在します。組合せ論者リチャード・P・スタンリー著『Enumerative Combinatorics : Volume 2』には、カタラン数の66通りの解釈を解説した演習問題集が掲載されています。以下に、 $C$ $3$ $= 5$ と $C$ $4$ $= 14$ の場合を例に挙げ、その例を挙げます。

$C n$ $は長さ2$ $n$ のDyck 語^[6]の数です。Dyck 語とは、 $n$ 個の X と $n$ 個の Yからなる文字列で、文字列の最初の部分には Y の数が X の数より多くならないものです。例えば、長さ6までの Dyck 語は以下のとおりです。

- XY
- XXYY
- XYXY
- XXXYYY
- XYXXYY
- XYXYXY
- XXYYXY
- XXYXYY

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

（（（）））
（（）（））
（））（）
（）（（））
（）（）（）

$C n$ $は、 n + 1$ 個の因数を完全に括弧で囲む方法の数（または、行列連鎖乗算問題における二項演算子の $n回の適用を$ 関連付ける方法の数）です。 $例えば、 n$ $= 3$ の場合、4つの因数には以下の5つの異なる括弧の囲み方があります。

((ab)c)d
(a(bc))d
(ab)(cd)
a((bc)d)
a(b(cd))

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

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

次の図はn = 4 の

場合を示しています。

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

- [0,0,0,0]
- [0,0,0,1]
- [0,0,0,2]
- [0,0,1,1]
- [0,1,1,1]
- [0,0,1,2]
- [0,0,0,3]
- [0,1,1,2]
- [0,0,2,2]
- [0,0,1,3]
- [0,0,2,3]
- [0,1,1,3]
- [0,1,2,2]
- [0,1,2,3]

$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$ $は、{1, ..., n}$ の順列のうち、順列パターン 123（または長さ 3 の他のパターンのいずれか）を回避する $順列の数です。つまり、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 回の$ 下降ストロークがすべて水平線より上にあり、「山脈」を形成する方法の数です。山脈の解釈では、山々は決して地平線より下に下がることはありません。

山脈
$n=0:$	*	片道
$n=1:$	/\	片道
$n=2:$	/\ /\/\, / \	2つの方法
$n=3:$	\ \ /\ 0 0 /\/ \, 0 / 0 , / \/\, / , / \	5つの方法

$C n は$ 、図が2行 $n列の長方形となる$ 標準的なヤングの図の数です。言い換えれば $、1、2、\dots、2$ $n$ $の数を2行n$ 列の長方形に並べる方法の数であり、各行と各列は増加します。したがって、この式はフックの長さの公式の特別なケースとして導くことができます。

123 124 125 134 135456 356 346 256 246

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

式の証明

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

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

は、上記の組み合わせ問題を解きます。以下の最初の証明では、生成関数が用いられます。その他の証明は、全単射証明の例であり、ある種のオブジェクトの集合を文字通り数えて正しい式を導き出します。

最初の証明

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

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.

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

w = X w 1 Y w 2

Dyckワード $w 1$ と $w 2$ (空である可能性もある) 。

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

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

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

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

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

c(x)={\frac {1+{\sqrt {1-4x}}}{2x}}

または。

c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}

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

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

。

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

${\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}}$ したがって、 $c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}x^{n}\,.$

第二校正

で始まり、で終わり、単調で、直線より上に点を含むパスを悪いパスと呼びます。悪いパスの数は、で始まり、で終わり、単調であるパスと一対一の関係を確立することで数えます。 $(x,y)=(0,0)$ $(n,n)$ $y=x$ $(0,0)$ $(n-1,n+1)$

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

これは一対一です。なぜなら、からへのすべての単調なパスは不良パスから構築可能であり、すべての反射パスはと交差する必要があるため存在する必要がある唯一のポイントを見つけることによって一意に反転できるからです。 $(0,0)$ $(n-1,n+1)$ $P$ $y=x+1$

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

反射経路の数は、通常の方法で、上向きのステップが合計ステップ数にどれだけ分配されるかを数えることによって数えることができる。

{2n \choose n+1}

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

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

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

第三の証明

$この全単射的な証明は、 C$ $n$ の式の分母に現れる項 $n + 1$ を自然に説明する。この証明の一般化版は、Rukavicka Josef (2011) の論文に記載されている。^[10]

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

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

左下から始めて、対角線の上を通過するまでパスをたどります。
経路を辿り、対角線に再び接するまで進みます。到達した最初の辺を $Xで表します。$
$X$ の前に発生するパスの部分と $X$ の後に発生する部分を交換します。

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

超過度は $3から$ $2$ に減少しました。実際、このアルゴリズムでは、入力するパスごとに超過度が $1$ 減少します。これは、アルゴリズムを適用した際に、対角線から始まる最初の垂直ステップ（黒点でマークされた点）が、対角線の上側から下側に変化する唯一の垂直エッジであるためです。他のすべての垂直エッジは、対角線の同じ側に留まります。

図 4. 3×3 グリッド内のすべての単調パス。超過減少アルゴリズムを示しています。

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

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

$図4はn = 3$ の場合の状況を示しています。20通りの単調経路がそれぞれ表のどこかに現れています。最初の列は、対角線より完全に上に位置する、超過度が3であるすべての経路を示しています。右側の列は、アルゴリズムを連続的に適用した結果を示しており、超過度は1単位ずつ減少しています。行は5つ、つまり $C 3 = 5$ であり、最後の列は対角線より上に位置しないすべての経路を示しています。

Dyck語を用いて、から始まるシーケンスから始めます。を最初の部分シーケンスが等しくなる最初の $X$ とし、シーケンスをに設定します。新しいシーケンスはです。 $\textstyle {\binom {2n}{n}}$ $X_{d}$ $(F)X_{d}(L)$ $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$ の方向付けられたエッジを三角形に拡張して、その新しい辺をマークすることができます。

したがって

(4n+2)C_{n}=(n+2)C_{n+1}

。

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

なぜなら

(2n)!=(2n)!!(2n-1)!!=2^{n}n!(2n-1)!!

我々は持っています

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

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

第五証明

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

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$ にはとが同数含まれているのでとなります。バランスの取れた文字列はまたはに一意に分解できるので、 $($ $)$ $\textstyle B_{n}={2n \choose n}$ $(c)b$ $)c'(b$

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

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

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

また、定義から次のことが分かります。

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$ に対して成り立つので、

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

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

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

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

第六証明

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

X と Y のシーケンスが支配的であるとは、左から右に読んで、X の数が常に Y の数より確実に大きい場合を言います。サイクルの補題^[13]によれば、の任意のX とY のシーケンスには、正確に支配的な円移動があります。これを確認するには、与えられたX と Yのシーケンスを円状に配置します。XY のペアを繰り返し削除すると、X がちょうど個残ります。これらの X はそれぞれ、何かが削除される前に支配的な円移動の始まりでした。たとえば、を考えます。このシーケンスは支配的ですが、その円移動、、およびのいずれも支配的ではありません。 $m$ $n$ $m>n$ $m-n$ $m+n$ $m-n$ ${\mathit {XXYXY}}$ ${\mathit {XYXYX}}$ ${\mathit {YXYXX}}$ ${\mathit {XYXXY}}$ ${\mathit {YXXYX}}$

文字列がXとYのDyck語である場合、かつそのDyck語の先頭にXを付加するとXとYの支配的なシーケンスが得られる場合に限り、後者を数える代わりに前者を数えることができます。特に、のとき、支配的な円シフトはちょうど1つ存在します。XとYのシーケンスがちょうど1つ存在します。これらのそれぞれについて、円シフトのうち1つだけが支配的です。したがって、支配的なXとYのシーケンスが別々に存在し、それぞれがちょうど1つのDyck語に対応します。 $n$ $n$ $n+1$ $n$ $m=n+1$ $\textstyle {2n+1 \choose n}$ $n+1$ $n$ $2n+1$ $\textstyle {\frac {1}{2n+1}}{2n+1 \choose n}=C_{n}$ $n+1$ $n$

ハンケル行列

n $\times n$ ハンケル行列の $(i, j)$ 要素がカタラン数 $C i + j -2$ $である行列式は、 n$ の値に関わらず 1 となる。例えば、 $n$ $= 4$ の場合には $、$

\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$ の場合、

\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 \times nの部分行列に行列式$ $n$ $+ 1$ があることです。

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

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

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

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

などなど。

歴史

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

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

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

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

一般化

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

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

の場合、これは通常のカタラン数の2倍に過ぎず、の場合、これらの数は簡単な組合せ論的記述を持つ。しかし、他の組合せ論的記述はとについてのみ知られており[ 17 ^]、^[18] 、一般的な組合せ論的解釈を見つけることは未解決問題である。 $m=1$ $m=n$ $m=2,3$ $4$

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

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

互いに素な正の整数 $r$ と $s$ に対して、有理カタラン数は $(0,0)から$ $($ $r$ $,$ $s$ $)$ まで右上方向に単位長さずつ進み、直線 $ry$ $=$ $sx$ より上に行かない格子パスの数を数える。^[21] ${\frac {1}{r+s}}{\binom {r+s}{r}}$

カタランk倍畳み込み

カタラン $k$ 畳み込み（ $k = m$ ）は次の式で表される: ^[22]

\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}}

参照

注記

^ Koshy, Thomas; Salmassi, Mohammad (2006). 「カタラン数のパリティと素数性」(PDF) . The College Mathematics Journal . 37 (1): 52– 53. doi :10.2307/27646275. JSTOR 27646275.
^ Sloane, N. J. A. (編). 「シーケンスA000108（カタラン数）」.オンライン整数シーケンス百科事典. OEIS財団.
^ 「カタラン番号」。
^ チェ・ハヨン；イェ・ヨンナン；ユ・ソンウク（2020）「カタラン的数列とハウスドルフモーメント列」、離散数学、343（5）：111808、11、arXiv：1809.07523、doi：10.1016/j.disc.2019.111808、MR 4052255、S2CID 214165563 例3.1
^ フェン、チー; Bai-Ni, Guo (2017)、「Integral Representations of the Catalan Numbers and Their Applications」、数学、5 (3): 40、doi : 10.3390/math5030040定理1
^ ディックパス
^ スタンリー p.221 例 (e)
^ Črepinšek, Matej; Mernik, Luka (2009). 「カタラン数関連問題を解くための効率的な表現」(PDF) .国際純粋応用数学ジャーナル. 56 (4): 589– 604.
^ A. de Segner、Enumeratio modorum、quibus figurae planae rectilineae per anglees dividuntur in triangula. Novi commentarii academiae scientiarum Petropolitanae 7 (1758/59) 203–209。
^ Rukavicka Josef (2011),一般化Dyck経路について, Electronic Journal of Combinatorics online
^ ダーショウィッツ、ナハム; ザックス、シュムエル (1980)、「順序付き木の列挙」、離散数学、31 : 9–28、doi :10.1016/0012-365x(80)90168-5、hdl : 2027/uiuo.ark:/13960/t3kw6z60d
^ Dvoretzky, Aryeh; Motzkin, Theodore (1947)、「配置の問題」、Duke Mathematical Journal、14 (2): 305– 313、doi :10.1215/s0012-7094-47-01423-3
^ Dershowitz, Nachum; Zaks, Shmuel (1990年1月). 「循環補題とその応用」(PDF) . European Journal of Combinatorics . 11 (1): 35– 40. doi :10.1016/S0195-6698(13)80053-4.
^ Stanley, Richard P. (2021). 「1960年代と1970年代の列挙的組合せ論と代数的組合せ論」arXiv : 2105.07884 [math.HO].
^ Larcombe, Peter J. 「18世紀中国におけるカタラン数の発見」(PDF)。
^ “世界初のカタラン数字の発明者、ミン・アントゥ”. 2020年1月31日時点のオリジナルよりアーカイブ。2014年6月24日閲覧。
^ Chen, Xin; Wang, Jane (2012). 「s ≤ 4 に対する超カタラン数 S(m, m + s)」. arXiv : 1208.4196 [math.CO].
^ Gheorghiciuc, Irina; Orelowitz, Gidon (2020). 「第三種および第四種の超カタラン数」. arXiv : 2008.00133 [math.CO].
^ セルゲイ・フォミンとネイサン・リーディング、「ルートシステムと一般化アソシアヘドラ」、幾何学的組み合わせ論、IAS/パークシティ数学。第13号、アメリカ数学会、プロビデンス、ロードアイランド州、2007年、pp 63–131。arXiv : math/0505518
^ チェ・ハヨン；イェ・ヨンナン；ユ・ソンウク（2020）「カタラン的数列とハウスドルフモーメント列」、離散数学、343（5）：111808、11、arXiv：1809.07523、doi：10.1016/j.disc.2019.111808、MR 4052255、S2CID 214165563
^ Krattenthaler, Christian (2015). 「Lattice Path Enumeration」（PDF） . Bóna, Miklós (編). Handbook of Enumerative Combinatorics . Discrete Mathematics and Its Applications (1 ed.). CRC Press. p. 598. ISBN 9780429170317。
^ Bowman, D.; Regev, Alon (2014). 「対称性の計算：凸正多角形の分割クラス」. Adv. Appl. Math . 56 : 35–55 . arXiv : 1209.6270 . doi : 10.1016/j.aam.2014.01.004 . S2CID 15430707.

参考文献

スタンリー、リチャード・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。
ラーコム, PJ (1999). 「18世紀中国におけるカタラン数の発見」(PDF) .数学スペクトラム. 32 : 5–7 .
スタンリー、リチャード・P.（1999）「列挙的組合せ論」第2巻、ケンブリッジ高等数学研究第62巻、ケンブリッジ大学出版局、ISBN 978-0-521-56069-6、MR 1676282
Egecioglu, Omer (2009), カタラン–ハンケル行列式の評価(PDF)
Gheorghiciuc, Irina; Orelowitz, Gidon (2020),第3種および第4種の超カタラン数, arXiv : 2008.00133

外部リンク

スタンリー、リチャード P. (1998)、「列挙的組合せ論」第 2 巻のカタロニア語版補遺(PDF)
ワイスタイン、エリック・W.「カタラン数」。MathWorld。
デイビス、トム：カタラン数。さらに例を挙げます。
Wolfram Demonstrations Project [1]の「3つのカタラン数解釈の同値性」
Wikiversityの分割関連数三角形に関する学習教材

[1] Koshy, Thomas; Salmassi, Mohammad (2006). 「カタラン数のパリティと素数性」(PDF) . The College Mathematics Journal . 37 (1): 52– 53. doi :10.2307/27646275. JSTOR 27646275.

[2] Sloane, N. J. A. (編). 「シーケンスA000108（カタラン数）」.オンライン整数シーケンス百科事典. OEIS財団.

[3] 「カタラン番号」。

[4] チェ・ハヨン；イェ・ヨンナン；ユ・ソンウク（2020）「カタラン的数列とハウスドルフモーメント列」、離散数学、343（5）：111808、11、arXiv：1809.07523、doi：10.1016/j.disc.2019.111808、MR 4052255、S2CID 214165563 例3.1

[5] フェン、チー; Bai-Ni, Guo (2017)、「Integral Representations of the Catalan Numbers and Their Applications」、数学、5 (3): 40、doi : 10.3390/math5030040定理1

[6] ディックパス

[7] スタンリー p.221 例 (e)

[8] Črepinšek, Matej; Mernik, Luka (2009). 「カタラン数関連問題を解くための効率的な表現」(PDF) .国際純粋応用数学ジャーナル. 56 (4): 589– 604.

[9] A. de Segner、Enumeratio modorum、quibus figurae planae rectilineae per anglees dividuntur in triangula. Novi commentarii academiae scientiarum Petropolitanae 7 (1758/59) 203–209。

[10] Rukavicka Josef (2011),一般化Dyck経路について, Electronic Journal of Combinatorics online

[11] ダーショウィッツ、ナハム; ザックス、シュムエル (1980)、「順序付き木の列挙」、離散数学、31 : 9–28、doi :10.1016/0012-365x(80)90168-5、hdl : 2027/uiuo.ark:/13960/t3kw6z60d

[12] Dvoretzky, Aryeh; Motzkin, Theodore (1947)、「配置の問題」、Duke Mathematical Journal、14 (2): 305– 313、doi :10.1215/s0012-7094-47-01423-3

[13] Dershowitz, Nachum; Zaks, Shmuel (1990年1月). 「循環補題とその応用」(PDF) . European Journal of Combinatorics . 11 (1): 35– 40. doi :10.1016/S0195-6698(13)80053-4.

[14] Stanley, Richard P. (2021). 「1960年代と1970年代の列挙的組合せ論と代数的組合せ論」arXiv : 2105.07884 [math.HO].

[15] Larcombe, Peter J. 「18世紀中国におけるカタラン数の発見」(PDF)。

[16] “世界初のカタラン数字の発明者、ミン・アントゥ”. 2020年1月31日時点のオリジナルよりアーカイブ。2014年6月24日閲覧。

[Chen2012-17] Chen, Xin; Wang, Jane (2012). 「s ≤ 4 に対する超カタラン数 S(m, m + s)」. arXiv : 1208.4196 [math.CO].

[18] Gheorghiciuc, Irina; Orelowitz, Gidon (2020). 「第三種および第四種の超カタラン数」. arXiv : 2008.00133 [math.CO].

[19] セルゲイ・フォミンとネイサン・リーディング、「ルートシステムと一般化アソシアヘドラ」、幾何学的組み合わせ論、IAS/パークシティ数学。第13号、アメリカ数学会、プロビデンス、ロードアイランド州、2007年、pp 63–131。arXiv : math/0505518

[20] チェ・ハヨン；イェ・ヨンナン；ユ・ソンウク（2020）「カタラン的数列とハウスドルフモーメント列」、離散数学、343（5）：111808、11、arXiv：1809.07523、doi：10.1016/j.disc.2019.111808、MR 4052255、S2CID 214165563

[21] Krattenthaler, Christian (2015). 「Lattice Path Enumeration」（PDF） . Bóna, Miklós (編). Handbook of Enumerative Combinatorics . Discrete Mathematics and Its Applications (1 ed.). CRC Press. p. 598. ISBN 9780429170317。

[22] Bowman, D.; Regev, Alon (2014). 「対称性の計算：凸正多角形の分割クラス」. Adv. Appl. Math . 56 : 35–55 . arXiv : 1209.6270 . doi : 10.1016/j.aam.2014.01.004 . S2CID 15430707.

権限管理データベース
国際的	GND
全国	アメリカ合衆国チェコ共和国イスラエル
他の	イェール・ラックス