Computing the number of possibilities of functions.

Question

Suppose $A$ is a set of n distinct elements.What is the number of functions $f:A\to A$ satisfying $f(f(x))=x$ for $x\in A$?

Answer 1

Such functions are self-inverse permutations, or involutions. If $f$ is an involution on $A$, for each $a\in A$ there are two possibilities: either $f(a)=a$, or there is a $b\in A\setminus\{a\}$ such that $f(a)=b$ and $f(b)=a$. For each involution $f$ on $A$ let

$$F(f)=\{a\in A:f(a)=a\}\;,$$

the set of fixed points of $f$, and let $P(f)=A\setminus F(f)$. Then $P(f)$ must have an even number of elements, because $P(f)$ can be partitioned into pairs $\{a,b\}$ of distinct elements such that $f(a)=b$ and $f(b)=a$. Thus, $P(f)$ can be split into $k$ pairs for some $k$ between $0$ and $\left\lfloor\frac{n}2\right\rfloor$ inclusive.

There are $\binom{n}{2k}$ ways to choose a subset of $A$ to be $P(f)$. This question tells you that there are $\frac{(2k)!}{2^kk!}$ ways to divide a set of $2k$ objects into pairs. Thus, for $k=0,\ldots,\left\lfloor\frac{n}2\right\rfloor$ there are $\binom{n}{2k}\cdot\frac{(2k)!}{2^kk!}$ ways to choose a function $f$ for which $|P(f)|=2k$. Summing over the possible values of $k$, we see that there are

$$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}\frac{(2k)!}{2^kk!}=\sum_{k=0}^{\lfloor n/2\rfloor}\frac{n!}{2^kk!(n-2k)!}$$

involutions on $A$.

If $a_n$ is the number of involutions on a set of cardinality $n$, the sequence $\langle a_n:n\in\Bbb N\rangle$ is OEIS A000085 in The On-Line Encyclopedia of Integer Sequences. The FORMULA section of the entry indicates that no nice closed form is known, though there is a nice recurrence:

$$a_n=a_{n-1}+(n-1)a_{n-2}$$

for $n>1$, with initial values $a_0=a_1=1$. You should try to see why this recurrence holds; the reasoning is fairly straightforward.