# Number of surjective functions from A to B

Am I on the right track? I am not sure about my reasoning...

Number of surjective functions from $$A$$ to $$B$$

$$A = \{1,2,3,4\} ; B = \{a,b,c\}$$

We must count the surjective functions, meaning the functions for which for all $$b \in B$$, $$\exists~a \in A$$ such that $$f(a) = b$$, $$f$$ being one of those functions. In order for a function $$f:A\rightarrow B$$ to be a surjective function, all 3 elements of $$B$$ must be mapped.

We need to count how many ways we can map those 3 elements. We will subtract the number of functions from $$A$$ to $$B$$ which only maps 1 or 2 elements of $$B$$ to the number of functions from $$A$$ to $$B$$ (computed in 4.c : 81).

Only 1 element of $$B$$ is mapped

The first $$a \in A$$ has three choices of $$b \in B$$. The others will then only have one. Total functions from $$A$$ to $$B$$ mapping to only one element of $$B$$ : 3.

Exactly 2 elements of $$B$$ are mapped

Similarly, there are $$2^4$$ functions from $$A$$ to $$B$$ mapping to 2 or less $$b \in B$$. However, these functions include the ones that map to only 1 element of $$B$$. So there are $$2^4-3 = 13$$ functions respecting the property we are looking for.

In the end, there are $$(3^4) - 13 - 3 = 65$$ surjective functions from $$A$$ to $$B$$.

• For reference, this answer contains a general method for counting the number of surjective functions between two finite sets. – Ayman Hourieh Sep 21 '13 at 21:10
• The 2 elements ignores that there are 3 different ways you could choose 2 elements from B so in fact there are 39 such functions instead of 13, I believe. – JB King Sep 21 '13 at 23:24

$$\left\lbrace{4\atop 3}\right\rbrace=6$$ is the number of ways to partition $$A$$ into three nonempty unlabeled subsets. For each partition, there is an associated $$3!$$ number of surjections, (We associate each element of the partition with an element from $$B$$). Thus, the total number of surjections is $$3! \times \left\lbrace{4\atop 3}\right\rbrace= 36.$$

• Why do you count the ways to map the other three elements? The way I see it is we place the first three elements with $3! {4 \choose 3}$. Then we add the fourth in the empty space. So I would not multiply by $3!$. – Justin D. Sep 21 '13 at 22:01
• You can't "place" the first three with the $3! {4\choose 3}$-- I am confused by this... I do not understand what you mean.. – Rustyn Sep 21 '13 at 22:06
• The way I see it (I know it's wrong) is that you start with your 3 elements and map them. You have 24 possibilities. Then you add the fourth element. It can be on a, b or c for each possibilities : $24 \cdot 3 = 72$. – Justin D. Sep 21 '13 at 22:12
• I'll think about it! – Justin D. Sep 21 '13 at 22:29
• @JustinD. The answer is correct now. – Rustyn Sep 21 '13 at 22:49

More generally, the number S(a,b) of surjective functions from a set A={1,...,a} into a set B={1,...,b} can be expressed as a sum :

$S(a,b) = \sum_{i=1}^b (-1)^{b-i} {b \choose i} i^a$

where ${b \choose i} = \frac{b!}{i! (b-i)!}$ is the number of different ways to choose i elements in a set of b elements.

To see this, first notice that $i^a$ counts the number of functions from a set of size $a$ into a set of size $i$. Therefore, our result should be close to $b^a$ (which is the last term in our sum). If we want to keep only surjective functions, we have to remove functions that only go into a subset of size $b-1$ in $B$. There are ${b \choose {b-1}}$ such subsets, and for each of them there are $(b-1)^a$ functions. If we just keep $b^a - {b \choose {b-1}} (b-1)^a$ as our result, there are some functions that we removed more than once, namely all functions that go into a subset of size $< b-1$. Therefore, we have to add them back, etc. This leads to the result claimed: $b^a - {b \choose {b-1}} (b-1)^a + {b \choose {b-2}} (b-2)^a - ...$

• Here I just say that the above general formula for $S(a, b)$ is easily obtained by applying the inclusion–exclusion principle en.wikipedia.org/wiki/Inclusion–exclusion_principle to the subsets $A_i$ of $B^A$ consist of those maps don't have $i$ in their images. – Lao-tzu Jul 27 '19 at 9:11

This is an old question, but I recently came across the same problem and solved it in a different way which I find a bit easier to comprehend.

Say you have a $k$ letter alphabet, and want to find the number of possible words with $n_1$ repetitions of the first letter, $n_2$ of the second, etc. The equation for the number of possible words is, as demonstrated in this paper:

$$P(n:n_1,n_2,...,n_k)=\frac{n!}{n_1!\times n_2! \times\cdots\times n_k!}$$

Now, think of the elements of $B$ as our alphabet of 3 letters, one of which is repeated in its mapping on to our 4 elements of $A$. Since the repeated letter could be any of $a$, $b$, or $c$, we take the $P(4:1,1,2)$ three times. Then the number of surjections is

$$3\times P(4:1,1,2)=36$$

I came out with the same solution as the accepted answer, but I may still be erroneous somewhere in my reasoning. Please let me know if you see a mistake ;)

Let a(n,m) be the number of surjections of En = {1,2,...,n} to Em = {0,1,...,m}. Choose an element L of Em. This can be done in m ways. There are two possibilities. (1) L has 1 original in En (say K). The other (n - 1) elements of En are mapped onto the (m - 1) elements of Em (other than L). Number of ways mxa(n-1,m-1). (2) L has besides K other originals in En. The other (n-1) elements of En are in that case mapped onto the m elements of Em. Here is the number of ways mxa(n-1,m). Conclusion: we have a recurrence relation a(n,m) = m[a(n-1,m-1)+a(n-1,m)]. a(n,n) = n!, a(n,1) =1 for n>=1 and a(n,m)= 0 for m>n. One verifies that a(4,3)=36.