Let $$f:[2n]\to[2n]$$ $[2n]=\{1,...,2n\}$. Furthermore, $\\ f(x)\ne x, f(f(x))=x$
And $\forall x<y$ with $f(x)>x$ follows $f(x)<y$ or $f(x)>f(y)$
I have to proof that for the number of those functions we have $a_n=C_n$, where $C_n$ are the Catalan-Numbers.
Can anyone give me a hint how to approach such a problem? I know that $$C_n=\sum_{i=0}^nC_{i-1}C_{n-i}$$
Any help is greatly appreciated!
Sketch of the proof. It's well-known that $n$-th Catalan number $C_n$ counts the number of expressions containing $n$ pairs of parentheses which are correctly matched. For example, for $n=3$ it's $$ ((())),\space ()(()),\space ()()(),\space (())(),\space (()())). $$
For every such sequence of parentheses we can divide the set $\{1,2,\ldots, 2n\}$ into $n$ pairs in the following way: numbers $a$ and $b$ are in the same pair if $a$-th and $b$-th elements of the sequence are corresponding parentheses. For example, if $n=3$ and we have sequence $((()))$ we divide $\{1,2,\ldots, 6\}$ into pairs $\{(1,6),(2,5),(3,4)\}$. If we have $(())()$ then we divide $\{1,2,\ldots, 6\}$ into pairs $\{(1,4),(2,3),(5,6)\}$.
Now, for such $n$ pairs $(a_1, b_1), \ldots, (a_n, b_n)$ we can consider function $f\colon\{1,2,\ldots,2n\}\rightarrow \{1,2,\ldots,2n\}$ which maps $x$ to element $y$ such that $(x,y)\in \{(a_k, b_k)|1\leq k\leq n\}$. It's easy to prove that the function $f$ is satysfying all conditions of the problem. Also, it's not hard to prove that this is a bijection between such functions and correct expressions containing $n$ pairs of parentheses.
