Probability and PermutationsDate: 09/12/1999 at 12:51:08 From: Sunda Subject: Probability and permutation Here's the question: A permutation denoted by f is a 1-1 mapping of the first n positive integers onto themselves. What is the probability that a permutation has the property that f(i) = i for at least one i, 1 <= i <= n? Construct an appropriate probability space and within that space obtain an answer to the question. Check your answer for a few small values of n for which you are able to list all permutations. My attempt: Let f(x) = {x := positive integers 1, 2, 3, ..., n-1, n} Mapping: x f(x) 1 nP1 2 nP2 : : n-1 nP(n-1) Let n = 10: x f(x) 1 10!/(10-1)! = 10 Let n=2: x f(x) 1 2!/1! = 2 2 2!/0! = 2 In this case, I have one x = 2 whose f(x) is also 2. I cannot proceed beyond this. Can you help? Date: 09/12/1999 at 15:09:41 From: Doctor Anthony Subject: Re: Probability and permutation This is the same as the classic problem of putting letters at random into envelopes and finding the probability that every letter is in the wrong envelope. See the following archive entries for an outline of the general method of calculating the probability. Letters and Envelopes and the Inclusion-Exclusion Principle http://mathforum.org/dr.math/problems/jarrad03.27.99.html Probability of Matching Envelopes and Letters http://mathforum.org/dr.math/problems/dey3.3.98.html - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/