Suppose $\sigma\in S_{n}$ is written in cycle notation, with its fixed points included. We say $\sigma$ is written in canonical cycle notation if each cycle is rotated such that its smallest element is last, and the cycles are arranged in ascending order of their last elements.
For example, $(351)(462)(87)(9)$ is in canonical form.
Define the function $f:S_{n}\to S_{n}$ by removal of parentheses, with the image interpreted in one-line notation. Prove that $f$ is bijective.
This is one of those things that seems pretty obvious but I'm having trouble formalising it. It's Foata's fundamental transformation, and the only proof I can find of it is his original one, which is in french.
NB. I realise that this is not the typical definition of canonical form.
Hint: in the permutation written in one line notation $$ 351462879 $$ you have enough information to restore the parentheses.
Can you see why $1$ must end the first cycle? Then $2$ the next, and so on.