Onto Functions

Probability Level 3

Let $E = \{1, 2, 3, 4\}$ and $F = \{1, 2\}.$ Then what is the number of onto functions from $E$ to $F?$

The answer is 14.

3 solutions

Rajdeep Das
Aug 28, 2016

1 in F can be the image of 4 choices in E. Similarly 2 in F can be the image of 4 choices in E. So by the rule of product there are 16 functions. But as the question asks for onto functions we have to subtract 2 functions from 16 (one where every element in E corresponds to 1 in F and second where every element in E corresponds to 2 in F). So number of onto functions are 16-2 = 14

Even though your answer is right, the solution is incorrect. It just happened that $2^4=4^2$. One can quickly see the flaw in your solution by letting the first set have 3 elements instead of 4.

Ben Lou - 3 years, 3 months ago

Also, it just happened that it is 4C1 + 4C2 + 4C3 where xCy is binomial(x, y). Because it is a function, every x in X is mapped onto Y. Therefore if e.g. (1) is mapped onto Y=1 then (2, 3, 4) have to be mapped onto Y=2, or if (2, 4) is mapped onto 1 then (1, 3) is mapped onto 2. That's why we use combinations for only one of them (the other y takes the rest). I didn't get it right first :(.

Paweł Piela - 2 years, 2 months ago

This is the correct solution, some moderator should make it one.

Mr. Krabs - 1 week, 1 day ago

I am confused>>>

ISAIAH LAMBERT-GUTIERREZ - 1 year, 9 months ago

is there some why to see the actual answer published?

Linda Matton - 1 year, 9 months ago

I didn't get the right answer in first 3 try so cannot post a official solution. However, after some thought, I think I found it. If we have f(x) that is a surjective function so: f(1) = Y1 and either f(2), f(3), f(4) = Y2 => this is a combination of function that could map 1 out of 4 input to Y1 which is 4C1

or f(1), f(2) = Y1 and either f(3), f(4) = Y2 => this is a combination of function that could map 2 out of 4 input to Y1 which is 4C2

or f(1), f(2), f(3) = Y1 and f(4) = Y2 => this is a combination of function that could map 2 out of 4 input to Y1 which is 4C3

To complete the series, we need to mention the 4C4 function which map all 4 input to Y1 and hence is not a surjective function.

So we could rephase the problem into: how many ways we could find a function that map either 1, 2, or 3 input into Y1 (and of course that function has to map remaining input to Y2) Answer: 4C1 + 4C2 + 4C3 = 6 + 4 + 4 = 14

Let's try to apply this to a set of 3 input 3C1 + 3C2 = 6 + 3 = 9

Thái An Lê - 1 year, 3 months ago

Isn't a function not defined if an input maps to multiple outputs?

Harshmallow Macaroni - 11 months ago

Joshua Lehman
Sep 21, 2019

Rather than attempt to count the surjective functions, let us subtract the non-surjective functions from the total number of functions. The total number of functions is equal to $2^4$ . This is because for each element of E, it can either map to 1 or 2 (which are the elements of F) thus there are $2\times2\times2\times2$ total functions that map the elements of E to the elements of F. Recall the definition of a surjective function, in doing so one notices that the only functions that won't be surjective are the ones that map all of E to either 1 OR 2. Thus there are 2 functions that are not surjective. Thus our answer becomes $16-2 = 14$ . For completeness, one should note that there are no injective functions from E to F, since $|E|>|F|$ , if this doesn't make sense I recommend reviewing the definition of an injective function and the "Pigeon-hole principle".

Another way to get the total number of functions is by checking how many ways there are to map to 1 in F from E (4 ways) and how many ways there are to map to 2 in F from E (4 ways).

4x4 = 16

Preet Rajdeo - 1 year, 2 months ago

Wrong answer i stands that question is wrost if anyone can makes me understand this question whatsapp me on 8178993845 or can be call me here.

Hitesh Verma - 9 months, 2 weeks ago

Gediminas Sadzius
Feb 19, 2021

This is equivalent to putting n distinct objects into m distinct bins, which can be calculated using Stirling number of the second kind times the permutation of m , where n =4 and m =2, or look up the method at Distribution into Non-empty Bins :

Stirling[ n , m ] *m != 14

Onto Functions

The answer is 14.

3 solutions

0 pending reports