Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Homework question: permutations
Posted:
Oct 20, 2001 1:32 PM


Fred Galvin wrote:
> The question wasn't about even and odd permutations, it was about > permutations of odd *order*.
Nevertheless, there is a more mysterious even/odd principle lurking around here.
Number of permutations of odd order = number of permutations with all cycles of odd length = number of permutations with all cycles of even length (if n is even).
So your list of equiprobables can be rephrased thus.
"If n is an even number, the following probabilities are equal: (a1) the probability that a random element of S_n has all cycles odd; (a2) the probability that a random element of S_n has all cycles even; (b) the probability that a random element of S_{n+1} has all cycles odd; (c) the probability of getting equal numbers of heads and tails in n independent tosses of a fair coin."
a2 = c is true because an even cycle decomposes into a pair of subsets (elements at even and odd positions) plus two matchings (forward and backward) between them. Direct arguments for a1=a2=b would be nice to see, it seems similar to the (hard) problem of proving that 4^n is a convolution of central binomial coefficients.



