Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
This was a question from a test. There's a set $A$ with elements $\{1,2,3,4,5\}$ and another set $B$ with elements $\{0,1,2,3,4,5\}$. Now $f$ is a function from $A$ to $B$ such that $f(1)$ is not equal to $0$ or $1$ and $f(i)$ is not equal to $i$ (for $i=2,3,4,5$). Then how many such one to one functions are possible?
It looks like an application of the derangement formula, but it's getting way too complex when I apply it. Can anyone help me out in this?
Introduce 0 in set A and place it in position which is not occupied by any 5 elements in set A(no of cases still remain same).
If 0 takes 0 , then it is simply $d_5$
If 0 does not take 0 it would have been $d_6$ if 1 could take 0 but u see 1 has equal probability going to 0,2,3,4,5 right. Out of $d_6$ every 4 out of 5 cases should be counted
Answer is simply $d_5$ + $\frac{4d_6}{5}$ = 44 + $\frac{4*265}{5}$ = 44 + 212=256
If no number is mapped to zero, you need a derangement of five items-use the derangement formula. If a number is mapped to zero, we can assume it is $2$ and multiply by $4$. If no number is mapped to $2$, you need a derangement of four items. If a number is mapped to $2$, we can assume it is $3$ and multiply by $4$ (because now it could have been $1$ that is mapped to $2$). Then if no number is mapped to $3$ we need a derangement of three items. If a number is mapped to $3$, assume it is $4$, multiply by $3$, and you need a derangement of two items. The final total is $$!5+4\cdot !4+4\cdot 4 \cdot !3 + 4 \cdot 4 \cdot 3 \cdot !2=44+4\cdot 9+16\cdot 2+48\cdot 1=160$$
Well the problem may be solved by a simple algorithm which always works in every problem of derrangement and is derived from its proof. Set $f(1)=2$ Now you have to assign values to $x=3,4,5$ under constraint of $f(i)$ not equal to $i, 2$ is free to go anywhere as we already assigned $2$ of codomain to $f(1)$. By inclusion exclusion, Total unconditional ways $= \binom54 \times 4!$ Now subtract cases in which one of $3,4,5$ was matched to $3,4,5$ of codomain . But now you subtracted the number of cases in which $2$ of $3,4,5$ was matched to $2$ of $3,4,5$ in codomain twice ,so add it. And so on .... Total cases are $$\binom54\times 4!-\binom31\times \binom43\times 3!+\binom32\times \binom32\times 2!-\binom33\times \binom21\times 1!=64$$ Since $f(1)$ may take $2,3,4,5$ and all those cases are symmetrical . Total ways$=4\times64=256$
