Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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.
|
|
|
|
