# Finding the number of onto maps from $A = \{1,2,3,4,5\}$ to $B = \{a,b,c\}$

I'm trying to catch up in my discrete math class right now and I came across a practice question:

Use inclusion-exclusion to find the number of onto maps from $A = \{1,2,3,4,5\}$ to $B = \{a,b,c\}$.

I understand that the steps are as follows:

1. $A_1$ = maps from A to B such that f(i) =/= a for i = 1,...,5

$A_2$ = maps from A to B such that f(i) =/= b for i = 1,...,5

$A_3$ = maps from A to B such that f(i) =/= c for i = 1,...,5

2. Find the number of non-onto maps $\to |A_1 \cup A_2 \cup A_3|$;

3. Use the result to find the number of onto maps.

How can I calculate $|A_1 \cup A_2 \cup A_3|$ using inclusion-exclusion? I've used it to calculate other unions of sets but I'm not sure how to apply it in this situation... And what do I do with the result (number of non-onto maps) to get the number of onto maps?

EDIT: The way to calculate the number of onto maps written in my notes is as follows: $|A_1 \cup A_2 \cup A_3| = C(3,1) * 2^5 - C(3,2) * 1^5 + C(3,3) * 0^5$

If someone could explain to me how this is derived, that would be incredibly helpful.

Thanks for any help ahead of time.

• In your question, what is $A_i$? – user122283 Mar 13 '14 at 0:45
• @SanathDevalapurkar See edit of #1 – user134788 Mar 13 '14 at 0:47
• What do you mean by $f(i) \neq a,b,c$ respectively for $i=1,2,..5$? $f(1)\neq a$, $f(2)\neq b,f(3)\neq c$ - what about $f(4),f(5)$? – user122283 Mar 13 '14 at 0:57
• @SanathDevalapurkar I've added a couple things. I'm not sure what it means! That's what I have written in my notes, I was hoping someone could explain it to me... – user134788 Mar 13 '14 at 1:12

The number of onto maps is the total number of maps, minus those that "miss something" i.e. are a member of $A_1 \cup A_2 \cup A_3$.

Inclusion-exclusion says you can calculate the size of the union by calculating sizes of intersections.

If you have an intersection of $n$ sets, you're not mapping to $n$ elements. Then you're considering functions from a set with 5 elements to one with $3-n$ elements.

Hopefully this helps!

• This clarifies it a good amount actually. However I'm still not sure how $|A_1 \cup A_2 \cup A_3| = C(3,1) * 2^5 - C(3,2) * 1^5 + C(3,3) * 0^5$ is derived. Also...how do I get from the result (# non-onto maps) to the # of onto maps? – user134788 Mar 13 '14 at 1:31
• Why is the number chosen going up instead of down? and why is the multiplier decreasing? – user134788 Mar 13 '14 at 1:32
• The choose terms $\binom{n}{k}$ are the number of times an intersection of size $k$ appears. The $(3-k)^5$ are the number of functions. To get the number of onto maps, subtract $|A_1 \cup A_2 \cup A_3|$ from the total number of maps, $3^5$. – Chris Jones Mar 13 '14 at 1:38