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.

pretty interesting..

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

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%