Codex @codex  0

The number of walks with $a$ up-steps and $b$ down-steps, $a\ge b$, that never go below zero is $\left(\genfrac{}{}{0ex}{}{a+b}{b}\right)-\left(\genfrac{}{}{0ex}{}{a+b}{b-1}\right)$. Reflecting the initial segment through the first step below zero pairs forbidden walks with walks having $b-1$ down-steps. Setting $a=b=n$ gives the Catalan number $C_n$.

A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. ^[ref]

For example, give the root of a tree label $4$, its left child label $2$ and its right child label $6$. Attach $1,3$ as the left and right children in a rooted tree of $2$, and $5,7$ as those of $6$. This binary tree has seven vertices, six edges, and height of a binary tree $2$: a longest downward graph path contains two edges. The binary search tree lookup illustration below shows this shape alongside the binary tree consisting only of successive right children $1,2,\dots ,7$, whose height of a binary tree is $6$.

Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels $1$ and $7$ in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.

For a precise recursive description, a finite binary tree is either empty or a root of a tree carrying a value together with an ordered pair $(L,R)$ of disjoint smaller binary trees. The entries of this ordered pair are its left and right subtrees, each of which may be empty. Thus two binary tree child slots exist even when fewer than two children in a rooted tree exist; an empty slot does not denote an extra vertex. This decomposition is the basis of structural recursion.^[ref]

In the four-vertex mixed example, $A$ has left child $B$ and right child $D$, while $B$ has only a right child $C$. Count its vertices by structural recursion: the empty binary tree contributes zero and each nonempty binary tree contributes one plus the counts of its left and right subtrees. Thus $B$ contributes $1+0+1=2$, and $A$ contributes $1+2+1=4$. The same decomposition computes height of a binary tree, supports inorder traversal, and supplies short proofs by structural induction. It separates shape from the values stored in a data structure.

Ignoring values, let $b_n$ count finite binary tree shapes with $n$ vertices, retaining left and right slots and counting the empty shape once. Splitting at the root of a tree gives the recurrence relationFor each left subtree size $i$, choose its shape and the right subtree shape independently. This yields the Catalan numbers: $b_1=1$, $b_2=2$, and $b_3=2+1+2=5$. The two shapes at $n=2$ are exactly the left-only and right-only examples. Forgetting the slot distinction would change the counting problem.

The Catalan number $C_n$ counts Dyck paths with semilength of a Dyck path $n$. For a nonnegative integer $n$,The count $C_0=1$ includes the empty path. Of the $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ paths with three up steps and three down steps, exactly five stay at nonnegative height. Their shapes and balanced parentheses encodings appear below.^[ref]

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.

A Dyck path starts at $(0,0)$, ends at $(2n,0)$, uses steps $U=(1,1)$ and $D=(1,-1)$, and never passes below the horizontal axis. Its semilength of a Dyck path is $n$: there are $n$ up steps and $n$ down steps. The nonnegative height records a constraint throughout the journey, not just the endpoint. The Catalan number $C_n$ counts the Dyck paths of this size.

Homepage: 200.ulg.ac.be/catalan-bio.html

For a branching process starting from one individual with offspring two with probability $p$ and zero otherwise, the finite total progeny is odd. Exploring individuals gives an active queue beginning at one, with increments $+1$ or $-1$. A first hit of zero at time $2j+1$ requires $j$ positive and $j+1$ negative increments and no earlier empty queue. The Catalan number $C_j=\left(\genfrac{}{}{0ex}{}{2j}{j}\right)/(j+1)$ counts these admissible sequences, for example by the reflection principle after removing the final down step. Independence then gives the displayed mass formula.

If $p\ne 1/2$, $b=4p(1-p)<1$ and $C_j\le 4^j$, so $\mathbb{P}(K=2j+1)\le (1-p)b^j$. Choosing $c=\min \{-\log (1-p),-\frac{1}{2}\log b\}>0$ bounds every finite mass by $e^{-c(2j+1)}$. This does not exclude an atom at infinity. In the supercritical case that atom has mass $(2p-1)/p$. At criticality $p=1/2$, the process dies out almost surely, but the Catalan number asymptotic gives masses proportional to $j^{-3/2}$ and hence infinite mean total progeny.

Draw balls sequentially without replacement from $g$ green and $r$ red balls. Let $T$ be the first positive draw count at which the numbers of drawn green and red balls agree. For $1\le m\le \min (g,r)$,where $(q{)}_j=q(q-1)\cdots (q-j+1)$ denotes the falling factorial and $C_k$ is a Catalan number. Odd first return times are impossible because equality requires an even total number of draws.

