Tags: #theorem

Statement

The number of records of a permutation is equidistributed to the number of cycles. In other words, records is Sterlingian.

Proof

We shall construct a bijection between $f:S_n\to S_n$ such that $\mathrm{cyc}(w)=\mathrm{rec}(f(w))$.

Take some $w\in S_n$ and write it in cycle notation. Specifically, we choose the notation such that:

• in each cycle, the first element is the maximal element of the cycle
• the cycles are arranged such that the first elements are in increasing order

For example, $(2,5,3)(1,6)(4)\to (4)(5,3,2)(6,1)$

Then, our map is just converting this to a 1-line notation by removing all the parenthesis.

We note that the records of this permutation is the first element of each cycle.

Now to construct the inverse:

• At the start, add $($
• Every time we have a record, insert $)($ before it
• Add a $)$ at the end
  

These two maps are evidently inverses of each other.