Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
ayatollah potassium

Posts: 477
Registered: 12/6/04
Re: Homework question: permutations
Posted: Oct 20, 2001 1:32 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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.







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.