Let $f(n)$ be the number of permutations $\tau$ on a set of $n$ elements such that $\tau \circ \tau$ is the identity permutation. We can calculate that $f(1) = 1$ and $f(2) = 2$ . If $n=3$ , the first element could either remain in position, or be moved to another position. If it remains in position, the number of ways to permute the remaining 2 elements is given by $f(2)$ . There are 2 ways for it to change positions, either to the second or third position. In each case, if the first element is shifted to another position, the element in that position must be shifted to the first position for $\tau \circ \tau$ to be the identity permutation. This leaves just one element behind to permute. ( $f(1)=1$ way to permute) From this: $f(3) = f(2) + 2f(1) = 2+2=4$ .

The more general case holds similarly. If the first element remains in position, there are $f(n-1)$ ways. Otherwise, it has $n-1$ places to be permuted to, and that element must be shifted to the first position, so there are $f(n-2)$ ways to permute the remaining element. Hence, $f(n) = f(n-1) + (n-1)f(n-2)$ .

Working up to $f(8)$ gives: $f(3) = 4$ $f(4) = 4+2*3 = 10$ $f(5) = 10 +4*4 = 26$ $f(6) = 26 + 5*10 = 76$ $f(7) = 76 + 6*26 = 232$ $f(8) = 232 + 7*76 = 764$ There answer to the problem is $764$ .

[Edits for clarity - Calvin]

Firstly, note that when one of the elements is moved to another position in the ordering, it has to be moved back after another shuffle. Thus elements can only be swapped in pairs.

Thus we come with our 5 cases: No pairs swapped, 1 pair swapped, 2 pairs swapped, 3 pairs swapped or 4 pairs swapped.

Case 1: No pairs swapped. This corresponds with the identity permutation.

Case 2: One pair swapped. This corresponds to an arrangement of 2 "1"s and 6 "0"s. Example: 00100010 means the third card (Third position is a 1) and the seventh card (seventh position is a 1) are swapped.

Total in this case $= \frac{8!}{2! \times 6!} = 28$ .

Case 3: 2 pairs swapped. This corresponds to an arrangement of 2 "1"s, 2 "2"s and 4 "0"s, then divided by 2.

Note that 00212010 and 00121020 mean the same thing: 3rd card is swapped with 5th card, 4th card is swapped with 7th card. Thus we have to divide by 2.

Total in this case $= \frac{8!}{4! \times 2! \times 2! \times 2} = 210$ .

Case 3: 3 pairs swapped. This corresponds to an arrangement of 2 "1"s, 2 "2"s, 2 "3"s and 2 "0"s, then divided by 6.

Note that there are 6 ways to write a swapping by permuting the "1"s, "2"s and "3"s. Thus we have to divide by 6.

Total in this case $= \frac{8!}{2! \times 2! \times 2! \times 2! \times 6} = 420$ .

Case 4: 4 pairs swapped. This corresponds to an arrangement of 2 "1"s, 2 "2"s, 2 "3"s and 2 "4"s, then divided by 24.

Note that there are 24 ways to write a swapping by permuting the "1"s, "2"s, "3"s and "4"s. Thus we have to divide by 24.

Total in this case $= \frac{8!}{2! \times 2! \times 2! \times 2! \times 24} = 105$ .

Thus the total number of permutations $=1+28+210+420+105=764$

Let the 8 elements be $a???????$ . WLOG, let $\tau$ include moving the element in the 1st position, $a$ , to the 3rd position. That is, $\tau(a???????)=??a?????$ .

Since $\tau \circ \tau(a???????)=\tau(??a?????)=a???????$ , then $\tau$ must also include moving the element in the 3rd position to the 1st position.

Hence, $\tau$ should exchange the position of elements in a pair.

To exchange elements in:

(a) 0 pairs, there is 1 way. This counts as 1 $\tau$ .

(b) 1 pair (which involves 2 elements), there are $8C2=28$ ways to choose 2 elements. These count as 28 $\tau$ 's.

(c) 2 pairs (which involves 4 elements), there are $8C4=70$ ways to choose 4 elements. To pair up the 4 elements, say $abcd$ , there are 3 possible options for the pair of $a$ . If $a$ is paired with $b$ , only 1 option is left for $c$ (or $d$ ). So there are 3 $\cdot$ 1=3 ways to form pairs out of 4 elements. These count as 70 $\cdot$ 3=210 $\tau$ 's.

(d) 3 pairs, there are $8C6=28$ ways to choose 6 elements. Using the counting technique above, there are 5 $\cdot$ 3 $\cdot$ 1=15 ways to pair up the 6 elements. These count as 28 $\cdot$ 15=420 $\tau$ 's.

