0
$\begingroup$

This question already has an answer here:

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – Alvin Lepik Jul 10 '17 at 8:27
  • 1
    $\begingroup$ Have a look at derangements $\endgroup$ – drhab Jul 10 '17 at 8:31
1
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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) $$.
Substitute the value for n as 5 you will get the answer.

$\endgroup$
  • 1
    $\begingroup$ Fun fact! $D_n$ can be computed by finding $n! / e$, and rounding to the nearest integer. $\endgroup$ – Theo Bendit Jul 10 '17 at 8:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.