# What is the number of functions $f : A\rightarrow A, \forall_{x\in{A}} f(f(x))=x$, set $A$ have $n$ distinct elements.

What is the number of functions $f : A\rightarrow A, \forall_{x\in{A}} f(f(x))=x$, set $A$ have $n$ distinct elements.

For $A=\{a,b,c,d\}$ we could look on the right-upper triangle of matrix of all possible pairs (? better word needed here) - below. For $a$ we have four possibilities but if we choose $a->b$ for example, then we have to delete second column. Without deletation we would have $4!$ functions $f$ for $A=\{a,b,c,d\}$, but there is only 1+6+3 of them.

$a->a,a->b,a->c,a->d \\ ........b->b,b->c,b->d \\ ................c->c,c->d \\ ........................d->d$

I think that if $n=2k$ then we could choose first $k$ elements so we have $k$ sets with single element then for each elements with number $k+1 : 2k$ we assign $0$ or $1$. $0$ if $a_{i}->a_{i}$ and $1$ if $a_{i}->a_{1 : n}$, for $i\in k+1:2k$, so we have $2^k$ possibilities. If $j$, $1's$ have been assigned then we have $\binom{k}{j}$ possibilities for two element sets and ... I'm out of ideas.

You could edit my post this is welcome.

-
In other words, the number of permutations $\sigma\in S_n$ such that $\sigma^2=e$. If you're familiar with the terms, consider the cycle decomposition of these $\sigma$'s. (Apparently, the answer isn't terribly simple, though.) – anon May 17 '12 at 18:30
yes, it's the essence of my question – Qbik May 17 '12 at 18:33
I don't get the tagging. This is neither set theory nor category theory related. – Asaf Karagila May 17 '12 at 18:33
– anon May 17 '12 at 18:38

Let $B$ denote a set of size $n+1$ with $B=A\cup\{o\}$, $A$ of size $n$, and $o$ not in $A$. Let $f$ denote an involution of $B$. Then:
• Either $f(o)=o$, then $f$ is characterized by an involution of $A$.
• Or $f(o)\ne o$, then there are $n$ possible choices of $f(o)=a$ with $a$ in $A$. Once $a$ is fixed, one knows that $f(a)=o$ hence $f$ is characterized by an involution of $A\setminus\{a\}$.
Let $i_n$ denote the number of involutions of a set of size $n$. One sees that $i_1=1$, $i_2=2$, and that the recursion $i_{n+1}=i_n+ni_{n-1}$ holds, for every $n\geqslant2$. This characterizes the sequence $(i_n)_{n\geqslant1}$.