(e) 4 pairs, there is 1 way to choose all 8 elements. Using the same technique, there are 7 $\cdot$ 5 $\cdot$ 3 $\cdot$ 1=105 ways to pair up the 8 elements. These count as 1 $\cdot$ 105=105 $\tau$ 's.

All in all, there are $764$ possible $\tau$ 's.

We can map every permutation $\tau$ to a function $f$ from the set $S =\{ 1,2,3,4,5,6,7,8\}$ to itself. For example, we will denote the permutation $(8,7,6,5,4,3,2,1)$ of $(1,2,3,4,5,6,7,8)$ as such:

$f(1) = 8, f(2) = 7, f(3) = 6, f(4) = 5,$ $f(5) = 4, f(6)=3, f(7) = 2, f(8)=1$ or, if making easier, $f(\text{previous position}) = \text{new position}$

We will call it the identity fucntion of a permutation $\tau$ .

Now, $\tau \circ \tau =$ identity implies that, all elements return to it's original positions after permuting it twice in that way, or as to say, if $f$ is the identity function of $\tau$ , then if $f(a) =b$ , then $f(b) = a$ , which also means $f(f(a)) = a$ for all $a \in S$ .

Now, If we can count the number of such functions then we are done. Notice that, if $f(a) = b, f(b) \neq a$ for some $f$ , identity function of $\tau$ , then $\tau$ does not meet the requirements. So, we need to find the number of functions $f: S \rightarrow S$ which satisfies $f(f(a)) = a$

Now, there is two options for some $f(a)$ , it can be equal $b$ , with $f(b) = a$ , or $f(a) = a$ , which would both imply $f(f(a)) =a$ .

Now, we can first select $i$ pairs of $(a,b)$ from $S$ and define $f$ sucht that $f(a) =b \text{ and } f(b)=a$ , and then define the remaining $f(x)$ 's as $x$ , i.e. define $f(x)=x$ for all else $x \in S$ .

Now, we can pick $i$ elements from $8$ in $\binom 8 i$ ways, then pick another $i$ elements and pair them with the previously picked $i$ elements in $\binom {8-i}i \cdot i!$ ways. But defining $f(x) =y$ is the same as defining $f(y)=x$ , as one implies the other, so if we pick $i$ pairs, we have to divide it by $2^i$ to avoid double counting. So, for $i$ pairs, we have total $\frac 1 {2^i}\binom 8i \binom {8-i}i i!$ ways to construct such an $\tau$ .

As the number of pairs can be $0$ to $4$ , the answer we need is $\sum _{i=0}^{5} \frac 1 {2^i}\binom 8i \binom {8-i}i i!$ , which is $\binom 8 0 \binom 8 0 × 0! +\frac 1 2 (\binom 8 1 \binom 7 1×1!)+$ $\frac 14 (\binom 8 2 \binom 6 2×2!)+ \frac 18 (\binom 8 3 \binom 5 3 ×3!)+ \frac 1{16} (\binom 8 4 \binom 4 4×4!)$ which equals to $764$ , which is the number of such $\tau$ s.

First, let us prove that for $\tau \circ\tau$ to be the identity permutation, the permutations come in pairs (i.e $a_1$ switches to $a_j$ while $a_j$ switches to $a_i$ ). Let us assume the contrary, that $a_i$ switches to $a_j$ , while $a_j$ switches to $a_k$ where $k\ne i$ . But when the permutation is done twice, $a_i$ , which is now at $a_j$ 's spot, must switch back to $a_i$ . However, we know that $a_j$ switches to $a_k$ , and since $k\ne i$ , we have a contradiction, and the proof is complete.

Now we have $5$ cases: $4$ switching pairs, $3$ pairs, $2$ pairs, $1$ pair, or $0$ pairs (the identity permutation itself).

$4$ pairs: $\dfrac{\binom{8}{2}\cdot\binom{6}{2}\cdot\binom{4}{2}\cdot\binom{2}{2}}{24}=105$ .

$3$ pairs: $\dfrac{\binom{8}{2}\cdot\binom{6}{2}\cdot\binom{4}{2}}{6}=420$ .

$2$ pairs: $\dfrac{\binom{8}{2}\cdot\binom{6}{2}}{2}=210$

$1$ pair: $\binom{8}{2}=28$

$0$ pairs: $1$ .

Adding these together, we get $105+420+210+28+1=\boxed{764}$ and we are done.

Essentially, the concept is this: $\tau$ must reverse anything it does.

More formally, if $\tau$ moves element $i$ to position $j$ , then it must move element $j$ to position $i$ . Otherwise, we would have that $\tau\circ\tau\Rightarrow i\mapsto j\mapsto\text{ (not }i\text{)}$ , a contradiction from the assumption that $\tau\circ\tau$ is the identity permutation.

