Answer to Question #339125 in Discrete Mathematics for Yagami

Question

How many bijections (bijective functions) are there from A to A with the

property that no element of A is mapped to itself? (A is a set with 5 elements)

Answer 1

There are $5!$ different bijections from $A$ to $A$. Namely the first element can be mapped into $5$ different elements. The second one into $4$ elements and so on. Using a multiplication principle of combinatorics, we receive: $5!=120$ different bijections. We point out that a bijection that has $4$ elements mapped to itself and $5$ elements mapped to itself is the same. There is $1$ bijection of this type. Consider bijections that have $3$ elements mapped to itself, but not $4$ and $5$ . There are $C_5^3=\frac{5!}{3!2!}=10$ maps of this type. Consider maps that have only $2$ elements mapped to itself. There are $2C_5^2=2\frac{5!}{3!2!}=20$ maps of this type. Consider maps that have $1$ element mapped to itself. As an example, we fix $1$. There are $4!$ different bijections that have $1$ mapped to itself. They contain $1$ bijection that has $4$ and $5$ elements mapped to itself, $C_4^2=\frac{4!}{2!2!}=6$ bijections that have $3$ elements mapped to itself and $2C_4^1=8$ bijections that have $2$ elements mapped to itself. We receive: $4!-1-6-8=9$ bijections. Thus, there are $9$ bijections that have only $1$ mapped to itself. We receive:$45$ bijections that have only $1$ element mapped to itself. Thus, we get: $1+10+20+45=76$ different bijections that have at least $1$ element mapped to itself. We receive: $120-76=44$ bijections that have no elements mapped to itself.

Answer: there are $44$ bijections that have no elements mapped to itself.