4
$\begingroup$

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

  • 0
    @Math, looks good to me.2017-10-05

2 Answers 2

4

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).

  • 0
    Comes out to 826, but I think we've both spent enough time on this :-)2012-02-22
0

$ f(1) \in \{2,3,4,5,6,7\} $ $ f(2) \in \{1,3,4,5,6,7\} $ $ f(3) \in \{1,2,4,5,6,7\} $ $ f(4) \in \{1,2,3,5,6,7\} $

The total possible functions is: $ 6^4 = 1296 $