1
$\begingroup$

Let $A = \{1,2,3,4\}$ and $B = \{a,b,c,d,e\}$. How many functions from $A$ to $B$ are either one-to-one or map the element $1$ to $c$? (you need not simplify your answer)

First. the number of functions which are one-to-one : $5\cdot4\cdot3\cdot2$

Second. the number of functions that map the $1$ to $c$ : $5^3$

answer : $5\cdot4\cdot3\cdot2 + 5^3$

is it right? please help me..

  • 1
    You need to subtract the number of 1-1 functions that map 1 to $c$.2012-01-13
  • 0
    You are double counting, those maps that take 1 to c can be one-one in particular. So, You need to subtract those maps from the count of $5^3$. So, The number of such maps will be $4 \cdot 3 \cdot 2$. This has to be subtracted from your answer.2012-01-13
  • 0
    Are you forgetting to appreciate @Brian's help? If not, why don't choose his answer and there'll be one less post to settle for math.SE2012-01-13

1 Answers 1

4

Your sub-answers are correct, but the final answer is not: you forgot that some functions from $A$ to $B$ are in both categories $-$ they’re one-to-one and take $1$ to $c$. You’ve counted these functions twice in your answer of $5\cdot4\cdot3\cdot2+5^3$. To correct for this, you need to figure out how many functions are simultaneously in both categories and subtract this number from your current answer. How many injections from $A$ to $B$ take $1$ to $c$? If you use the kind of reasoning that you used to get your sub-answers, you should have little difficulty with this.

  • 0
    Dear Brian, I think you mean "How many *injections* from $A$ to $B$ take $1$ to $c$?" instead of "How many *bijections* from $A$ to $B$ take $1$ to $c$?" in the second last line of your answer. Regards,2012-01-13
  • 0
    @Amitesh: I sure do! Thanks very much.2012-01-13