Confused about Catalan number equation

Question

Why is the Catalan number $$C_{n+1} = C_0 C_n+C_1C_{n-1}+\cdots+C_{n-1}C_1+C_nC_0,$$ and not $$C_{n+1} = C_0C_{n+1} + C_1C_n +\cdots+ C_nC_1 + C_{n+1}C_0 ?$$ In the latter formula, $0+(n+1) = 1+n = (n+1)$, but the former formula miss 1. It seems missing 1 is correct and wondering what is the logics behind the scene.

Link

Answer 1

One way of thinking about the recursion is a sort of divide and conquer. For example, one combinatorial interpretation of the Catalan numbers is that $C_n$ is the number of ways of drawing $n$ non-intersecting chords between $2n$ points on a circle (Part (n) of Stanley's infamous "catalan exercise").

Here the recurrence for $C_{n+1}$ comes from marking a single point (call it $x$) and considering the chord through that point.

The chord through $x$ divides the circle into two parts, one starting clockwise from $x$ and one counterclockwise. If there's $k$ chords in one part, there's $n-k$ chords in the other part, so there's $C_k$ ways to draw the chords in the clockwise part, and $C_{n-k}$ ways to draw the chords in the counterclockwise part. The recursion comes from adding up over all $k$.

A key thing here: Even though there's $n+1$ chords in the original circle, when I do my divide-and-conquer I'm only dividing up $n$ chords. This is because the chord through $x$ is not included in either half. That's where the missing "1" went.

A similar thing happens many other times when you prove something is counted by the Catalan numbers using the recursive formula: You fix one small part (one triangle in your triangulation, or the time of the first return to $0$ of your Dyck path). This divides the rest of your objects into two classes, but the sum of the sizes of the two classes is smaller than the original, because you've already fixed what happens in one place.