# Calculating the number of ways a surjective function can be defined. [closed]

The image above contains the questions with their solutions. I'm really not quite sure how they arrived with $36$ in case of answer (e).

I don't understand why the $3$ is multiplied to $16$ and why the additional $3$ is added.

## closed as off-topic by Henrik, Stefan4024, GNUSupporter 8964民主女神 地下教會, José Carlos Santos, NamasteDec 14 '17 at 0:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Henrik, Stefan4024, GNUSupporter 8964民主女神 地下教會, José Carlos Santos, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

Step 1: How many ways can $f$ be defined without restrictions -- that was already answered as $81$.

Step 2: A surjection must map something to each of $b_1, b_2, b_3$. How many of those $81$ possibilities fail to map anything to $b_1$ -- that was already answered as $16$.

Steps 3 and 4: But missing $b_1$ is not the only way to fail: You could fail to map anything to $b_2$ or to $b_3$. Each of those represents $16$ more "bad" (not surjective) maps.

So far we have $81-16-16-16 = 81-3\times 16$ possibilities. But some possibilities have been rejected twice. For example, if you fail to map anything to $b_1$ and also fail to map anything to $b_2$, that would have been rejected twice. So you have to add these back.

Steps 5, 6, and 7: How many ways can the map fail to map anything to $b_1$ and also fail to map anything to $b_2$? that answer was also already given, as $1$.

How many ways can the map fail to map anything to $b_1$ and also fail to map anything to $b_3$? Again, $1$. And how many ways can the map fail to map anything to $b_2$ and also fail to map anything to $b_3$? We have to add those three $1$s back in.

So far we have $81-16-16-16+1+1+1 = 81-3\times 16+3$ possibilities. Now any map that fails to map anything to any of ($b_1$, $b_2$, or $b_3$) has been rejected three times, and added back three times, so its counting is OK. Besides, how many ways can the map fail to map anything to any of the $b_i$ at all? The answer to this is already given as zero.

So the total number of surjections is $$81-3\times 16 + 3\times 1 = 36$$

Surjective means that every element $B$ has at least one element in $A$ that maps onto it.

I think the since there are $3$ elements in $B$ and $4$ elements in $A.$ There is one element in $B$ that has 2 elements in $A$ mapping to it.

$3\cdot {4\choose 2}$ gives the number of ways to accomplish this.

There remain two umapped elements in $A$ and $2$ elements in $B$ that each can map to. And once we map one of those it will determine how the last element in $A$ will be mapped.

$3\cdot {4\choose 2}\cdot 2 = 36$

This is not "inclusion exclusion." But, it might help you think it through.

Inclusion -- Exclusion

There are $81$ mappings. $16$ of which leave nothing mapping to $b_1$ and $16$ not mapping onto $b_2$, and $1$ of which leave nothing mapping to $b_1$ and $b_2$

This one that doesn't map to $b_1$ and $b_2$ is one of the $16$ that doesn't map to $b_1$ and one of the $16$ that doesn't map to $b_2$

$81 - 16 - 16$ has "double subtracted" this map, and we need to add it back.

$81 - 16 - 16 + 1$

When we introduce the maps that don't map to $b_3$ we will have to look at "double subtraction" the maps that don't map to $b_1$ and $b_3$ and don't map to $b_2$ and $b_3.$

$81 - 16\cdot 3 + 3$

Recall that the number of functions between an $m$ element set and an $n$ element set is $n^m$. You can compute the number of surjective functions between 4 elts and 3 elts as follows:

1. The total number of functions from $4\rightarrow 3$ is $3^4 = 81$.
2. Some of these functions leave out one of the elements, and consequently aren't surjective. We should count them and subtract them out.

Those functions act like $4\rightarrow 2$ functions. The number of such functions is equal to the number of $4\rightarrow 2$ functions, times the number of ways of picking two elements to be the new range. Hence the number of such functions is ${3 \choose 2} \cdot 2^4 = 3\times 16$.

3. Just a few of these functions leave out two of the elements, and we've accidentally double counted them. For example, in the previous step, we've counted $f:\{a_1,a_2,a_3)\rightarrow \{b_1,b_2\}$ which sends everything to $b_1$ as a different function from $\{a_1,a_2,a_3\}\rightarrow \{b_1,b_3\}$ which sends everything to $b_1$.

There are three functions $4\rightarrow 3$ which leave out two elements; they're the three constant functions. We counted each one twice in the last step, hence we subtracted out 3 more functions than we needed to. We should add them back in.

The overall count is $81 - 3\times 16 + 3 \times 1$.

Personally, this isn't how I'd count the number of surjective functions. What I would do is for each value in the range $\{b_1, b_2, b_3\}$, pick a unique member in $\{a_1, a_2, a_3, a_4\}$ which will be mapped to that value.

Because we have to pick a different $a$ value for each one, there are 4 possibilities for $b_1$, then 3 possibilities for $b_2$, then 2 possibilities for $b_3$. There is one value $a$ left over which hasn't been assigned to any $b$ value. Because we've already made the function surjective, we can assign it to any of the 3 $b$ values, no problem.

Intuitively, it seems like there are around

$$4\cdot 3\cdot 2\cdot 3$$

surjective functions.

One subtlety is that this double-counts slightly: for each surjective function, two $a$ values will get mapped to the same $b$ value. Our counting algorithm makes it seem like it matters which one we assign first. Because it doesn't matter, we are overcounting by a factor of two (the number of ways of choosing which one of the two we assign first). Hence the real number of surjective functions is:

$$4\cdot 3 \cdot 2 \cdot 3 / 2 = 36$$

Note that $81 - 3\cdot 16 + 3 = 36$ as well.