Catalan number

We first observe that all of the combinatorial problems listed above satisfy Segner's[6] recurrence relation

${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0.}$

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

w = Xw₁Yw₂

with (possibly empty) Dyck words w₁ and w₂.

The generating function for the Catalan numbers is defined by

${\displaystyle c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}.}$

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

${\displaystyle c(x)=1+xc(x)^{2};}$

in other words, this equation follows from the recurrence relation by expanding both sides into power series. On the one hand, the recurrence relation uniquely determines the Catalan numbers; on the other hand, interpreting xc² − c + 1 = 0 as a quadratic equation of c and using the quadratic formula, the generating function relation can be algebraically solved to yield two solution possibilities

${\displaystyle c(x)={\frac {1+{\sqrt {1-4x}}}{2x}}}$  or  ${\displaystyle c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}}$.

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

${\displaystyle C_{0}=\lim _{x\to 0}c(x)=1}$.

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

${\displaystyle {\sqrt {1+y}}=\sum _{n=0}^{\infty }{{\frac {1}{2}} \choose n}y^{n}=\sum _{n=0}^{\infty }{\frac {(-1)^{n+1}}{4^{n}(2n-1)}}{2n \choose n}y^{n}}$

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.

Setting y = −4x gives

${\displaystyle {\sqrt {1-4x}}=\sum _{n=0}^{\infty }{\frac {-1}{2n-1}}{2n \choose n}x^{n}=1-\sum _{n=1}^{\infty }{\frac {1}{2n-1}}{2n \choose n}x^{n}}$

and substituting this power series into the expression for c(x), the expansion simplifies to

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{2(2n-1)}}{2n \choose n}x^{n-1}}$.

Let ${\displaystyle N=n-1}$, so that

${\displaystyle \sum _{N=0}^{\infty }{\frac {1}{2(2N+1)}}{2N+2 \choose N+1}x^{N}}$

and because ${\displaystyle {\frac {1}{2(2N+1)}}{2N+2 \choose N+1}=C_{N}}$ (see 'proof of recurrence' above)

we have

${\displaystyle c(x)=\sum _{n=0}^{\infty }{2n \choose n}{\frac {x^{n}}{n+1}}.}$

Figure 1. The invalid portion of the path (dotted red) is flipped (solid red). Bad paths (after the flip) reach (n – 1, n + 1) instead of (n,n).

We count the number of paths which start and end on the diagonal of a n × n grid. All such paths have n right and n up steps. Since we can choose which of the 2n steps are up or right, there are in total ${\displaystyle {\tbinom {2n}{n}}}$ monotonic paths of this type. A bad path crosses the main diagonal and touches the next higher diagonal (red in the illustration).

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.

Since there are still 2n steps, there are now n + 1 up steps and n − 1 right steps. So, instead of reaching (n,n), all bad paths after reflection end at (n − 1, n + 1). Because every monotonic path in the (n − 1) × (n + 1) grid meets the higher diagonal, and because the reflection process is reversible, the reflection is therefore a bijection between bad paths in the original grid and monotonic paths in the new grid.

The number of bad paths is therefore:

${\displaystyle {n-1+n+1 \choose n-1}={2n \choose n-1}={2n \choose n+1}}$

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,

${\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}={\frac {1}{n+1}}{2n \choose n}.}$

In terms of Dyck words, we start with a (non-Dyck) sequence of n X's and n Y's and interchange all X's and Y's after the first Y that violates the Dyck condition. After this Y, note that there is exactly one more Y than there are Xs.

This bijective proof provides a natural explanation for the term n + 1 appearing in the denominator of the formula for C_n. A generalized version of this proof can be found in a paper of Rukavicka Josef (2011).[7]

Figure 2. A path with exceedance 5.

Given a monotonic path, the exceedance of the path is defined to be the number of vertical edges above the diagonal. For example, in Figure 2, the edges above the diagonal are marked in red, so the exceedance of this path is 5.

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.

• Starting from the bottom left, follow the path until it first travels above the diagonal.
• Continue to follow the path until it touches the diagonal again. Denote by X the first such edge that is reached.
• Swap the portion of the path occurring before X with the portion occurring after X.

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 3. The green and red portions are being exchanged.

The exceedance has dropped from 3 to 2. In fact, the algorithm causes the exceedance to decrease by 1 for any path that we feed it, because the first vertical step starting on the diagonal (at the point marked with a black dot) is the unique vertical edge that passes from above the diagonal to below it - all the other vertical edges stay on the same side of the diagonal.

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

It is also not difficult to see that this process is reversible: given any path P whose exceedance is less than n, there is exactly one path which yields P when the algorithm is applied to it. Indeed, the (black) edge X, which originally was the first horizontal step ending on the diagonal, has become the last horizontal step starting on the diagonal. Alternatively, reverse the original algorithm to look for the first edge that passes below the diagonal.

This implies that the number of paths of exceedance n is equal to the number of paths of exceedance n − 1, which is equal to the number of paths of exceedance n − 2, and so on, down to zero. In other words, we have split up the set of all monotonic paths into n + 1 equally sized classes, corresponding to the possible exceedances between 0 and n. Since there are ${\displaystyle \textstyle {2n \choose n}}$ monotonic paths, we obtain the desired formula ${\displaystyle \textstyle C_{n}={\frac {1}{n+1}}{2n \choose n}.}$

