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$
3
  • 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
    Commented Nov 10, 2014 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
    Commented Nov 10, 2014 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
    Commented Nov 10, 2014 at 22:21

2 Answers 2

Reset to default
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$
7
  • $\begingroup$ Oops. I forgot to mention that the functions must be bijective. I've edited the question. $\endgroup$
    – MathNerd
    Commented Nov 10, 2014 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
    Commented Nov 10, 2014 at 15:10
  • $\begingroup$ @ThomasAndrews inclusion exclusion principle is needed to compile the results. $\endgroup$
    – AlexR
    Commented Nov 10, 2014 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
    Commented Nov 10, 2014 at 15:22
  • 1
    $\begingroup$ True, but your approach doesn't work for bijections, either. $\endgroup$
    – Thomas Andrews
    Commented Nov 10, 2014 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .