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

  • 1
    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$).2012-02-16
  • 0
    I see what you're saying, but I don't understand why I can't seem to get the inclusion exclusion approach to work.2012-02-16
  • 3
    Check this out http://en.wikipedia.org/wiki/Derangement2012-02-16
  • 0
    @GerryMyerson What will be final answer for this question. Is it $840-C(4,1)(6 \cdot 5 \cdot 4)+C(4,2) (5 \cdot 4)-C(4,3) 4+C(4,4)$ ?2017-10-05
  • 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 $$