Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Homework question: permutations
Replies: 12   Last Post: Oct 21, 2001 8:04 PM

 Messages: [ Previous | Next ]
 ayatollah potassium Posts: 477 Registered: 12/6/04
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.

Date Subject Author
10/13/01 Fred Galvin
10/13/01 Entropix
10/14/01 Fred Galvin
10/14/01 Entropix
10/15/01 Robin Chapman
10/15/01 Robin Chapman
10/16/01 Fred Galvin
10/18/01 Jim Ferry
10/18/01 Fred Galvin
10/19/01 Jim Ferry
10/19/01 Fred Galvin
10/21/01 ayatollah potassium
10/20/01 ayatollah potassium