# Number of One to One functions such that $f(i)\neq i$

Given the sets $A=\{1,\dots,4\}$ and $B=\{1,\dots,7\}$ how many one to one functions are there from $A$ to $B$ such that $f(i)\neq i$ ?

I used inclusion exclusion to first find the number of one to one functions:

$S_1 = f(a)=f(b) , S_2 = f(a)=f(b)=f(c) , S_3 = f(a)=f(b)=f(c)=f(d)$

$$7^4 - \binom{4}{2}\cdot 7^3 + \binom{4}{3}\cdot 7^2 - \binom{4}{4}\cdot 7^1=532$$

I then repeated using a similar approach for eliminating cases of $f(a)=a$, etc...

$$532 - \binom{4}{1}\cdot6^3 + \binom{4}{2}\cdot5^2 - \binom{4}{3}\cdot4^1 + \binom{4}{4}\cdot 3^0$$

Are my solutions correct?

EDIT

I see that the number of one to one functions is $7\cdot6\cdot5\cdot4=840$ and that makes sense. But I still can't seem to get it to work using inclusion exclusion.

$U$ would be the group of all possible functions, $7^4=2401$.

$S_1 =$ where $f(a)=f(b)$

$S_2 =$ where $f(a)=f(b)$ and $f(c)=f(d)$

$S_3 =$ where $f(a)=f(b)=f(c)$

$S_4 =$ where $f(a)=f(b)=f(c)=f(d)$

-
I think you chose the hard way to do the first part - the number of one to one functions is just $7\times6\times5\times4$ (which isn't $532$). – Gerry Myerson Feb 16 '12 at 10:38
I see what you're saying, but I don't understand why I can't seem to get the inclusion exclusion approach to work. – Robert S. Barnes Feb 16 '12 at 11:00
Check this out en.wikipedia.org/wiki/Derangement – Jernej Feb 16 '12 at 11:40

## 1 Answer

Here's how it goes, using inclusion-exclusion to count the one-one functions.

Notice that you have 6 conditions: $f(a)=f(b)$, $f(a)=f(c)$, $f(a)=f(d)$, $f(b)=f(c)$, $f(b)=f(d)$, and $f(c)=f(d)$.

So the first three terms in the inclusion-exclusion are $$7^4-6\times7^3+{6\choose2}7^2$$ Now the next term is trickier. If the three conditions that hold are $f(a)=f(b)$, $f(a)=f(c)$, and $f(b)=f(c)$, that contributes $7^2$, but if the three conditions are $f(a)=f(b)$, $f(b)=f(c)$, and $f(c)=f(d)$, then the contribution is only $7$. So so far we have $$7^4-6\times7^3+{6\choose2}7^2-4\times7^2-16\times7$$ Now if 4, 5, or 6 conditions hold, the contribution is 7, so you get $$7^4-6\times7^3+{6\choose2}7^2-4\times7^2-16\times7+{6\choose4}7-6\times7+7$$ With any luck, I haven't missed anything, and that comes out to $840$ (and you can see that I wasn't kidding when I said this was the hard way).

-
Comes out to 826, but I think we've both spent enough time on this :-) – Robert S. Barnes Feb 22 '12 at 19:02