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
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
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search