# How many one-to-one functions there $\phi$ from $\{1,2,3,4,5,\}$ to $\{1,2,3,4,5\}$ such that $\phi(i)\neq i$ for $i=1,2,3,4,5$ [duplicate]

How many functions one-to-one $\phi$ from $\{1,2,3,4,5,\}$ to $\{1,2,3,4,5\}$ such that $\phi(i)\neq i$ for $i=1,2,3,4,5$

my attempt:

the number of one-to-one functions $\phi$ from $\{1,2,3,4,5,\}$ to $\{1,2,3,4,5\}$ is 5!=120

and given condition is $\phi(i)\neq i$ for $i=1,2,3,4,5$ so these are 5

so number of one-to-one functions are $\phi$ from $\{1,2,3,4,5,\}$ to $\{1,2,3,4,5\}$ such that $\phi(i)\neq i$ for $i=1,2,3,4,5$

=120-5=55 is i am right

## marked as duplicate by M. Winter, N. F. Taussig, gebruiker, user370967, kingW3Jul 10 '17 at 12:32

• You have $5!$ injective functions, which is $120$. Now count how many injections you get when you allow one fixed point, two fixed points etc and subtract from $120$. Inclusion-exclusion principle. – Alvin Lepik Jul 10 '17 at 8:27
You could interpret your functions as the result of shuffling a 5-card deck. The number of outcomes where one card only is in the original position is given by (https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle, “Counting Derangements” section) $$W(n) = \sum_{p=1}^{n} \frac{n!}{p!}$$ So, $W(5) = 76$, and the number you look for is given by $120 – 76 = 44$.
Actually you are asking for the number of derangements of 5 intergers.i.e., $D_5$.
The general formula for derangements of n intergers is $$D_n=n!\left(1-1/1!+1/2!-1/3!+\cdots+ (-1)^n/n!\right)$$.
• Fun fact! $D_n$ can be computed by finding $n! / e$, and rounding to the nearest integer. – Theo Bendit Jul 10 '17 at 8:36