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


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
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




Re: Homework question: permutations
Posted:
Oct 15, 2001 4:17 AM


"Fred Galvin" <galvin@math.ukans.edu> wrote in message news://Pine.LNX.4.21.0110131534290.10973100000@titania.math.ukans.edu...
> 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?
For (a) and (b) let o_n denote the number of odd order permutations in S_n. Then it's easy to prove o_{n+1} = o_n + n (n1) o_{n1}. Note that o_n counts the permutations of odd order in S_{n+1} fixing n+1 while (n1)o_{n1} counts those taking n+1 to j (1 <= j <=n) [delete n+1 and j from a permutation, and note that these could have occurred in n1 places]. Now it's easy to induct that o_{n+1} = n o_n for even n and o_{n+1} = (n1)o_n for odd n.
Dunno about (c) :(
Robin Chapman www.maths.ex.ac.uk/~rjc/rjc.html
 Posted from oregano.ulcc.wwwcache.ja.net [194.82.103.36] via Mailgate.ORG Server  http://www.Mailgate.ORG



