Number of onto functions from 2 sets

[scorpius1782]

Homework Statement

I have 2 sets, one with 5 elements (A) and the other two(B).
How many onto functions can be made from A to B?

Homework Equations

The Attempt at a Solution

My first thought is that it should be something like $\frac{5!}{2!}=60$. I don't know if this is correct or not, I began counting them up manually but quickly found that it was not really feasible to do without mistakes. I've never been very good at these combinations problems and I can't say I ever really understand them.

Thanks for the help.

 

[Darksonn]

All the functions must have 5 inputs, and each input can give 2 things.
So for each input there is 2 options.
I would say that is 2^5 = 32 options.

 

[SammyS]

All the functions must have 5 inputs, and each input can give 2 things.
So for each input there is 2 options.
I would say that is 2^5 = 32 options.

That may count some functions twice.


I would suggest looking at an easier case - - or easier cases.

How about if set A contains i element and set B contains 2 elements?

How about if set A contains 2 elements and set B contains 2 elements?

How about if set A contains 3 elements and set B contains 2 elements?

etc.

 

[pasmith]

Homework Statement

I have 2 sets, one with 5 elements (A) and the other two(B).
How many onto functions can be made from A to B?

For convenience, let $B = \{0,1\}$. Every function $f : A \to B$ can be written as
$$f : a \mapsto \begin{cases} 0, & a \in C, \\ 1, & a \in A \setminus C, \end{cases}$$
for some $C \subseteq A$, and distinct functions result from distinct choices of $C$. Thus there are exactly as many functions from $A$ to $B$ as there are subsets of $A$.

You are asked for onto functions, which means that there must be at least one $a \in A$ such that $f(a) = 0$ and at least one $b \in A$ such that $f(b) = 1$. Thus $C$ can be any subset of $A$ except the empty set and $A$ itself.

 

[pasmith]

All the functions must have 5 inputs, and each input can give 2 things.
So for each input there is 2 options.
I would say that is 2^5 = 32 options.

That may count some functions twice.

Actually it counts each function exactly once.

Two functions $f: A \to B$ and $g: A \to B$ are equal if and only if $f(a) = g(a)$ for all $a \in A$. Thus if you make a different choice for the image of some $a \in A$ you have a different function. Since there are $\#B$ choices for each $f(a)$ and the choices are independent, there are (assuming both sets are finite) $(\#B)^{(\#A)}$ distinct functions, although not all of them are onto, which is what the question asks for.

 

[scorpius1782]

I think I understand. I don't recall ever being in class that discussed how these combinations are found mathematically, they always have assumed that a)I've already been taught or b)It is so straight forward that teaching it is a waste of time. Neither is true for me.

Does anyone know of a website that explains this in great detail (except wikipedia because they lack multiple examples and is hard to read)?

 

[scorpius1782]

That may count some functions twice.


I would suggest looking at an easier case - - or easier cases.

How about if set A contains i element and set B contains 2 elements?

How about if set A contains 2 elements and set B contains 2 elements?

How about if set A contains 3 elements and set B contains 2 elements?

etc.

I don't get anywhere doing this really. For 2 there are two possibilities, for 3 there are 6 (I think) but for 4 there are too many for me to do by hand really. I'm at 11 now but there could be more that I'm not seeing. It gets to be too many options to keep track of for me.

 

[scorpius1782]

I found this link on math.stackexchange but the solution looks about 10x harder than would be expected for the freshman class I'm in...

I also ended up getting 14 functions that were onto for 4->2.

It seems that for my problem, though, I could do it like

$2^5-2(2-1)^5$ which would be 30. The possible combinations minus the combinations that don't include the elements from B. This also works with all the other cases.

Have I got the idea now?

 

[PeroK]

Here's another way to look at it: imagine that B is the set {0, 1}. Then every function from A to B is effectively a 5-digit binary number. So, there are 32 = 2^5.

But, if the function is onto, then you cannot have 00000 or 11111. So, that leaves 30.

So, you can now extend your counting of functions to larger sets.

 

[scorpius1782]

Here's another way to look at it: imagine that B is the set {0, 1}. Then every function from A to B is effectively a 5-digit binary number. So, there are 32 = 2^5.

But, if the function is onto, then you cannot have 00000 or 11111. So, that leaves 30.

So, you can now extend your counting of functions to larger sets.

This helped me so much to understand right here. Thank you so much.

 

[anjla]

if the 2nd set hs 2 elements, the no of onto fns would be 2^n - 2 where n is the no of elements in the 1st set...so 4 ur qn it would be 32-2=30...this works only in cases where d 2nd set has 2 elements though...