Solved

# permutation mappings..

Posted on 2004-09-28

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..