TL;DR

The sequence \( C_n = \frac{1}{n+1}\binom{2n}{n} \) counting balanced parentheses, binary trees, non-crossing partitions, and paths below the diagonal. First few values: 1, 1, 2, 5, 14, 42.

By Valenke Exam Prep Team·Last updated 2026-06-03

Catalan Number

The sequence \( C_n = \frac{1}{n+1}\binom{2n}{n} \) counting balanced parentheses, binary trees, non-crossing partitions, and paths below the diagonal. First few values: 1, 1, 2, 5, 14, 42.

Why it matters for interviews

Catalan numbers appear in ballot problems, random walk counting, and tree enumeration -- all common in quant interviews. Recognizing when a counting problem yields Catalans is a valuable pattern-matching skill.

Definition and Mathematical Foundation

The sequence \( C_n = \frac{1}{n+1}\binom{2n}{n} \) counting balanced parentheses, binary trees, non-crossing partitions, and paths below the diagonal. First few values: 1, 1, 2, 5, 14, 42.

Application in Quantitative Finance

Related Concepts

Catalan Numbers

Related Terms

Ready to practice for the Quant Trading Interview?

Adaptive practice powered by Item Response Theory targets your weak areas. Start with 3 free sessions.

Start free practice →

Frequently Asked Questions

What objects do Catalan numbers count?▼

Balanced parenthesizations, full binary trees with n+1 leaves, paths from (0,0) to (2n,0) that never go negative, non-crossing partitions, triangulations of polygons, and many more -- over 200 known interpretations.

What is the recurrence for Catalan numbers?▼

\( C_0 = 1 \), \( C_{n+1} = \sum_{i=0}^n C_i C_{n-i} \). This convolution recurrence corresponds to the generating function \( C(x) = \frac{1 - \sqrt{1-4x}}{2x} \).

How do Catalan numbers relate to the ballot problem?▼

The ballot problem asks for the probability that candidate A stays ahead throughout the count. The reflection principle and Catalan numbers provide the answer: \( \frac{a-b}{a+b} \) when A gets a votes and B gets b votes.