Let PI be a permutation of the integers 0,1,2,3...2^(n-1), such that
PI(m) gives the permuted value of m, 0 <= m < 2^n. Put another way,
PI maps the set of n-bit integers into itself and no two integers map
into the same integer. DES (Data Encryption Standard, for those who
don't know a really popular way of encrypting data in a block-cipher
fashion) is such a permutation for 64 bit integers. We say that PI
has a fixed point at m if PI (m) = m. That is, if PI is an encryption
mapping, then a fixed point comes points to a message that encrypts to
itself. We are interested in the probability that PI has no fixed
points. Show the somewhat unexpected result that over 60% of mappings
will have at least one fixed point.

Think of N people sitting in N chairs. Now we have them all get up and randomly select them as we refill the seats in order. What is the probability that nobody gets their original seat back?

1st person:
Prob that seat is not occupied yet = 1
Prob of missing original seat = (N-1)/N

2nd person:
Prob that seat is not occupied yet = (N-1)/N
Prob of missing original seat = (N-2)/(N-1)

nth person:
Prob that seat is not occupied yet = (N-n)/N
Prob of missing original seat = (N-n)/(N-n+1)

To get the probability that nobody through the nth person has yet been seated in their original seat we require that the 1st person was not and the 2nd and ...
The probability that the nth person was not seated in his original seat is the probability that it was unoccupied and he was not seated in it or that it was already occupied:
(N-n)/N + (n-1)/N

So to get the probability that all persons were seated in a different seat from their original:
Product for n=1 to N of [ (N-n)/N + (n-1)/N ]
= Product for n=1 to N of [ (N-1)/N ]
= ( (N-1)/N )^N

Subtract this from 1 to get the probability that at least one person was seated in their original seat:
1 - ( (N-1)/N )^N

You basically have to add the probablity that m will not map to m, for all m in the range 2^n.

So it's something like (1/(2^n - 1) ) ^ (2^n) ?