Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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$). –  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
2  
Check this out en.wikipedia.org/wiki/Derangement –  Jernej Feb 16 '12 at 11:40
add comment

1 Answer

up vote 3 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.