Let be a permutation of the integers 0 1 2 2n 1 such that

Let be a permutation of the integers 0, 1, 2, ... (2n - 1) such that (m) gives the permuted value of m, 0m<2n. Put another way, maps the set of n-bit integers into itself and no two integers map into the same integer. DES is such a permutation for 64-bit integers. We say that has a fixed point at m if (m) = m. That is, if is an encryption mapping, then a fixed point corresponds to a message that encrypts to itself. We are interested in the probability that has no fixed points.

Show the somewhat unexpected result that over 60% of mappings will have at least one fixed      point.

Solution

Answer

In order to understand this, try to think this problem as n people sitting in n chairs. Now make them get up and randomly select from among them as we refill the seats in order. Now, to make it similar to the given question we\'ll check the probability that nobody gets their original seat back.
  
So,
For 1st person:
Probability that seat is not occupied yet = 1
Probability of missing original seat = (N-1)/N

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

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

In order 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 so on.
The probability that the nth person was not seated in his original seat is equal to the probability that his seat was unoccupied plus he was not seated in his original seat or that his original seat was already occupied,
So,
(N-n)/N + (n-1)/N

Therefore, 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

In order to get the probability that at least one person was seated in their original seat subtract the above from 1:
= 1 - ( (N-1)/N )^N

Therefore, for N = 2^m

m 1 - ( (N-1)/N )^N

8 63.28%
12 63.22%
16 63.21%
20 63.21%
24 63.21%
28 63.21%

As you can see the mapping with the value gives that over 60% will have at least one person seating in their original seat, in our case at least one fixed point.