Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Probability and Permutations


Date: 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/   
    
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/