# Number of discrete functions such that $f(f(f(x)))=x$

The problem is:

For $f:X\rightarrow X$, where $X$ has $n$ distinct elements, how many different $f$ exist that meet $f(f(f(x)))=x$ for all $x\in X$?

I can calculate for small number of $n$'s by the following way (for example, $n=8$):

case-1) $f$ is an identity function ($f(x)=x$) for all $x$.

case-2) $f$ is an identity function for 5 elements in $X$ and for the rest of 3, it is cyclic, i.e. $f(a)=b,f(b)=c,f(c)=a$.

case-3) $f$ is an identity function for 2 elements in $X$ and for the rest of 6, it can be divided into two groups of each having 3, and each groups are cyclic.

As there are only two different ways of being cyclic (1,2,3 or 1,3,2), the number of functions for $n=8$ can be calculated as:

$$1+\binom85\cdot2+\binom82\binom63\frac12\cdot2^2=1233$$

I could also generalize it for any $n$ as:

$$n=3m+p\quad (p=0,1,2)$$ $$a_n=\sum_{k=0}^m\left(\binom{n}{n-3k}\cdot2^k\cdot\frac1{k!}\prod_{i=0}^{k-1}\binom{n-3k}{3}\right)$$

And then I found that $a_n$ are $1,1,3,9,21,81,351,1233,\dots$ that is the sequence in this link https://oeis.org/A001470/internal. In the link, it shows a simple recurrence equation of

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

But I can't figure out how one can reach to that recurrence equation.

So my question is "how one can reach to the above recurrence equation"?

• For continuous complex functions, consider $f(x)=e^{2k\pi i/3}x$ Jan 8, 2017 at 23:26
• @SimpleArt From the question body, this is quite clearly about permutations of finite sets. Jan 8, 2017 at 23:31
• Obviously $f$ is one-to-one. I think you're looking for permutations of $\{1,...,n\}$ that are products of disjoint $3$-cycles. Jan 8, 2017 at 23:34
• @LeGrandDODOM This is all explained in the question, if you just read it. Jan 8, 2017 at 23:41
• @LeGrandDODOM: I believe OP understands this and is just looking to justify the recurrence s/he found. Jan 8, 2017 at 23:42

To understand the recurrence, note that a function on a set of $n$ members can either fix the last member or not. If the last member is fixed, you have a function on the first $n-1$ members. If the last member is not fixed, you have $n-1$ choices of the next element in its cycle, $n-2$ choices for the third element in its cycle, and a function on the remaining $n-3$ elements.
• @martycohen: yes, it does. That is what makes the question so good. OP gave it a lot of thought, found the OEIS entry so we had data to work with, and asked a clear question. It seemed like there ought to be a bijection approach to the answer. The $n-3$ term was a strong clue. Jan 8, 2017 at 23:48
• @KayK.: I would leave what you had as it is an accurate quote from OEIS. When $n$ appears in the recurrence a shift in the base of the list changes the recurrence. You could add in the new version as a PS edit if you want. As an example, you found there were three functions for $n=3$, which is correct. Now for $n=4$ we can either have $f(4)=4$ in which case you just have one of the previous functions on the first three elements, or you have $f(4)=$ something else. There are $3$ choices for $f(4)$ and $2$ choices for $f(that)$, then you have to finish the cycle. That leaves just one Jan 9, 2017 at 0:09