Catalan numbers are a good thing
Calculation#
- $f(n)=\sum_{i=0}^{n-1}f(i)\cdot f(n-1-i)$
- $f(n)=\frac{(4n-2)\cdot f(n-1)}{n+1}$
- $f(n)=\frac{C_{2n}^{n}}{n+1}$
Applications#
-
Number of binary tree shapes with n nodes
-
Number of sequences for n elements in stack and unstack operations
Legal stack and unstack sequences: in any prefix of the sequence,
number of stack operations >= number of unstack operations -
Dividing a convex polygon with
(n+2)edges into triangles by connecting vertices -
Almost all Catalan number problems can be transformed into "complete n steps of k1 operations and n steps of k2 operations, where the number of k1 operations must always be greater than the number of k2 operations"
Actual Problem-solving Process#
The experts prove that this problem is related to Catalan numbers.
As a novice, I can only calculate the first three terms (1, 2, 5), and then
"Bold and reasonable extrapolation" - hqx expert
"You should add something like Galileo did in front" - hqx expert