= Catalan number
{c}
{title2=$C_n=\frac1{n+1}\binom{2n}{n}$}
{wiki}
The <Catalan number> $C_n$ counts <Dyck paths> with <semilength of a Dyck path> $n$. For a <nonnegative integer> $n$,
$$
\boxed{C_n=\frac1{n+1}\binom{2n}{n},\qquad (C_0,C_1,C_2,C_3,C_4,C_5)=(1,1,2,5,14,42).}
$$
The count $C_0=1$ includes the empty path. Of the $\binom63=20$ paths with three up steps and three down steps, \b[exactly five stay at nonnegative height]. Their shapes and <balanced parentheses> encodings appear below.<Bijective Proof Problems by Richard P. Stanley>[§5, printed pp. 38–39, formula (7) and Problems 154–159: Catalan counts, binary parenthesizations, binary trees and Dyck paths]{ref}
\Image[/catalan-five-dyck-paths-and-parentheses.png]
{title=All five Dyck paths of semilength three and their balanced parentheses encodings}
{description=Original enumeration of six-step up/down paths with nonnegative prefix heights. An up step encodes an opening parenthesis and a down step a closing one. Each panel shows one distinct string; no path shape or illustration is copied from a source.}
The useful connection is a shared decomposition. A <Dyck path> splits uniquely at its <first-return decomposition of a Dyck path>; a <binary tree> splits at its root into left and right subtrees; a <binary parenthesization> splits at its last operation. Each removes one outer unit and leaves an <ordered pair> of smaller objects. The resulting <Catalan recurrence> lets one count several different structures with the same calculation. A count of five does not mean the structures are physically identical: a <bijection> supplies the precise translation between them.
Back to article page