We have two cases of movements for any element $i$ to consider: $i$ to $i$ or $i$ to $\text{not }i$ . The first case is obvious in terms of the permutation; it is merely $i\mapsto i$ . In the second case, due to the condition we have established above, we must have $i\mapsto \text{ not }i$ and $\text{not }i\mapsto i$ . So these are the only two possible movements inside the permutation. Denote the first movement $\rightarrow_1$ and the second $\rightarrow_2$ . We split into casework based on the number of $\rightarrow_2$ s in $\tau$ .

$0 \rightarrow_2$ s: Thus every element maps to itself. There is exactly $1$ way for this to happen, so there is $1$ permutation in this case.

$1 \rightarrow_2$ : There are $\binom{8}{2}$ ways to choose which elements map to each other. All of the other elements map to themselves, with again $1$ way. Thus there are $\binom{8}{2}=28$ permutations in this case.

$2 \rightarrow_2$ s: There are $\binom{8}{4}$ ways to choose which elements will be in the group of being mapped to each other. Then there are $3$ ways to map these elements to each other (just consider which element the first in this group is mapped to - there are $3$ ways of choosing this), and again $1$ way for the elements that map to themselves. Thus there are $3\binom{8}{4}=210$ permutations in this case.

$3 \rightarrow_2$ s: There are $\binom{8}{6}$ ways to choose which elements will be in the group of being mapped to each other. In this group, we can map them in $5\cdot3$ ways (using similar reasoning as in the above case), and of course $1$ way to map the remaining elements. So in this case there are $5\cdot3\binom{8}{6}=420$ permutations in this case.

$4 \rightarrow_2$ s: All of the elements will be in the group of being mapped to each other. There are $7\cdot5\cdot3$ ways to map these. Thus there are $7\cdot5\cdot3=105$ permutations in this case.

Summing over all the cases, we obtain $1+28+210+420+105=\boxed{764}$ total permutations.

Suppose that group permutation $S_8$ ,

$\tau o \tau (x)=I$ , If x identitiy element in $S_8$ and order of x are 2 in $S_8$

Identity of $S_8$ is $(1)(2)(3)(4)(5)(6)(7)(8)$

Now, we will counting $x \in S_8$ have order $2$

$x$ have order $2$ if $LCM$ for long of cycle is $2$ , there is $4$ case for that:

Case I

permutation formed $(a)(b)(c)(d)(e)(f)(gh)$ where $1 \leq a,b,c,d,e,f,g,h \leq 8$ There is $\displaystyle C(8,6) \times \frac{C(2,2)}{1!}=28$ way

case 2

permutation formed $(a)(b)(c)(d)(ef)(gh)$ where $1 \leq a,b,c,d,e,f,g,h \leq 8$ There is $\displaystyle C(8,4) \times \frac{C(4,2) \times C(2,2)}{2!}=210$ way

case 3

permutation formed $(a)(b)(cd)(ef)(gh)$ where $1 \leq a,b,c,d,e,f,g,h \leq 8$ There is $\displaystyle C(8,2) \times \frac{C(6,2) \times C(4,2) \times C(2,2)}{3!}=420$ way

case 4

permutation formed $(ab)(cd)(ef)(gh)$ where $1 \leq a,b,c,d,e,f,g,h \leq 8$ There is $\displaystyle C(8,0) \times \frac{C(8,2) \times C(6,2) \times C(4,2) \times C(2,2) }{4!}=105$ way

So, total permutation are $1+28+210+420+105=\fbox{764}$

To go about this problem, it would be useful to have an idea as to how repeated permutations work. As an example, let's look at the permutation $\tau_1=1\rightarrow3, 2\rightarrow6, 3\rightarrow1, 4\rightarrow2, 5\rightarrow5, 6\rightarrow4$ . It keeps certain values separated; it is easy to see that as $\tau_1$ gets repeated, $1$ will never map to $6$ , $5$ will always map to itself, and so on. In fact, $\tau_1$ has three 'loops' that it repeats: $(1,3), (2,6,4),$ and $(5)$ . As such, it is useful to think of any permutation $\tau$ as a collection of loops that numbers go through as $\tau$ iterates. It happens that these loops are just disjoint subsets of the set $\tau$ permutes. (This is fairly simple to prove: if $u$ were an element of two loops, then $\tau (u)$ would not be unique, and $\tau$ wouldn't be a function.)

If $(\tau\circ\tau) (x)=x$ , then the largest of these loops is of at most size $2$ , and therefore, the problem is equivalent to finding the number of partitions with loops of size $2$ or smaller, or, equivalently, partitioning our set $S={1,2,3,4,5,6,7,8}$ into blocks of size $2$ or $1$ .

