カタラン数
例えば3組の () を正しく(つまり「開き」と「閉じ」が一対一に対応するように)並べる方法は、「((()))」「()(())」「()()()」「(())()」「(()())」の5通りある。これが C3 = 5 に対応している。())()) や )(()() といった形は () を正しく並べていないのでカウントしない。
Cn は、n個の分岐を持つ(n + 1枚の葉を持つ)二分木の総数である。上記の図は C3 = 5 の場合に対応している。
初等組合せ論におけるカタラン数(カタランすう、英: Catalan number)は、ベルギーの数学者ウジェーヌ・カタランに因んで名付けられた自然数のクラスである。n番目のカタラン数 Cn は
C n = 1 n + 1 ( 2 n n ) = ( 2 n ) ! ( n + 1 ) ! n ! ( n ≥ 0 ) {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\quad (n\geq 0)}
で表される。n = 0, 1, 2, ... に対してカタラン数は
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...(オンライン整数列大辞典の数列 A000108)
となる