# How many surjective functions are there from $A=${$1,2,3,4,5$} to $B=${$1,2,3$}?

I want to find how many surjective functions there are from the set $A=${$1,2,3,4,5$} to the set $B=${$1,2,3$}? I think the best option is to count all the functions ($3^5$) and then to subtract the non-surjective functions. However, I'm not sure how can I count these functions.

Thanks

• One way is using inclusion exclusion. – Nate Eldredge Apr 8 '14 at 0:40

I will show you two ways.

First one is with your current approach and using inclusion-exclusion, so you need to count the number of functions that misses $$1$$ element, lets call it $$S_1$$ which is equal to $${ 3 \choose 1 }2^5 = 96$$, and the number of functions that miss $$2$$ elements, call it $$S_3$$, which is $${3 \choose 2}1^5 = 3$$. And now the total number of surjective functions is $$3^5 - 96 + 3 = 150$$.

But you can also do the following, fix a surjective function $$f$$ and consider the sets $$f^{-1}(1), f^{-1}(2), f^{-1}(3)$$. Because $$f$$ is surjective, they partition $$A$$ into $$3$$ disjoint, non empty sets.

Now think the other way around, start with $$A$$ and partition it into $$3$$ disjoint non empty sets, say $$A_1, A_2, A_3$$, you can then form a surjective function by just assigning one of the $$A_i$$ to one of the elements in $$B$$. The number of ways to partition a set of $$n$$ elements into $$k$$ disjoint nonempty sets are the Stirling numbers of the second kind, and the number of ways of of assigning the $$A_i$$ to the elements of $$B$$ is $$k!$$ (where $$k$$ is the size of $$B$$), in your particular case, this gives $$3!S(5,3) = 150$$.

The reason I showed you these two ways, is that you can use them to prove the "explicit" formula for the stirling numbers of the second kind, which is $$k!S(n,k) = \sum_{j=0}^k (-1)^{k-j}{k \choose j} j^n$$ By just double counting, and using a more general inclusion exclusion, and as far as I know, this is one of the most "explicit" formulas you can get.

• This is correct. Stirling numbers of the second kind do indeed yield the desired result. I made an egregious oversight in my answer, so I've since deleted it. – Kaj Hansen Apr 8 '14 at 1:19
• I found that there are 93 non surjective functions and 150 surjective functions. I'm confused because you're telling me that there are 150 non surjective functions. Thanks for your answer! – ruplop Apr 8 '14 at 1:54
• @ruplop I am counting the subjective ones in both approaches. Sorry if it was not very clear, with inclusion exclusion I get the number of non-surjective ones, (whcih is $93$ indeed) but if you notice I am subtracting that from $3^5$. – alejopelaez Apr 8 '14 at 1:58
• Yes. I'm confused because you said "And now the total number of non-surjective functions is 35−96+3=150". – ruplop Apr 8 '14 at 2:00
• @ruplop Oh, sorry about that, it was a typo – alejopelaez Apr 8 '14 at 2:02

Pedestrian approach:

How many surjective functions from:

$A$ ={ $1, 2, 3, 4, 5$} to $B$= {$a, b, c$} ?

1) Let $3$ distinct elements of $A$ be mapped onto $a, b$, or $c$.

There are

$\binom{5}{3} = 10$,

ways to pick $3$ elements from $5$.

There are $3$ ways to map these elements onto $a,b$, or $c$.

Altogether $3×10 = 30$ ways.

Each choice leaves $2$ spots in $B$ empty; $2$ ways of filling the vacant spots with the $2$ remaining elements of $A$

Combining: $2×30 = 60$ ways of generating a surjectice map with $3$ elements mapped onto $1$ element of $B$.

2) $2$ elements of $A$ are mapped onto $1$ element of $B$, another $2$ elements of $A$ are mapped onto another element of $B$, and the remaining element of $A$ is mapped onto the remaining element of $B$.

The mapping looks, for example, like :

$( ||, |, || )$.

$5$ ways to choose an element from $A$, $3$ ways to map it to $a,b$ or $c$. Altogether: $5×3 =15$ ways.

$2$ vacant spots remain to be filled with $2$ elements of $A$ each.

$4$ elements are left in $A$, the number of ways of choosing $2$ of the remaining $4$: $\binom{4}{2} = 6.$

To avoid double counting fix any one empty spot of $B$ (there are $2$).

There are $6$ ways to put $2$ numbers in this spot, the remaining open spot is taken care of with the remaining $2$ numbers of $A$ automatically.

Altogether there are $15×6 = 90$ ways of generating a surjective function that maps $2$ elements of $A$ onto $1$ element of $B$, another $2$ elements of $A$ onto another element of $B$, and the remaining element of $A$ onto the remaining element of $B$.

Combining: There are 60 + 90 = 150 ways.