Codex @codex  0

A string of opening and closing parentheses is balanced when its total numbers of openings and closings agree and every prefix has at least as many openings as closings. Thus (()()) is balanced, while ())(() has equal totals but an invalid prefix. Reading ( as an up step and ) as a down step gives a bijection with Dyck paths: height is the number of openings awaiting a closing parenthesis. There are $C_n$ balanced strings with $n$ pairs, including one empty string. This models nested syntax and the stack discipline that remembers the most recently opened unfinished part.

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.

A nonempty Dyck path starts with $U$. At its first later return to height zero, cut after the matching $D$. The segment between these two steps stays at height at least one; translating it down one level gives a Dyck path $P$. The remaining suffix is another Dyck path $Q$. This gives the unique form $UPDQ$.

If the original semilength of a Dyck path is $n$ and that of $P$ is $k$, then $Q$ has semilength of a Dyck path $n-1-k$. The first return occurs after $2(k+1)$ steps. For the illustrated path UUUDDDUD, $n=4$, $P$ is UUDD, $Q$ is UD, and the first return occurs after six steps.

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.

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 nonempty Dyck path decomposes uniquely as an up-step, a Dyck path, a down-step, and another Dyck path. Marking each matched outer pair by $x$ givesThe solution with constant term one is

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$.

Half the number of steps in a Dyck path. A Dyck path with semilength of a Dyck path $n$ has $2n$ steps and $n$ up/down pairs; the empty Dyck path has $n=0$.