[proofplan]
We count noncrossing partitions by decomposing each partition according to the block containing $1$. The gaps between consecutive elements of that block support independent smaller noncrossing partitions, which gives the Catalan recurrence. We translate this recurrence into an identity of formal [power series](/page/Power%20Series), solve the resulting quadratic equation by the branch with constant term $1$, and extract the coefficients by the binomial expansion of the formal square root.
[/proofplan]
[step:Define the counting sequence and isolate the block containing $1$]
For each integer $n \geq 0$, define the integer $C_n := |NC(n)|$. For $n = 0$, the set $\{1,\dots,n\}$ is empty, and there is exactly one partition of the empty set, so $C_0 = 1$.
Fix an integer $n \geq 1$ and a partition $\pi \in NC(n)$. Let $V$ be the block of $\pi$ containing $1$. Write
\begin{align*}
V = \{i_1,\dots,i_r\}
\end{align*}
where $r \in \{1,\dots,n\}$ and
\begin{align*}
1 = i_1 < i_2 < \cdots < i_r \leq n.
\end{align*}
Define finite ordered intervals $I_1,\dots,I_r$ by
\begin{align*}
I_j := \{i_j + 1,\dots,i_{j+1}-1\}
\end{align*}
for $1 \leq j \leq r-1$, and
\begin{align*}
I_r := \{i_r+1,\dots,n\}.
\end{align*}
Let $m_j := |I_j|$ for $1 \leq j \leq r$. Since the elements of $\{1,\dots,n\}$ are precisely the $r$ elements of $V$ together with the disjoint intervals $I_1,\dots,I_r$, we have
\begin{align*}
m_1 + \cdots + m_r = n-r.
\end{align*}
[/step]
[step:Show that every remaining block lies inside one interval]
Every block of $\pi$ distinct from $V$ is contained in one of the intervals $I_1,\dots,I_r$.
Indeed, suppose a block $W \neq V$ contains two elements $a < b$ lying in different intervals. Then there exists an index $j \in \{2,\dots,r\}$ such that
\begin{align*}
a < i_j < b.
\end{align*}
Since $i_1 = 1$ and $a \notin V$, we also have
\begin{align*}
i_1 < a < i_j < b.
\end{align*}
The elements $i_1$ and $i_j$ lie in the block $V$, while $a$ and $b$ lie in the distinct block $W$. This is a crossing, contradicting $\pi \in NC(n)$. Hence no such block $W$ exists.
[guided]
The key point is that the block $V$ containing $1$ acts as a set of dividers. We prove that another block cannot pass across one of these dividers.
Let $W$ be a block of $\pi$ with $W \neq V$. Assume, for contradiction, that $W$ contains two elements $a < b$ that are not in the same interval among $I_1,\dots,I_r$. Because the intervals are exactly the gaps between consecutive elements of $V$, this means that at least one element of $V$ lies strictly between $a$ and $b$. Thus there is an index $j \in \{2,\dots,r\}$ such that
\begin{align*}
a < i_j < b.
\end{align*}
Since $i_1 = 1$ and $a$ is not in the block $V$, we also have $i_1 < a$. Therefore the four elements occur in the order
\begin{align*}
i_1 < a < i_j < b.
\end{align*}
Now $i_1$ and $i_j$ lie in the same block $V$, while $a$ and $b$ lie in the same block $W$, and $V \neq W$. This is exactly the forbidden crossing pattern in the definition of a noncrossing partition. Hence $W$ cannot meet two different intervals, and every block other than $V$ is contained in a single interval.
[/guided]
[/step]
[step:Construct the bijection with tuples of smaller noncrossing partitions]
For fixed integers $r \geq 1$ and $m_1,\dots,m_r \geq 0$ satisfying
\begin{align*}
m_1+\cdots+m_r = n-r,
\end{align*}
the choice of a block $V$ containing $1$ with gap sizes $m_1,\dots,m_r$ is unique. Its elements are determined recursively by $i_1 = 1$ and
\begin{align*}
i_{j+1} = i_j + m_j + 1
\end{align*}
for $1 \leq j \leq r-1$.
By the previous step, restricting a partition $\pi \in NC(n)$ to each interval $I_j$ gives a noncrossing partition of the linearly ordered set $I_j$. After identifying $I_j$ order-preservingly with $\{1,\dots,m_j\}$, this restriction is an element of $NC(m_j)$.
Conversely, given partitions
\begin{align*}
\sigma_j \in NC(m_j)
\end{align*}
for $1 \leq j \leq r$, identify each $\sigma_j$ with a partition of the corresponding interval $I_j$ by the unique order-preserving bijection $\{1,\dots,m_j\} \to I_j$. Then form a partition $\pi$ of $\{1,\dots,n\}$ whose blocks are $V$ together with all blocks coming from the transported partitions on the intervals.
This partition $\pi$ is noncrossing. A crossing entirely inside one interval would contradict $\sigma_j \in NC(m_j)$ for that interval. A crossing involving elements from two different intervals would require a block other than $V$ to meet two intervals, which does not occur by construction. A crossing involving the block $V$ and a block inside an interval is impossible because that interval lies between two consecutive elements of $V$, or after the last element of $V$, so the two elements of the inner block cannot separate two elements of $V$ in the forbidden alternating order.
Thus the construction is inverse to restriction. Therefore, for every $n \geq 1$,
\begin{align*}
C_n = \sum_{r=1}^{n}\sum_{\substack{m_1, \dots, m_r \geq 0, m_1+\cdots+m_r = n-r}} C_{m_1}\cdots C_{m_r}.
\end{align*}
[/step]
[step:Translate the recurrence into a quadratic formal power series identity]
Define the formal power series $C(z) \in \mathbb{Z}[[z]]$ by
\begin{align*}
C(z) := \sum_{n=0}^{\infty} C_n z^n.
\end{align*}
The recurrence gives, as an identity in $\mathbb{Z}[[z]]$,
\begin{align*}
C(z) = 1 + \sum_{r=1}^{\infty} z^r C(z)^r.
\end{align*}
The term $z^r C(z)^r$ records the choice of $r$ elements in the distinguished block together with $r$ gap partitions, because the coefficient of $z^{n-r}$ in $C(z)^r$ is the inner convolution over $m_1+\cdots+m_r=n-r$.
Since the right-hand sum is a geometric series in the formal power series $zC(z)$, whose constant term is $0$, we have
\begin{align*}
\sum_{r=1}^{\infty} z^r C(z)^r = \frac{zC(z)}{1-zC(z)}.
\end{align*}
Hence
\begin{align*}
C(z) = 1 + \frac{zC(z)}{1-zC(z)}.
\end{align*}
Multiplying by $1-zC(z)$ and simplifying gives
\begin{align*}
C(z) = 1 + zC(z)^2.
\end{align*}
[/step]
[step:Solve the quadratic identity by the branch with constant term $1$]
The identity
\begin{align*}
C(z) = 1 + zC(z)^2
\end{align*}
is equivalent to
\begin{align*}
zC(z)^2 - C(z) + 1 = 0.
\end{align*}
Solving this quadratic equation formally gives
\begin{align*}
C(z) = \frac{1-\sqrt{1-4z}}{2z}.
\end{align*}
The other formal expression with the plus sign has a pole at $z=0$ and therefore is not a formal power series with constant term $1$.
To extract coefficients, use the binomial expansion in $\mathbb{Q}[[z]]$:
\begin{align*}
\sqrt{1-4z} = \sum_{k=0}^{\infty} \binom{1/2}{k}(-4z)^k.
\end{align*}
Therefore, for $n \geq 0$, the coefficient of $z^n$ in $C(z)$ is
\begin{align*}
-\frac{1}{2}\binom{1/2}{n+1}(-4)^{n+1}.
\end{align*}
We compute this coefficient by expanding the generalized binomial coefficient:
\begin{align*}
\binom{1/2}{n+1}
= \frac{(1/2)(1/2-1)\cdots(1/2-n)}{(n+1)!}
= \frac{(-1)^n}{2^{n+1}(n+1)!}(1\cdot 3 \cdots (2n-1)).
\end{align*}
Multiplying by $-\frac12(-4)^{n+1}$ gives
\begin{align*}
-\frac{1}{2}\binom{1/2}{n+1}(-4)^{n+1}
= \frac{2^n}{(n+1)!}(1\cdot 3 \cdots (2n-1)).
\end{align*}
Using
\begin{align*}
(2n)! = (2\cdot 4 \cdots 2n)(1\cdot 3 \cdots (2n-1)) = 2^n n!(1\cdot 3 \cdots (2n-1)),
\end{align*}
we rewrite the right-hand side as
\begin{align*}
\frac{2^n}{(n+1)!}(1\cdot 3 \cdots (2n-1)) = \frac{1}{n+1}\binom{2n}{n}.
\end{align*}
Thus the coefficient of $z^n$ in $C(z)$ is $\frac{1}{n+1}\binom{2n}{n}$.
[guided]
We have reduced the enumeration problem to the formal identity
\begin{align*}
C(z) = 1 + zC(z)^2.
\end{align*}
This is a quadratic equation for the unknown formal power series $C(z)$. Rewriting it gives
\begin{align*}
zC(z)^2 - C(z) + 1 = 0.
\end{align*}
The [quadratic formula](/theorems/1301) suggests two possible expressions:
\begin{align*}
\frac{1-\sqrt{1-4z}}{2z}
\end{align*}
and
\begin{align*}
\frac{1+\sqrt{1-4z}}{2z}.
\end{align*}
Only the first one is a formal power series with constant term $1$. Indeed, the expansion of $\sqrt{1-4z}$ begins with constant term $1$, so $1-\sqrt{1-4z}$ has zero constant term and is divisible by $z$. The expression with $1+\sqrt{1-4z}$ has numerator with constant term $2$, so division by $z$ would produce a negative power of $z$.
Thus
\begin{align*}
C(z) = \frac{1-\sqrt{1-4z}}{2z}.
\end{align*}
Now we compute its coefficient of $z^n$. In the ring of formal power series over $\mathbb{Q}$, the binomial expansion gives
\begin{align*}
\sqrt{1-4z} = \sum_{k=0}^{\infty} \binom{1/2}{k}(-4z)^k.
\end{align*}
Subtracting from $1$ removes the $k=0$ term, and division by $2z$ shifts the index down by one. Hence the coefficient of $z^n$ in $C(z)$ is
\begin{align*}
-\frac{1}{2}\binom{1/2}{n+1}(-4)^{n+1}.
\end{align*}
It remains to simplify this expression. Expanding the generalized binomial coefficient gives
\begin{align*}
\binom{1/2}{n+1} = \frac{(1/2)(1/2-1)\cdots(1/2-n)}{(n+1)!}.
\end{align*}
Multiplying by $-\frac{1}{2}(-4)^{n+1}$ and collecting the factors yields the standard Catalan number:
\begin{align*}
-\frac{1}{2}\binom{1/2}{n+1}(-4)^{n+1} = \frac{1}{n+1}\binom{2n}{n}.
\end{align*}
Therefore the coefficient of $z^n$ in $C(z)$ is $\frac{1}{n+1}\binom{2n}{n}$.
[/guided]
[/step]
[step:Conclude the enumeration formula]
By definition, $C_n = |NC(n)|$. The coefficient computation in the preceding step gives
\begin{align*}
C_n = \frac{1}{n+1}\binom{2n}{n}
\end{align*}
for every integer $n \geq 0$. Therefore
\begin{align*}
|NC(n)| = \frac{1}{n+1}\binom{2n}{n}
\end{align*}
for every integer $n \geq 0$, as required.
[/step]
