Catalan numbers

Challenge

Implement:

long long catalan(int n);

Return the n-th Catalan number (1, 1, 2, 5, 14, 42, ...). 0 <= n <= 33.

Input format

n in [0,33].

Output format

The n-th Catalan number.

Constraints

Use long long; grows quickly.

Starter code

#include <stddef.h>
/* The n-th Catalan number (C0=1, C1=1, C2=2, C3=5, ...). 0<=n<=33. */
long long catalan(int n){ (void)n; return 0; }

Common mistakes

Off-by-one in the convolution indices.

Edge cases to handle

C0 = 1.

Background lessons

• Counting-ways DP