Published by Dimitris Kougioumtzis · Updated
Use the recurrence C(n) = Σ C(i)C(n−1−i), with C(0)=1.
Sum products of smaller Catalan values for every left/right split, making a structural counting recurrence explicit.
When to use Catalan numbers
Counting balanced parentheses and ordered binary-tree shapes.
Choosing an alternative
A binomial closed form computes the same sequence through a different formulation.
Worked example: input and state changes
Example input
10
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [] }Step 14: C(5) adds C(2) × C(2) = 4.
State at this checkpoint
{ "values": [ 1, 1, 2, 5, 14, 23, 0, 0, 0, 0, 0 ], "active": [ 5 ] }Step 29: C(7) adds C(6) × C(0) = 132.
State at this checkpoint
{ "values": [ 1, 1, 2, 5, 14, 42, 132, 429, 0, 0, 0 ], "active": [ 7 ] }Step 43: C(9) adds C(5) × C(3) = 210.
State at this checkpoint
{ "values": [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 2739, 0 ], "active": [ 9 ] }Step 57: Catalan number = 16796.
State at this checkpoint
{ "values": [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 ], "active": [ 10 ] }
Expected final state
Catalan number = 16796.
Complexity and input bounds
Family: Number theory. Time complexity: O(n²).
Space complexity: O(n) DP values.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
One integer from 0 to 15.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
C(0)=1 represents an empty structure; values grow quickly beyond fixed-width bounds.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 | // n from 0 to 15. Returns Catalan number C(n), bounded to fit signed 32-bit integer arithmetic. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(n) { let dp = Array(256).fill(0); dp[0] = 1; for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - 1 - j]; } } return dp[n]; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)
Donald E. Knuth (1997). Reference book.