Find all such mappings where $A=\{1,2,3,4\}$, $B=\{1,2,3,4,5,6\}$ and $f:A \to B$ is an injective mapping such that $f(i) \neq i ~\forall i=1,2,3,4$.

675 Views Asked by At

Fund all such mappings where $A=\{1,2,3,4\}$, $B=\{1,2,3,4,5,6\}$ and $f:A \to B$ is an injective mapping such that $f(i) \neq i ~\forall i=1,2,3,4$.

I'm thinking about using the principle of inclusion and exclusion but I'm somewhat not sure how to do that. I think I'm getting lots of cases. Basically, I'm considering all possible values $i$ (for $1\leq i \leq 4$) can map to and that's basically $5$ for each $i$ since $f(i)\neq i$. After that, we will use PIE to rule out the cases when the condition $f(1)\neq f(2)\neq f(3)\neq f(4)$ isn't satisfied. But I think that's a bit of a big thing. Please continue from here; I'm not exactly getting to the destination.

Also, if some nice bijection exists, it would be quite appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $E$ be the set of injective mappings, and let $E_i$ be the set of injective mappings where $f(i)=i$. Then, letting $AB$ denote $A\cap B$, $$ \text{#}\{f:\forall i\;f(i)\neq i\}=|E|-\sum_i|E_i|+\sum_{i<j}|E_iE_j|-\sum_{i<j<k}|E_iE_jE_k|+|E_1E_2E_3E_4| $$ Now, $$ \begin{aligned} |E|&=6\cdot 5\cdot 4\cdot 3, \\ |E_i|&=5\cdot 4\cdot 3,&\\ |E_iE_j|&=4\cdot 3,& \end{aligned} $$ etc.