There's a math problem in the book Discrete Mathematics with Applications(2nd Edition) by Susanna S. Epp is something like this:
How many onto functions are there from a set with four elements to a set with two elements?
Definition of onto function is:
Let be a function from a set to a set . is onto(or surjective) if, and only if, given any element in
it is possible to find an element in with the property that .
Symbolically:
Now back to the math problem. I did this.
Let the element of the domain be called and the elements of the co-domain be called
Now there ways to select 2 elements of and and associate with set . I added twice because there are two elements in and 1 for each element of
Also there are ways to select 3 elements of and associate with set . Again because there are two elements in and added twice.
So the total number of onto function from a set with four elements to a set with two elements is: . But the answer in the book is .
What am i doing wrong? Is it possible for someone to kindly look into the problem and figure out the error in my thinking?
This is an example of using the inclusion/exclusion principle. I know that it is in Epp's book. Count the function that leave out one of the final set, the two of the final set, then three ETC. So we end up adding and subtracting each of those. I no longer have a copy of her book. But I am positive this idea is in that text.