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

Question

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.

Answer 1

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!