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.

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

share|improve this question
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. –  user21436 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 –  user21436 Jan 13 '12 at 12:59
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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, –  Amitesh Datta Jan 13 '12 at 13:02
    
@Amitesh: I sure do! Thanks very much. –  Brian M. Scott Jan 13 '12 at 13:06
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.