Easy Random Trees
a day ago
- #combinatorial proofs
- #random trees
- #Catalan numbers
- The text introduces Stanley's combinatorial proof for the Catalan numbers formula using the isomorphism between plane trees and strict ballot sequences.
- Random plane trees can be generated via a program that converts random sequences of 1s and -1s into depth vectors, applying rotation to enforce strict ballot conditions.
- The proof yields a formula for Catalan numbers as C_n = (1/(2n+1)) * C(2n+1, n), and notes its relationship to counting plane trees with n+1 nodes.
- The connection between depth vectors from DFS traversal and strict ballot sequences is explained, providing a concrete method for tree representation.