We were given the following question in class:

Let A = {1, 2, 3, 4, 5} and B = {a, b, c, d, e, f}. How many functions 
from A to B are there:

(a) which are a surjection? 
(b) which are an injection 
(c) which are a bijection, 
(d) which have f(1) = a, 
(e) for which ∃x ∈ A, f(x) = b, 
(f) for which 1 and 5 have the same image, 
(g) for which two elements of A have the image c, and three elements have the image e.

I was just wondering if someone could give me a little advice with how I'm working through these, and some tips on how to go through the question.

  • For (a) I treated it like a Stars and Bars question, where the size was 6 (size of B) and the amount of gaps was 5 (size of A) and you could have ones where certain ones in A didn't do anything, so the formula would be $\binom{5 + 6 - 1}{5 - 1}$. Is that right?
  • For (b) I was confused with whether or not injection means ALL of the ones in the domain must match to unique ones in the codomain, or if for instance, one matching to one in the codomain counts as a separate one, such as f(1) = b, and f(1) = a count as two separate functions. How would I tackle this one?
  • c) I figured 0, because $|B| > |A|$
    • d) I figured 1 was a mandatory option now, so that left us with 4 other numbers to match with (to 6 different letters). Considering that something else could still equal a, just 1 couldn't, I considered it another Stars and Bars question and said $\binom{4 + 6 - 1}{4 - 1}$
  • e) I know this means that b will always have a value in the domain linking to it, but I'm not sure how to tackle it.
  • f) and g) I'm not sure how to tackle either.

For the ones I think I did well at solving, the numbers seem really low for my understanding of injective, surjective and bijective functions.

Could anyone offer some insight/help into how I'd go about solving these? Many thanks, just looking for some help.

  • $\begingroup$ For $a$, think of it like this: suppose you have $5$ balls and $6$ buckets. Is there any way you can arrange the balls so all of the buckets have at least one ball? In fact, your reasoning on $c$ eliminates the possibility for $a$.... $\endgroup$ – Clayton Jan 28 '13 at 6:29

(1) There are no surjections: if you have 5 lids for 6 pots, you cannot cover all pots.

(2) Injections: Those map each element of the domain (the numbers) to a different element of the range (the letters). You can map 1 to 6 different letters; after you picked one, you can map 2 to 5 different letters without overlapping with where you map 1; 3 to 4 different letters, etc. So the number is $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2$.

(3) Bijections: a bijection is injective and surjective. By (1), there are no bijections.

(4) $f(1) =a$: You can map $2 -5$ to any of the 6 letters. There are 6 letters, so there are $6^4$ such maps.

(5) $f(1) = f(5)$: You can map $2-4$ to any of the 6 letters, as well as 1 - but then it is also determined where you map 5. So there are again $6^4$ such maps.

(6) You map 2 out of 5 to c, and 3 out of 5 to e. You are free to pick which 2 first. The formula to pick 2 out of 5 is $\binom{5}{2} = 10$. Once you have determined which 2 to map to c, it follows which to map to e (the remaining numbers). So these are all such maps (if you wonder what would happen if you instead determined which 3 out of 5 to map to e, which would imply which 2 to map to c, note that $\binom{5}{2} = \binom{5}{3}$).

  • $\begingroup$ I think your (a) is wrong. With surjections, multiple ones from the domain can map to the codomain, so with your example you could cover all pots if a lid could cover multiple pots. $\endgroup$ – Doug Smith Jan 28 '13 at 14:44
  • $\begingroup$ @Doug Smith: It's definitely right. In plain English, a subjection is also called "onto", which implies every element in the range (codomain) is covered (which can't be dove bête). Formally, for each y in the range, you need to find an x in the domain st f(x) = y. And you're left with one pot y st you can't f find a lid x for it. $\endgroup$ – gnometorule Jan 28 '13 at 15:06
  • $\begingroup$ Dove bête = done here (typo). You're thinking of that in a surjection, multiple x can map to the same y. That's true. But we don't even have enough x hit every y - which is the actual definition; that several x might map to the same y in a surjection is merely a sideffect. $\endgroup$ – gnometorule Jan 28 '13 at 15:10

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.