Figure 4 illustrates the situation for n = 3. Each of the 20 possible monotonic paths appears somewhere in the table. The first column shows all paths of exceedance three, which lie entirely above the diagonal. The columns to the right show the result of successive applications of the algorithm, with the exceedance decreasing one unit at a time. There are five rows, that is, C₃ = 5, and the last column displays all paths no higher than the diagonal.

Using Dyck words, start with a sequence from ${\displaystyle \textstyle {\binom {2n}{n}}}$. Let ${\displaystyle X_{d}}$ be the first X that brings an initial subsequence to equality, and configure the sequence as ${\displaystyle (F)X_{d}(L)}$. The new sequence is ${\displaystyle LXF}$.

This proof uses the triangulation definition of Catalan numbers to establish a relation between C_n and C_n+1.

Given a polygon P with n + 2 sides and a triangulation, mark one of its sides as the base, and also orient one of its 2n + 1 total edges. There are (4n + 2)C_n such marked triangulations for a given base.

Given a polygon Q with n + 3 sides and a (different) triangulation, again mark one of its sides as the base. Mark one of the sides other than the base side (and not an inner triangle edge). There are (n + 2)C_n + 1 such marked triangulations for a given base.

There is a simple bijection between these two marked triangulations: We can either collapse the triangle in Q whose side is marked (in two ways, and subtract the two that cannot collapse the base), or, in reverse, expand the oriented edge in P to a triangle and mark its new side.

Thus

${\displaystyle (4n+2)C_{n}=(n+2)C_{n+1}}$.

Write ${\displaystyle \textstyle {\frac {4n-2}{n+1}}C_{n-1}=C_{n}.}$

Because ${\displaystyle (2n)!=(2n)!!(2n-1)!!=2^{n}n!(2n-1)!!}$

then

${\displaystyle {\frac {(2n)!}{n!}}=2^{n}(2n-1)!!=(4n-2)!!!!.}$

Applying the recursion with ${\displaystyle C_{1}=1}$ gives the result.

This proof is based on the Dyck words interpretation of the Catalan numbers, so C_n is the number of ways to correctly match n pairs of brackets. We denote a (possibly empty) correct string with c and its inverse (where "[" and "]" are exchanged) with c^'. Since any c can be uniquely decomposed into c = [ c₁ ] c₂, summing over the possible spots to place the closing bracket immediately gives the recursive definition

${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0.}$

Let b stand for a balanced string of length 2n—that is, containing an equal number of "[" and "]", so ${\displaystyle \textstyle B_{n}={2n \choose n}}$. As before, any balanced string can be uniquely decomposed into either [ c ] b or ] c^' [ b, so

${\displaystyle B_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}.}$

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

${\displaystyle B_{n+1}-C_{n+1}=\sum _{i=0}^{n}{2i+1 \choose i}C_{n-i}}$

Also, from the definitions, we have:

${\displaystyle B_{n+1}-C_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}-\sum _{i=0}^{n}C_{i}\,C_{n-i}=\sum _{i=0}^{n}(2B_{i}-C_{i})C_{n-i}.}$

Therefore

${\displaystyle 2B_{i}-C_{i}={2i+1 \choose i}={\frac {2i+1}{i+1}}B_{i},}$

${\displaystyle C_{i}=B_{i}\left(2-{\frac {2i+1}{i+1}}\right),}$

${\displaystyle C_{i}={\frac {1}{i+1}}{\binom {2i}{i}}.}$

This proof is based on the Dyck words interpretation of the Catalan numbers and uses the Cycle lemma of Dvoretzky and Motzkin.[8][9]

We call a sequence of X's and Y's dominating if, reading from left to right, the number of X's is always strictly greater than the number of Y's. The Cycle lemma[10] states that any sequence of ${\displaystyle m}$ X's and ${\displaystyle n}$ Y's, where ${\displaystyle m>n}$, has precisely ${\displaystyle m-n}$ dominating cyclic permutations. To see this, arrange the given sequence of ${\displaystyle m+n}$ X's and Y's in a circle. Repeatedly removing XY pairs leaves exactly ${\displaystyle m-n}$ X's. Each of these X's was the start of a dominating cyclic permutation before anything was removed.

For example, consider ${\displaystyle XXYXY}$. This is dominating, but none of its cyclic permutations ${\displaystyle XYXYX}$, ${\displaystyle YXYXX}$, ${\displaystyle XYXXY}$ and ${\displaystyle YXXYX}$ are.

In particular, when ${\displaystyle m=n+1}$, there is exactly one dominating cyclic permutation. Removing the leading X from it (a dominating sequence must begin with X) leaves a Dyck sequence. Since there are ${\displaystyle \textstyle {2n+1 \choose n}}$ in total, and each one belongs to an equivalence class of size 2n+1 (because n, m and 2n+1 are pairwise coprime), we have ${\displaystyle \textstyle {\frac {1}{2n+1}}{2n+1 \choose n}={\frac {1}{n+1}}{2n \choose n}=C_{n}}$ distinct cycles of ${\displaystyle n+1}$ X's and ${\displaystyle n}$ Y's, each of which corresponds to exactly one Dyck sequence, hence ${\displaystyle \textstyle C_{n}}$ counts Dyck sequences.