Calculating the number of ways a surjective function can be defined.

Question

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.

Answer 1

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 $$

Answer 2

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$

Answer 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.