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 pushing and popping n elements
Legal push-pop sequences: in any prefix of the sequence,
number of pushes >= number of pops -
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 operation k1 and n steps of operation k2, where the number of k1 operations is always 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 in front" - hqx expert