How many permutations (bijections) are there on the set B = {0,1}^(8) of bytes? How can there be permutations if there is no function? I know that B would be the set {00000000, 00000001, ..., 11111111}, and there are 256 elements on this set. I don't know how there can be a bijection on the set, though...I thought that you needed a function in order to have a bijection, and my teacher didn't give us a function. I was thinking that I could use the identity function and say that there would be 256 permutations since there are 256 elements, but I don't know if this would be right... I'm really confused as to how there can be permutations on a set when there is no function.
 A: First of all, it helps to know that a permutation is a bijection from a set to itself. So, the question is asking how many functions are there from $B$ to $B$ that meet the requirements of a bijection.
Try thinking about a smaller space that is easier to picture or write out. For example, suppose we are in $\{0, 1\}^2 = \{00, 01, 10, 11\}$. A bijection is just a mapping between sets, with a few extra rules. Using what you know about bijections, what does such a mapping look like in this case?
The identity function is one example to consider. Here's another:
\begin{align*}
 00 & \mapsto 01 \\
 01 & \mapsto 11 \\
 10 & \mapsto 00 \\
 11 & \mapsto 10 \\
\end{align*}
When coming up with new bijections, notice that there are four ways to pick what $00$ maps to, then three remaining ways to pick what $01$ maps to, and so on. Given this, how many such bijections can there be? Now extend this to the case of $\{0, 1\}^8$, or even $\{0, 1\}^n$. In order to show that the rule holds for any $n$, you can use mathematical induction.
