Error in thought:How many onto functions there from a set of 4 element to 2 elements?

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?

Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

You are over counting by repeating some selections.

If then the number of surjection from a set of elements to a set of is:

So .

Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

Thanks FernandoRevilla and Plato for explanation.

Plato you're right i'm counting some selection multiple times. My mistake. Sorry(Happy). Thanks again.

Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

Quote:

Originally Posted by

**Plato** You are over counting by repeating some selections.

If

then the number of surjection from a set of

elements to a set of

is:

So

.

Sorry for reopening this thread but Plato how did you come up with this formula?

I can't find this formula in my book. Is there a proof somewhere?

I like to know it. My curious mind can't help it.

Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

Quote:

Originally Posted by

**x3bnm** I like to know it. My curious mind can't help it.

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.

Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

Quote:

Originally Posted by

**Plato** 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.

Thanks Plato. It's on page 299-300 of Epp's book for those who are interested.