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 $\displaystyle F$ be a function from a set $\displaystyle X$ to a set $\displaystyle Y$. $\displaystyle F$ is onto(or surjective) if, and only if, given any element $\displaystyle y$ in

$\displaystyle Y$ it is possible to find an element $\displaystyle x$ in $\displaystyle X$ with the property that $\displaystyle y = F(x)$.

Symbolically:

$\displaystyle F:X\to Y\; is\; onto\; \Leftrightarrow \forall y\in Y,\; \exists x\in X\; such\; that\; F(x)\; =\; y.$

Now back to the math problem. I did this.

Let the element of the domain be called $\displaystyle M = \{a,b,c,d\}$ and the elements of the co-domain be called

$\displaystyle N = \{u,v\}$ Now there $\displaystyle \binom{4}{2} + \binom{4}{2} = 6 + 6 = 12$ ways to select 2 elements of $\displaystyle M$ and and associate with set $\displaystyle N$. I added twice because there are two elements in $\displaystyle N$ and 1 for each element of $\displaystyle N$

Also there are $\displaystyle \binom{4}{3}+\binom{4}{3} = 4 + 4 = 8$ ways to select 3 elements of $\displaystyle M$ and associate with set $\displaystyle N$. Again because there are two elements in $\displaystyle N$ and added twice.

So the total number of onto function from a set with four elements to a set with two elements is: $\displaystyle 12 + 8 = 20$. But the answer in the book is $\displaystyle 14$.

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

Quote:

Originally Posted by

**x3bnm** So the total number of onto function from a set with four elements to a set with two elements is: $\displaystyle 12 + 8 = 20$. But the answer in the book is $\displaystyle 14$.

Consider $\displaystyle A=\{1,2,3,4\},\;B=\{a,b\}$ then, any map $\displaystyle f:A\to B$ can be considered as an arrangement , for example $\displaystyle aaaa,\;aaab,\ldots, \;baab,\ldots,bbbb$ . All are onto except $\displaystyle aaaa$ and $\displaystyle bbbb$ . Hence, we have $\displaystyle 2^4-2=14$ onto maps.

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 $\displaystyle N\ge K$ then the number of surjection from a set of $\displaystyle N$ elements to a set of $\displaystyle K$ is:

$\displaystyle {\text{Surj}}(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^j \binom{K}{j}\left( {K - j} \right)^N }. $

So $\displaystyle \text{Surj}(4,2)=14$.

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 $\displaystyle N\ge K$ then the number of surjection from a set of $\displaystyle N$ elements to a set of $\displaystyle K$ is:

$\displaystyle {\text{Surj}}(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^j \binom{K}{j}\left( {K - j} \right)^N }. $

So $\displaystyle \text{Surj}(4,2)=14$.

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.