GoKawiilEasy Random Trees
Posted on February 27, 2026 by Brandon Wilson
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 connection with combinatorial objects, despite the fact that the appearance of a binomial coefficient gives a hint that it’s counting something, and the division suggests we might be looking at some kind of equivalence class.
Stanley’s proof is so direct and beautiful, I cannot help but share. However, let us instantiate the proof as a little program that generates a random tree with \(n\) nodes:
D←{n←⍵-1 ⍝ The ⍵-1st Catalan number counts number of ⍵-node trees x←x[?⍨≢x←1⍪(n⍴1)⍪n⍴¯1] ⍝ Random step vector of length 1+2×⍵ d←0⍪¯1↓+⍀x ⍝ Depth vector i←⊃⌽⍸(⌊⍀d)=d ⍝ Righmost lowest node x⌽⍨←i ⍝ Strict ballot sequence d←¯1+(x=1)⌿+⍀x ⍝ Corresponding tree node depths }
At center stage here is the isomorphism between plane trees and strict ballot sequences, which is directly connected via the depth vector tree representation, which I’ll assume is already familiar to readers here. The image to have in mind is a depth-first search traversal pattern.
Depth-first search tree traversal
... continue reading