1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In your question, what is $A_i$? $\endgroup$ – user122283 Mar 13 '14 at 0:45
  • $\begingroup$ @SanathDevalapurkar See edit of #1 $\endgroup$ – user134788 Mar 13 '14 at 0:47
  • $\begingroup$ 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)$? $\endgroup$ – user122283 Mar 13 '14 at 0:57
  • $\begingroup$ @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... $\endgroup$ – user134788 Mar 13 '14 at 1:12
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user134788 Mar 13 '14 at 1:31
  • $\begingroup$ Why is the number chosen going up instead of down? and why is the multiplier decreasing? $\endgroup$ – user134788 Mar 13 '14 at 1:32
  • $\begingroup$ 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$. $\endgroup$ – Chris Jones Mar 13 '14 at 1:38

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.