1
$\begingroup$

How many permutations $\tau$ on 8 elements are there such that $\tau\circ\tau$ is the identity permutation?

*Details and assumptions

You may think of a permutation on 8 elements as a way to shuffle a deck of 8 cards. The identity permutation would correspond to the shuffle where we do nothing (hence it stays the same = identity). If $\tau$ corresponds to only exchanging the top 2 cards, then $\tau\circ\tau$ would return the deck to it's unchanged state.*

3 Answers 3

2

Suppose that $\tau$ leaves $k$ fixed; then $\tau\circ\tau$ will also leave it fixed, so $\tau\circ\tau$ will take $k$ to $k$. If $\tau$ takes $k$ to some other number $\ell$, then $\tau\circ\tau$ will take $k$ to $\tau(\ell)$. In order for $\tau\circ\tau$ to be the identity, $\tau(\ell)$ must be $k$. In other words, if $\tau$ sends $k$ to $\ell$, it must also send $\ell$ to $k$. In terms of shuffling cards, if $\tau$ leaves the $k$-th card in the $k$-th position, so will $\tau\circ\tau$, and if $\tau$ interchanges the cards in the $k$-th and $\ell$-th positions, $\tau\circ\tau$ will leave both the $k$-th and the $\ell$-th cards in their original positions. These are the only possibilities if $\tau\circ\tau$ is to be the shuffle that leaves the deck unchanged.

Thus, you want to count the permutations (shuffles) that consist entirely of two-card interchanges (like $k\mapsto\ell$ and $\ell\mapsto k$) and cards left in place (like $k\mapsto k$). You can count these systematically.

  • Count those with no interchanges: there is just one of these, the permutation that takes $k$ to $k$ for $k=1,\dots,8$.
  • Count those with exactly one interchange: there are $\binom82$ ways to choose the pair to be swapped, so there are $\binom82$ such permutations.
  • Count those with exactly two interchanges: there are $\binom82$ ways to choose one pair to interchange, and then there are $\binom62$ ways to choose a second pair to interchange. However, each pair of pairs can be chosen in either order (e.g., first the pair $\{1,3\}$ and then the pair $\{7,8\}$, or first the pair $\{7,8\}$ and then the pair $\{1,3\}$), so $\binom82\binom62$ counts each pair of pairs twice; the actual number of permutations interchanging two pairs is just $\frac12\binom82\binom62$.

Can you finish it off with correct calculations for the other two cases?

1

A permutation $\tau$ such that $\tau \circ \tau=\mbox{id}$ is called an involution. You're looking for the involutions of $S_8$. Now consider these:

  • Every permutation can be written as a product of disjoint cycles.
  • A cycle of length $k$ has order $k$.
  • The order of a product of disjoint cycles is the lcm of the order of the cycles.

They should get you started.

  • 4
    If it's necessary to explain a permutation as shuffling cards, I doubt the phrase "disjoint cycle" is going to mean anything to OP.2012-12-04
1

You can format a permutation $\tau$ as matrix T with 8 rows and 8 columns that contains in each row and each column only one entry which differs from 0 and equals 1. From the condition $\tau\circ\tau$ we have T * T = E, where E is identity matrix. This means that T is symmetric matrix. Now you should calculate the number of such matrices.