3
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Inclusion-exclusion? $\endgroup$ Jan 4, 2020 at 5:40
  • $\begingroup$ The same problem was asked here and solved in a different way. $\endgroup$ Jan 29 at 8:49

3 Answers 3

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Can u kindly explain how can we introduce 0 in set A and still have the total no. of cases unaltered? $\endgroup$ Jan 8, 2020 at 7:57
  • $\begingroup$ Oo i got it...thanks a lot! Such an interesting approach to a mind-boggling problem(atleast for me)! $\endgroup$ Jan 8, 2020 at 14:03
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Unfortunately, the answer given was 256. $\endgroup$ Jan 4, 2020 at 11:47
  • $\begingroup$ You are sorting out cases for exclusively 0(not being mapped to) or 0(being mapped to) but that does not have any impact on the inclusion or exclusion of "1".That's probably where we are missing out some cases. $\endgroup$ Jan 4, 2020 at 12:20
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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