Easy Random Trees

Rigorous Nonsense Home Archive Easy Random Trees Posted on February 27, 2026 by Brandon Wilson Tags: math, apl, trees Can you think of a way to efficiently generate a random plane tree? Richard P. Stanley in his book Catalan Numbers has a really nifty combinatorial proof of why Catalan numbers have the formula \[ C_n = {1 \over n+1}{2n \choose n} \] The standard proof uses generating functions applied to an inductive definition of the Catalan numbers, which frankly does little to illumiate their