Now that we have our problem in terms of structures on $S$ , we can apply the theory of Generating Functions. If the function $f(x)=$ number of partitions of a set of size x into subsets of size $2$ or less (what a mouthful!) and $F(t)$ is its exponential generating function, then by the Composition Principle, we have $F(t)=(G \circ H)(x)=e^{x+\frac{x^2}{2}}$ , where $G(t)=e^x$ , the trivial generating function, and $H(t)=x+\frac{x^2}{2}$ , the 'of size $1$ or $2$ ' generating function. Expanding at $t=0$ , $F(t)=e^{x+\frac{x^2}{2}}=1+x+...+764\frac{x^8}{8!}+...$ , and our answer is $\boxed{764}$ .

Sorry about the use of Generating Functions if you don't understand them; they're a kind of deeper topic in counting problems that I don't have the space or expertise to write about here, but if you're interested in finding out more, here are some resources (these are off-site, FYI):

Math DB

UC Berkeley

This problem has been a good opportunity to study a bit of theory behind permutations.

Let it be $m$ the least integer such that $\tau^m=\epsilon$ , where $\tau$ is a permutation of the set $S=\{1,2,...,8\}$ and $\epsilon$ is the identity permutation. We call $m$ the order of $\tau$ , also indicated as $m=\text{order}(\tau)$ .

In our particular case, we are looking for all the permutation of $S$ such that their order $m=2$ :

$\displaystyle \tau^2=\tau \circ \tau=\epsilon$ .

The Order Theorem for Permutations states that, given a permutation $\tau$ written as a product of $k$ disjoint cycles $^1$

$\displaystyle \tau=t_1 \circ t_2 \circ \cdots \circ t_k$

and being $m_i=\text{order}(t_i)$ for $i \in [1,k]$ , the order of $\tau$ is

$\displaystyle m=\text{order}(\tau)=\text{lcm}(m_1,...,m_k)$

where $\text{lmc}(\cdot)$ is the least common multiple .

Since, in our case, $m=2$ , we have to find all the permutation of $S$ that can be written as the product of 2-cycles $^2$ , since it can be proved that $\text{order}(\sigma)=2$ only if $\sigma$ is a 2-cycle .

Hence, the number $N$ of permutation composed of only 2-cycles (plus the identity permutation itself) is

$\displaystyle N=1+\binom{8}{2}+\frac{1}{2!}\binom{8}{2}\binom{6}{2}+\frac{1}{3!}\binom{8}{2}\binom{6}{2}\binom{4}{2}+\frac{1}{4!}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}=\sum_{k=0}^{4} \frac{8!}{2!^k (2(4-k)!)} \cdot \frac{1}{k!}=\boxed{764}$

---

$^1$ : you can find the definition of cycle and some of its properties here .

$^2$ : a k-cycle is a cycle of length $k$ .

The problem of asking for the number of permutations $\tau$ on $n$ elements such that $\tau$ $\circ$ $\tau$ is the identity permutation is equivalent to asking the following question: what is the number of involutions in $S_n$ , the symmetric group on n letters? It can be proved that the number of involutions in $S_n$ is given by:

$\sum_{k=0}^{\left\lfloor \frac{n}{2} \right\rfloor}$ $\frac{n!}{2^k k!(n - k)!}$

In this particular case, we are looking for the number of involutions in $S_8$ , the symmetric group on 8 letters. From our previous formula, we have that the number of involutions in $S_8$ is:

$\sum_{k=0}^{\left\lfloor \frac{8}{2} \right\rfloor}$ $\frac{8!}{2^k k!(8 - k)!}$ = 764.

Break it down into cases depending on how many elements are fixed .

f = No. of fixed elements ( f is always even )

n(f) = no. of requisite permutations with f elements fixed .

• f= 8 --> n(f)= 1
• f=6 --> n(f)= 8C2 = 28
• f=4 --> n(f) = (8C4 x 4C2)/2 = 210
• f=2 --> n(f)= (8C2 x 6C2 x 4C2 ) /6 = 420
• f=0 -- >n(f)= (8C2 x 6C2 x 4C2 )/24 = 105

So the no. of reqd. permutations = n(8) + n(6) + n(4) + n(2) + n(0) = 1 + 28 + 210 + 420 + 105 = 764

There are five cases to consider.

Case 1: No cards are exchanged. There is exactly one such permutation.

Case 2: One pair of cards is interchanged. There are $\binom{8}{2}=28$ such permutations.

Case 3: Two pairs of cards are interchanged. There are $\frac{\binom{8}{2} \cdot \binom{6}{2}}{2!} = 210$ such permutations.

Case 4: Three pairs of cards are interchanged. There are $\frac{\binom{8}{2} \cdot \binom{6}{2} \cdot \binom{4}{2}}{3!} = 420$ such permutations.

Case 5: All pairs of cards are interchanged. There are $\frac{\binom{8}{2} \cdot \binom{6}{2} \cdot \binom{4}{2} \cdot \binom{2}{2}}{4!} = 105$ such permutations.

Summing these gives $\boxed{764}$