# 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

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 ;)

-

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

-