[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.[/step]

[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: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}$.[/step]

[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: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]