1

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

Brian M. Scott
  • 616,228
Q123
  • 251
  • 1
    You need to subtract the number of 1-1 functions that map 1 to $c$. – David Mitra Jan 13 '12 at 12:42
  • 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. –  Jan 13 '12 at 12:45
  • 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.SE –  Jan 13 '12 at 12:59

1 Answers1

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.

Brian M. Scott
  • 616,228