Brandon Wilson shows how ballot-sequence rotation converts any random ±1 sequence into a strict ballot sequence, yielding a compact APL random plane-tree generator and a direct proof of the Catalan number formula.
Key Takeaways
Plane trees with n+1 nodes biject with strict ballot sequences of length 2n+1 via depth-first traversal encoding; partial sums give the depth vector directly.
A random ±1 sequence (n+1 ones, n negative ones) becomes a strict ballot sequence by rotating at the index of the rightmost lowest partial sum.
The rotation argument also proves C_n = (1/2n+1) * C(2n+1,n) combinatorially, since gcd(n, 2n+1)=1 guarantees no two rotations collide.
The full generator fits in ~5 lines of APL using scan, grade, and rotate primitives.
Stanley’s Catalan Numbers is cited as the source of the core isomorphism; the post instantiates it as executable code.
Hacker News Comment Review
The single comment notes the construction is surprisingly intuitive for a topic that usually requires heavy generating-function machinery, and flags generative graphics and random UI/tree structures as natural application areas.
No substantive technical disagreement or caveats surfaced; practical limits (performance at large n, non-plane trees) were not discussed.
