Catalan number

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ... (sequence in the OEIS).

The latter representation is closely connected to Wigner's semicircle law for eigenvalue distribution of random symmetric matrices.

Also, the interior of the correctly matching closing Y for the first X of a Dyck word contains the description of the left subtree, with the exterior describing the right subtree.

The dark triangle is the root node, the light triangles correspond to internal nodes of the binary trees, and the green bars are the leaves.

For example, every Dyck word w of length ≥ 2 can be written in a unique way in the form

The recurrence relation given above can then be summarized in generating function form by the relation

From the two possibilities, the second must be chosen because only the choice of the second gives

The square root term can be expanded as a power series using the identity

This is a special case of Newton's generalized binomial theorem; as with the general theorem, it can be proved by computing derivatives to produce its Taylor series.

The part of the path after the higher diagonal is flipped about that diagonal, as illustrated with the red dotted line. This swaps all the right steps to up steps and vice versa. In the section of the path that is not reflected, there is one more up step than right steps, so therefore the remaining section of the bad path has one more right step than up steps. When this portion of the path is reflected, it will have one more up step than right steps.

and the number of Catalan paths (i.e. good paths) is obtained by removing the number of bad paths from the total number of monotonic paths of the original grid,

Given a monotonic path whose exceedance is not zero, we apply the following algorithm to construct a new path whose exceedance is 1 less than the one we started with.

In Figure 3, the black dot indicates the point where the path first crosses the diagonal. The black edge is X, and we place the last lattice point of the red portion in the top-right corner, and the first lattice point of the green portion in the bottom-left corner, and place X accordingly, to make a new path, shown in the second diagram.

Figure 4. All monotonic paths in a 3×3 grid, illustrating the exceedance-decreasing algorithm.

Any incorrect balanced string starts with c ], and the remaining string has one more [ than ], so

Taken together, these two conditions uniquely define the Catalan numbers.

The Quick Method for Obtaining the Precise Ratio of Division of a Circle[The Quick Method for Obtaining the Precise Ratio of Division of a Circle]

For instance, Ming used the Catalan sequence to express series expansions of sin(2α) and sin(4α) in terms of sin(α).