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   

  Probability of Matching Envelopes and Letters   

- Doctor Anthony, The Math Forum   
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- The Math Forum at NCTM. All rights reserved.