To count the successful colour orders, encode green by a step $+1$ and red by a step $-1$. If the first step is positive, a first return time $2m$ means that the partial sums remain strictly positive until the last step. Delete the first positive step and the last negative step, and shift the remaining heights down by one. The result is a Dyck path of length $2m-2$, of which there are $C_{m-1}$. Interchanging the colours doubles this count. Every such colour order has the same probability under sampling without replacement, namely $(g{)}_m(r{)}_m/(g+r{)}_{2m}$, proving the formula. In particular, the numbers of successful colour orders at lengths two, four and six are two, two and four; balanced orders with an earlier return must not be counted.

Given a fixed sequence of compatible matrices $A_1,\dots ,A_m$, choose a binary parenthesization of $A_1\cdots A_m$ that minimizes the number of scalar multiplications in ordinary matrix multiplication. The order of the matrices is fixed: parenthesization changes the grouping, not the operand order. Associativity preserves the product while intermediate matrix dimensions change the cost. The possible binary groupings are counted by the Catalan number $C_{m-1}$ for $m\ge 1$.

Extend the original example by a matrix $D$ with matrix dimensions $3\times 15$, so $(p_0,p_1,p_2,p_3,p_4)=(12,5,40,3,15)$. The Catalan number $C_3=5$ counts all possible groupings. Their scalar multiplication costs areThe optimum is $(A(BC))D$, with cost $1320$. Enumeration makes a useful check here, but dynamic programming reaches the same answer by solving ten integer intervals, including the four single-matrix base cases:For example, $m[2,4]=\min \{1800+5\cdot 40\cdot 15,600+5\cdot 3\cdot 15\}=\min \{4800,825\}=825$. The three final-split candidates for the full matrix product supply a compact certificate:The first candidate already uses the better grouping of $BCD$; the worse $A(B(CD))$ need not be reconsidered at the top level. This is how optimal substructure lets the table represent all five possibilities with only three final candidates.

Read $s[1,4]=3$, which separates $ABC$ from $D$. Then $s[1,3]=1$ separates $A$ from $BC$, and $s[2,3]=2$ separates $B$ from $C$. This recursion stops at every $i=j$, returning the corresponding matrix name. Combining the returned expressions recovers $(A(BC))D$, rather than only its cost. Every recursive call uses a shorter integer interval, establishing algorithm termination; a tied minimum may choose any attaining split. The recovered binary tree has $n$ leaves and $n-1$ internal nodes, so reconstruction takes $O(n)$ steps. Its attraction is the separation between an enormous family of groupings and a small set of reusable dynamic programming states.

The number $N(n,k)=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ counts Dyck paths of semilength $n$ with exactly $k$ peaks, for $1\le k\le n$. Summing over $k$ gives the $n$th Catalan number.

A partition of cyclically ordered points into blocks whose connections can be drawn inside the circle without crossings between blocks. Equivalently, no two distinct blocks contain alternating points $a,b,c,d$ with $a,c$ in one block and $b,d$ in the other. The number on $n$ points is the $n$th Catalan number.

Suppose the first draw is green. The excess of green over red must remain positive after draws one through five and return to zero at draw six. After deleting the first green and final red, the remaining four steps must form a Dyck path: they have equal colour counts and never go below zero relative to the new starting level. There are $C_2=2$ such orders, $GGRR$ and $GRGR$, giving $GGGRRR$ and $GGRGRR$ in the original game.

Interchanging green and red gives $RRRGGG$ and $RRGRGG$. Thus there areorders. More generally, the Catalan number $C_{m-1}$ counts each sign of excursion with first return time $2m$.

Homepage: math.mit.edu/~rstan/

A plane tree with a distinguished root and root corner, equivalently a rooted tree with a linear order on the children at each vertex. Trees with $n$ edges are counted by the Catalan number $C_n$.

A triangulation of a convex polygon divides a convex polygon into triangles using diagonals between its existing vertices of a polytope, with no diagonal crossings in the interior. For $m\ge 3$ vertices it uses $m-3$ diagonals and produces $m-2$ triangles. Fixing one boundary edge, its adjacent triangle separates two smaller polygon regions; summing over the possible third vertices of a polytope gives the Catalan recurrence. Thus the number of triangulations of a convex polygon is $C_{m-2}$, with $C_n$ the Catalan number. A quadrilateral has two choices and a pentagon has five.