# Injective Functions $X=\{1,2,3,4\}$ , $Y=\{1,2,3,4,5,6\}$

I have the following question:

I got two groups $X=\{1,2,3,4\}$ , $Y=\{1,2,3,4,5,6\}$

How many injective functions $f: X → Y$ consider next terms: for each $i \in X$ , $f(i) ≠ i$ . The solution has to be via inclusion - exclusion principle.

Can anyone suggest an approach or an answer?

Thanks!

-
It isn't that simple, @tetori. Note the requirement that $f(i)\neq i$ for all $i\in X$. – Cameron Buie Feb 3 '13 at 16:00

You can use this approach. At first you count the total no. of injective functions. This according to me is $$6C4*4!$$ Then you can count the no. of ways in which 1 of the $F(i)=i$ this equals $$4C1\times5C3\times3!$$Then you can count the no. of ways in which 2 of the $F(i)=i$ this equals $$4C2\times4C2\times2!$$Then for 3 i such that $F(i)=i$ this equals $$4C3\times3C1\times1!$$And lastly the case when all $F(i)=i$ this equals $$1$$.So the no. of fns. are $$6C4*4!-4C1\times5C3\times3!+4C2\times4C2\times2!-4C3\times3C1\times1!+1$$ Using inclusion exclusion principle.
Hint: Lets enumerate the numbers. If $f$ is such that injection, then in how many ways we can define $f(1)\in Y$? It is $5$, cause we exclude $f(1)=1$. Do the same way for another number $2\in X$, so we have $4$ and s... so there are $5!$ injective functions with that property.
If $f(1)=2$, then 2 has 5 possibilities! – Stefan Feb 3 '13 at 16:13
@Stefan: But we assume that $f$ is an injectice, so we should care about $x=2$, so it takes 4 positions. – Babak S. Feb 3 '13 at 16:15