-3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I'm not actually sure if this was known or not, so feel free to comment if it was or if there things like that. $\endgroup$ – Juan Sebastian Lozano Apr 27 '16 at 10:58
  • $\begingroup$ Posting a question you already knew the answer to is frowned upon here. $\endgroup$ – Todd Trimble Apr 27 '16 at 11:32
  • $\begingroup$ Sorry, I didn't know that. Like I said below: I put it here mainly as a reference for anyone (like me) who might be looking for the answer, since I couldn't find it anywhere. I think that's pretty much why SE lets you answer your own questions, but that might be (slightly) more common over at Math.SE . $\endgroup$ – Juan Sebastian Lozano Apr 27 '16 at 11:34
  • $\begingroup$ Should I delete this question? $\endgroup$ – Juan Sebastian Lozano Apr 27 '16 at 11:36
  • 1
    $\begingroup$ Oh, by the way: "self-inverse" is fine, but I think it's more common to call such permutations involutions. $\endgroup$ – Todd Trimble Apr 27 '16 at 12:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! Although that question goes above my head, I can see that my exact sum is found in the second answer. $\endgroup$ – Juan Sebastian Lozano Apr 27 '16 at 11:01
0
$\begingroup$

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}\}$$

$\endgroup$
  • 3
    $\begingroup$ You posted this answer along with your question in the same minute. So I wonder why you actually asked the question if you already had the answer ? $\endgroup$ – Todd Leason Apr 27 '16 at 11:23
  • $\begingroup$ Two reasons: 1) I didn't know if this was known, since I couldn't find it anywhere, and I wanted to see if it was even correct, and 2) as a reference for anyone (like me) who might be looking for the answer. I think that's pretty much why SE lets you answer your own questions. $\endgroup$ – Juan Sebastian Lozano Apr 27 '16 at 11:32
  • $\begingroup$ There are several similar "closed" formulas (in terms of sums) in OEIS. $\endgroup$ – Alex Degtyarev Apr 27 '16 at 11:34
  • $\begingroup$ @AlexDegtyarev Although my idea of counting the number of graphs isn't novel (it's listed as Don Knuth's contribution on OIES), and there are a few other ones in terms of sums of other sequences, I couldn't find one with an explicit form like this. $\endgroup$ – Juan Sebastian Lozano Apr 27 '16 at 11:42
  • 1
    $\begingroup$ See for example math.stackexchange.com/questions/795541/involutions-of-s-n or google for "number of involutions in symmetric group". BTW: According to the acctepted SE answer the product in your formular can be resolved. $\endgroup$ – Todd Leason Apr 27 '16 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.