Consider the set Fn of factorizations of the full cycle (0 1 2 · · · n) ∈ S{0,1,...,n} into n transpositions. Write any such factorization (a1 b1) · · · (an bn) with all ai < bi to define its lower and upper sequences (a1, . . . , an) and (b1,...,bn), respectively. Remarkably, any factorization can be uniquely recovered from its lower (or upper) sequence. In fact, Biane (2002) showed that the simple map sending a factorization to its lower sequence is a bijection from Fn to the set Pn of parking functions of length n. Reversing this map to recover the factorization (and, hence, upper sequence) corresponding to a given lower sequence is nontrivial.
Discrete Mathematics & Theoretical Computer Science