1
$\begingroup$

I got this problem:

Let $A=\{A_1,A_2,A_3,A_4,A_5\}$ and $B=\{B_1,B_2,B_3,B_4,B_5\}$ be two sets.
How many one to one correspondences (one to one and onto functions) from $A$ to $B$ are there that satisfy the condition:

$\exists i\in\{1,2,3,4,5\}$ such that $ f(A_i)=B_i$

Can you generalize the result when $A$ and $B$ have $n$ elements?

I am stuck on this problem for at least $2\frac{1}{2}$ hours.

Thanks any hint/help.

$\endgroup$
  • 1
    $\begingroup$ How many functions from $A$ to $B$ do not have such an $i$? How many functions total from $A$ to 4B$? $\endgroup$ – Thomas Andrews Nov 10 '14 at 14:44
  • 1
    $\begingroup$ The answer to the original question would have been $5^5-4^5$. This new question, requiring bijections, will have to use inclusion/exclusion. $\endgroup$ – Thomas Andrews Nov 10 '14 at 15:12
  • 2
    $\begingroup$ As the set elements do not matter, are we not just talking about permutations with fixed points? Having cycles of length 1? $\endgroup$ – mvw Nov 10 '14 at 22:21
1
$\begingroup$

Hint

What is the number of bijective functions from $A$ to $B$ where $A$ and $B$ both have $5$ elements? What is is for $A, B$ containing $n$ elements?

Now for the actual problem

How many ways are there to chose the specific $i$ for wich $f(A_i) = B_i$?

Given an $i$ we can see that the number of functions with this particular value is the same as the number of bijections $$g: A\setminus\{A_i\} \to B\setminus \{B_i\}$$ Where $f(A_j) = \cases{B_i & $i=j$ \\ g(A_j) & else}$. Use the first result to obtain this number. Then use the principle of inclusion and exclusion to get the total number of functions with a "fixed point".

$\endgroup$
  • $\begingroup$ Oops. I forgot to mention that the functions must be bijective. I've edited the question. $\endgroup$ – MathNerd Nov 10 '14 at 15:09
  • 1
    $\begingroup$ No,this anser is wrong, because more than $1$ $i$ could exist fixed, and you are counting those twice. $\endgroup$ – Thomas Andrews Nov 10 '14 at 15:10
  • $\begingroup$ @ThomasAndrews inclusion exclusion principle is needed to compile the results. $\endgroup$ – AlexR Nov 10 '14 at 15:20
  • 1
    $\begingroup$ You could do it that way, or you could just write $5^5-4^5$. (For the problem as originally written.) The number of functions without a fixed point is $4^5$. $\endgroup$ – Thomas Andrews Nov 10 '14 at 15:22
  • 1
    $\begingroup$ True, but your approach doesn't work for bijections, either. $\endgroup$ – Thomas Andrews Nov 10 '14 at 16:13
1
$\begingroup$

There are $5!$ bijections in total. Those you don't want to count are exactly the derangements, of which there are $\left[5!/e\right]$ where $[\cdot]$ is the nearest-integer function. So the result is $$ \left[5!(1-e^{-1})\right] $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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