What is the number of self-inverse permutations on a set of cardinality $N$?

Question

Given a function (aka 'permutation') $f:A \rightarrow A$, where $A$ is a finite set such that $|A| = N$, we call it a self-inverse if $f(f(x)) = x$. The sequence of how many such functions exist for increasing cardinalities is given by OEIS A000085. As far as I can tell, there is only a recursive formula for this sequence, is there a general formula?

Answer 1

The answer to this question is closely related to the answers to the question representations of $S_k \times S_j$ (in the special case $j = N, k = 1$ which most answers actually concern themselves with), since the number you seek is also the sum of the degrees of the irreducible complex characters of $S_{N}$. As you write down, there is a precise summation formula for the number you want. However, there has been quite a bit of work on asymptotic estimates for it.

Answer 2

This problem is equivalent to asking the number directed graphs $G$ such that every vertex of $G$ has an outdegree of $1$, and every vertex sits in exactly one cycle of length at most $2$.

Taking the case of $N = 4$ we can easily construct the number, which OEIS tells us is $10$ (I am copy and pasting from my question here):

Case 1: All cycles are of length 1. This is equivalent to the identity function, which we know is unique. However from a graph theoretic point of view this is equal to $\binom{4}{4}$ because we are choosing 4 vertices to have cycle length one (notice that order does not matter because cycles start and end in the same place, and if two functions have the same cycles regardless of order they are equal). $\binom{4}{4} = 1$, consistent with what we know about the identity.

Case 2: One cycle is of length 2, and 2 are of length one. We know that the two of length one are chosen by $\binom{4}{2}$ and the reaming two vertices are forces to be in the cycles of length two (or are 'chosen' by $\binom{2}{2}$).

Case 3: 2 cycles of length 2, which is the same amount of choices as above, since the two remaining ones are forced to be the cycle, however, because there are $2!$ ways to range two cycles we must divide by $2!$, giving $3$.

Summing the amounts of functions from the three cases we get $10$.

In more generality we know that we will have similar cases. Specifically, the identity will always exist, and we will have to sum over the cases of having $i= 1,2,..,\lfloor \frac{N}{2} \rfloor$ $2$-cycles (since we can not have more than $\lfloor \frac{N}{2} \rfloor$ $2$-cycles on $N$ vertecies if every vertex sites in just one cycle), and we will have to divide by the number of ways there are to permute $i$ cycles.

For each case, we know this is the compound of choices, meaning we first have $\binom{N}{2}$ choices and then we much take $\binom{N-2}{2}, ...,\binom{N-2i}{2}$ choices corresponding to the $i$ cycles. So we will have the product $\prod\limits^{i}_{n=0} \binom{N-2n}{2}$. Summing all the cases (where we start with the case with one $2$-cycle, and adding 1 for the identity):

$$a(n) = 1+ \sum\limits^{\lfloor \frac{N}{2} \rfloor}_{i=1} \{\frac{1}{i!} \prod\limits^{i-1}_{n=0} \binom{N-2n}{2}\}$$