Functions from $A$ to $A$ Let $A=\{1,2,3,4,5,6\}$. How many distinct functions are there from $A$ to $A$ such that $f(f(f(n)))=n$ for all $n\in A$?
I tried this lot but still I can't get an answer.
Thanks.
 A: First of all, let's establish the possibilities for the cycle structure on this permutation (i.e. bijective function from $A$ to $A$).
Of course, if $f(n) = n$ for all $n$, then that works.
Suppose that this is not the case.  That is, suppose that there is an $a$ such that $f(a) \neq a$.  Let $b = f(a)$.  Note that we can't have $f(b) = a$ or $f(b) = b$ (why?), so there must be a third element $c$ such that $f(b) = c$.  Now, what about $c$?  Well, note that $f(c) = f(f(f(a)))$.  So, it must be the case that $f(c) = a$. 
That is, our function must act on some element $a$ via the cycle $a \to b \to c \to a$.  
Now, $f$ must do something to the remaining elements $d,e,f$.  By the above logic, there are two possibilities: either $f(n) = n$ for $n = d,e,f$, or we have another cycle $d \to e \to f \to d$.
Now: let's count.
In how many ways can we build a two-cycle permutation 
$$
a \to b \to c \to a, \quad d \to e \to f \to d
$$
There are $6 \times 5 \times 4$ ways to select the elements $a,b,c$.  However, this method counts each cycle three times (for instance, $1 \to 2 \to 3 \to 1$ is the same as $2 \to 3 \to 1 \to 2$), so there are $\frac{6 \times 5 \times 4}{3}$ ways to select the first cycle.  There are $3 \times 2 (\times 1)$ ways to select $d,e,f$ (having already selected $a,b,c$), but once again we must divide by $3$.   So, there are $\frac{6 \times 5 \times 4}{3} \times \frac{3 \times 2}{3}$ ways to select $2$ 3-cycles successively.  This counts each such permutation twice, so we divide by 2.  All together, there are
$$
\frac{6 \times 5 \times 4 \times 3 \times 2}{3 \times 3 \times 2} = 40
$$
ways to select such a permutation.
By a similar argument, there are exactly 
$$
\frac{6 \times 5 \times 4}{3} = 40
$$
ways to select a permutation with one $3$-cycle.  Finally, we also have the constant function.  All together, there are
$$
1 + 40 + 40 = 81
$$
functions with the desired property.
A: Any such $f$ must be $1$-to-$1.$ For if  $f(x)=f(y)$ then $x=f^3(x)=f^2(f(x))=f^2(f(y))=f^3(y)=y.$
So $f$ is a Permutation of $\{1,...,6\}.$ That is , $f$ is a bijection.
For $x\in \{1,..,6\},$ the sequence $f^n(x)$ for $n=1,2,3,...(etc)$ must contain duplicates.  If $f^n(x)=f^{n+m}(x)$ with $m>0,$ then, as $f^{-n}$ is also a bijection, we have $x=f^{-n}(f^n(x)) =f^{-n}(f^{n+m}(x))=f^m(x).$ 
Let $\|x\|$ denote the least  $m>0$ such that $f^{m}(x)=x.$ The set $F(x)=\{f^j(x):1\leq j\leq \|x\| \}$ is a Cycle of the Permutation $f.$ 
We have  $F(y)=F(x)\iff y\in F(x)$ and  we have $F(y)\cap F(x)=\phi \iff F(y)\ne F(x)\iff y\not \in F(x).$ So $\{F(x):x\in \{1,...,6\}\;\}$ is a partition of $\{1,...,6\}.$ 
In order that $f^3(x)=x$ for every $x,$ it is necessary and sufficient that each $F(x)$ has exactly $1$ member or exactly $3$ members.
(i). If every $F(x)$ has just $1$ member, then $f(x)=x$ for every x. This gives $1$ function of this type.
(ii). If $F(x)$ has just $1$ member for each of $3$ different $x,$ and some $F(y)$ has $3$ members, there are $\binom {6}{3}=20$ partitions  of this type. And for each such partition, there are exactly $2$ allowable $f.$ ....Because if $F(y)=\{y,z,a\}$ with $y\ne z\ne a \ne y$ then either $f(y)=z,  f(z)=a, f(a)=y$ , or $f(y)=a,f(a)=z,f(z)=y$.... This gives $2\cdot\binom {6}{3}=40$ functions of this type.
(iii). If there are disjoint $F(x), F(y$) each with $3$ members, there are $10$ partitions of this type.... Because if $F(1)=\{1,a,b\}$ with $1\ne a\ne b \ne 1$ there are $\binom {5}{2}=10$ choices for $\{a,b\}.$ And for each such partition, there are just $2$ choices for $f(x).$ And also just $2$ choices for $f(y)$, and they do not depend on the choice of $f(x).$ So there are $2^2\cdot 10=40$ functions of this type.
Altogether  we have $1+40+40=81$ functions.
