Is it possible to compress the given random permutation of any integer using N*(lg(N) -1) bits? For example if N= 512, then it could be represented using 512 * 9 = 4608 bits and its optimal representation can be represented using 4096 bits total.
I have been given only these two information and now I need to figure out whether we can represent the random permutation of 512 using less than 4096 bits or not. Please help me to get any idea on that. Thanks.
I took this question to mean a random permutation of $N$ "things".
A random permutation of the set $\{1,2,\ldots,N\}$ is a member of $S_N$, the symmetric group of $N$ elements. It is well known that there are $N!$ permutations of this set. Stirling's approximation gives $$ N!\sim \sqrt{2\pi N} (N/e)^N $$ or the upper bound $$ \log_2 N!\sim \frac{1}{2}\log_2(2 \pi)+N (\log_2(N)-\log_2(e))\leq 1.326 + N(\log_2 N-1.442)\leq N(\log_2 N-1) $$ on evaluating the relevant constants.