Catalan and Other Special Numbers

Catalan numbers

$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right),C_{n+1}={\sum }_{i=0}^n{C}_i{C}_{n-i}.$

$1,1,2,5,14,42,132,429,1430,4862,16796,\dots$

Also $C_n=\frac{2(2n-1)}{n+1}{C}_{n-1}$, which computes them in $O(n)$ with one inverse per step.

What Catalan numbers count

Object	Count
Balanced bracket sequences of length $2n$	$C_n$
Binary trees with $n$ internal nodes	$C_n$
Triangulations of a convex $(n+2)$-gon	$C_n$
Monotone lattice paths below the diagonal	$C_n$
Ways to parenthesise $n+1$ factors	$C_n$
Non-crossing chord diagrams on $2n$ points	$C_n$
Permutations avoiding any fixed 3-pattern	$C_n$
Standard Young tableaux of shape $2\times n$	$C_n$
Mountain ranges with $n$ up and $n$ down strokes	$C_n$

These are all the “same” object under bijection — recognising one lets you count all the others.

The reflection principle

Paths from $(0,0)$ to $(n,n)$ using right/up steps that never cross the diagonal:

$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)=C_n.$

The subtracted term counts the bad paths, put in bijection with unrestricted paths to $(n+1,n-1)$ by reflecting the portion after the first violation. This reflection argument generalises to the ballot problem and to paths with other boundary constraints — it is the technique, not the formula, that is worth learning.

Ballot problem: the number of paths from $(0,0)$ to $(a,b)$ with $a>b$ staying strictly above the diagonal is $\frac{a-b}{a+b}\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$.

Stirling numbers

Second kind $S(n,k)$ — partitions of $n$ labelled objects into $k$ non-empty unlabelled blocks:

$S(n,k)=kS(n-1,k)+S(n-1,k-1),S(n,k)=\frac{1}{k!}{\sum }_{j=0}^k(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})(k-j{)}^n.$

The closed form is an inclusion-exclusion over which blocks are empty, computable in $O(k\log n)$.

First kind $c(n,k)$ (unsigned) — permutations of $n$ elements with exactly $k$ cycles:

$c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1).$

Bell numbers $B_n={\sum }_{k}S(n,k)$ — all set partitions of $n$ elements: $1,1,2,5,15,52,203,877,\dots$ (Catalan and Bell agree up to $n=2$ then diverge).

$B_{n+1}={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)B_k.$

Surjections and derangements

Surjections from $n$ elements onto $k$: $k!S(n,k)={\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})(k-j{)}^n$.

Derangements $D_n$ — permutations with no fixed point:

$D_n=(n-1)(D_{n-1}+D_{n-2})=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}\approx \frac{n!}{e}.$

$1,0,1,2,9,44,265,1854,\dots$

Permutations with exactly $k$ fixed points: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)D_{n-k}$.

Other sequences worth recognising

Sequence	Counts	Start
Motzkin $M_n$	lattice paths with up/down/flat steps	1,1,2,4,9,21,51
Narayana $N(n,k)$	brackets with exactly $k$ peaks; ${\sum }_{k}N=C_n$
Schröder	paths with diagonal steps	1,2,6,22,90
Eulerian $A(n,k)$	permutations with $k$ descents
Fibonacci	see Fibonacci	1,1,2,3,5,8
Partition $p(n)$	integer partitions	1,1,2,3,5,7,11
Delannoy	paths with diagonal steps, unrestricted

Look it up

When a counting problem produces an unfamiliar sequence, compute the first 6-8 terms by brute force and search OEIS. It very often names the sequence, gives a closed form or recurrence, and links a proof. This is a legitimate and highly effective contest technique.

Computing modulo a prime

All of the above have $O(n)$ or $O(n^2)$ DP forms and $O(1)$-per-query closed forms once factorials and inverse factorials are precomputed. Watch for:

• $\frac{1}{n+1}$ in the Catalan formula needs a modular inverse;
• the inclusion-exclusion forms need alternating signs handled with (MOD - x) % MOD;
• Stirling numbers for a whole row can be computed by one convolution in $O(k\log k)$.

See also: Combinatorics · Generating Functions · Burnside and Pólya