Number of onto functions from 2 sets

  • #1
107
0

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.
 

Answers and Replies

  • #2
2
0
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.
 
  • #3
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,422
1,057
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.
 
  • #4
pasmith
Homework Helper
2,157
778

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 [itex]B = \{0,1\}[/itex]. Every function [itex]f : A \to B[/itex] can be written as
[tex]
f : a \mapsto \begin{cases} 0, & a \in C, \\
1, & a \in A \setminus C,
\end{cases}
[/tex]
for some [itex]C \subseteq A[/itex], and distinct functions result from distinct choices of [itex]C[/itex]. Thus there are exactly as many functions from [itex]A[/itex] to [itex]B[/itex] as there are subsets of [itex]A[/itex].

You are asked for onto functions, which means that there must be at least one [itex]a \in A[/itex] such that [itex]f(a) = 0[/itex] and at least one [itex]b \in A[/itex] such that [itex]f(b) = 1[/itex]. Thus [itex]C[/itex] can be any subset of [itex]A[/itex] except the empty set and [itex]A[/itex] itself.
 
Last edited:
  • #5
pasmith
Homework Helper
2,157
778
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 [itex]f: A \to B[/itex] and [itex]g: A \to B[/itex] are equal if and only if [itex]f(a) = g(a)[/itex] for all [itex]a \in A[/itex]. Thus if you make a different choice for the image of some [itex]a \in A[/itex] you have a different function. Since there are [itex]\#B[/itex] choices for each [itex]f(a)[/itex] and the choices are independent, there are (assuming both sets are finite) [itex](\#B)^{(\#A)}[/itex] distinct functions, although not all of them are onto, which is what the question asks for.
 
  • #6
107
0
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)?
 
  • #7
107
0
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.
 
  • #8
107
0
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?
 
  • #9
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
20,137
11,475
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.
 
  • #10
107
0
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.
 
  • #11
1
0
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....
 

Related Threads on Number of onto functions from 2 sets

  • Last Post
Replies
1
Views
3K
Replies
1
Views
3K
Replies
7
Views
10K
  • Last Post
Replies
2
Views
1K
Replies
6
Views
924
Replies
2
Views
393
Replies
2
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
17
Views
707
Top