Catalan objects and lattice paths

A Dyck path of semilength n contains n up-steps and n down-steps, starts and ends at height zero, and has no negative partial height. The empty path is allowed. Every nonempty Dyck path starts upward; pair that first step with the down-step making its first return to zero. Between them lies a smaller Dyck path shifted upward by one unit, and after them lies another Dyck path. The first-return position is unique, so this is a reversible decomposition.

If the inner path has semilength i, the remaining path has semilength n minus one minus i. Summing over i gives the Catalan convolution. Its generating function satisfies $C=1+xC^2$: one empty path, or one outer matched pair with two ordered smaller paths. The order of those two roles matters. A formal series with constant term one is determined recursively by this equation, without evaluating it at any real x or appealing to an analytic square-root branch.

There are binomially many unrestricted words with n up-steps and n down-steps. A bad word first reaches height minus one at a unique step. Swap up and down throughout the prefix ending at that first violation, leaving the suffix unchanged. The transformed word has n plus one up-steps and n minus one down-steps, so its endpoint is height two. The inverse reflects the prefix through the first arrival at height one in that transformed word.

The inverse works because every path ending at height two must pass through height one. Before its first such arrival it never exceeds zero, so reflecting that prefix produces a path whose first negative height is precisely minus one at the end of the reflected prefix. Thus reflection is a bijection, not just a heuristic subtraction. Subtracting the transformed-word count from all balanced words produces the Catalan formula. The derivation depends on unit steps and the stated starting boundary; modified steps or barriers require a new argument.

A balanced-parenthesis word corresponds to a Dyck path by replacing each opening parenthesis with an up-step. Nonnegative prefixes express that no closing parenthesis lacks a preceding match. Full ordered binary trees provide another Catalan class when size means number of internal vertices and every internal vertex has exactly two ordered child positions. The empty internal-vertex structure is represented by a leaf, and removing the root leaves an ordered pair of smaller full binary trees, giving the same recurrence with the same initial value.

A general rooted plane tree has an ordered list of children rather than exactly two child positions. It is counted by a shifted Catalan sequence when size counts all vertices; those size conventions cannot be silently interchanged. Likewise an unordered binary tree identifies child swaps and has a different count. Matching a Catalan number in small cases is therefore only a clue. Specify the structural class, its size statistic, and either its inverse encoding or its recurrence with initial conditions before claiming a Catalan enumeration.