
Homework question: permutations
Posted:
Oct 13, 2001 4:45 PM


S_n is the group of all permutations of {1,2,...,n}.
If n is an even number, the following probabilities are equal: (a) the probability that a random element of S_n has odd order; (b) the probability that a random element of S_{n+1} has odd order; (c) the probability of getting equal numbers of heads and tails in n independent tosses of a fair coin.
This came up in a homework problem in my combinatorics class. It's easy enough to verify the equalities by mindless computation with generating functions, but I think they must have a simple explanation. What is it?

