Numbers Choosing Each Other

There are $4^5$ functions $f \,:\,\{1,2,3,4,5\} \to \{1,2,3,4,5\}$ such that $f(n) \neq n$ for $1 \le n \le 5$ . Let us count the number of functions $f$ such that $f(n) \neq n$ for all $n$ and such that no "swap pair" of numbers exists.

Let $f$ be a "no swap pair" function of this type. Then $f(1) \neq 1$ , so we can find $a \neq 1$ such that $f(1) = a$ . Then $f(a) \neq 1$ and $f(a) \neq a$ , so we can find a third number $b$ such that $f(a) = b$ .

If $f(b) = 1$ , let $c,d$ be numbers such that $\{1,a,b,c,d\} = \{1,2,3,4,5\}$ . Then any choice of $f(c), f(d)$ is possible except $f(c) = d$ and $f(d) = c$ . There are $4$ choices for $a$ , $3$ choices for $b$ , and then $4^2-1 =15$ choices for the values of $f(c),f(d)$ . Thus there are $4\times3\times15 = 180$ "no swap pair" functions of this type.

If $f(b) \neq 1$ , then $f(b) \neq a$ and $f(b) \neq b$ as well, so we can find a find a new number $c$ such that $f(b) = c$ . Now find the number $d$ such that $\{1,a,b,c,d\} = \{1,2,3,4,5\}$ . Note that $f(c)$ cannot be either $b$ or $c$ .

If $f(c) = 1$ or $f(c) = a$ , then any choice of $f(d)$ will work. There are $4$ choices for $a$ , $3$ choices for $b$ , $2$ choices for $c$ , and $4$ choices for $d$ . Thus there are $2 \times 4 \times 3 \times 2 \times 4 = 192$ "no swap pair" functions of this type.

If $f(c)$ is neither $1$ nor $a$ , then $d = f(c)$ is such that $\{1,a,b,c,d\} = \{1,2,3,4,5\}$ . In this case $f(d)$ can be any one of $1,a,b$ . Thus there are $3 \times 4 \times 3 \times 2 \times 1 = 72$ "no swap pair" functions of this type.

This means that there are $180 + 192 + 72 = 444$ "no swap pair" functions, and hence there are $4^5 - 444 = 580$ functions that contain a "swap pair". Thus we deduce that $P \; = \; \tfrac{580}{4^5} \; = \; \tfrac{145}{256}$ and hence the answer is $145 + 206 = \boxed{401}$ .