Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.*

share|improve this question
    
If this is homework, please add the "homework" tag. –  Gerry Myerson Dec 4 '12 at 12:07
    
I didnt quite understand the question –  chndn Dec 4 '12 at 12:12
    
Can someone help –  chndn Dec 4 '12 at 12:13
    
You didn't understand my question? My question is: is this homework? –  Gerry Myerson Dec 4 '12 at 12:17
add comment

3 Answers 3

up vote 2 down vote accepted

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?

share|improve this answer
add comment

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.

share|improve this answer
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. –  Gerry Myerson Dec 4 '12 at 12:18
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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