7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ One way is using inclusion exclusion. $\endgroup$ – Nate Eldredge Apr 8 '14 at 0:40
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaj Hansen Apr 8 '14 at 1:19
  • $\begingroup$ 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! $\endgroup$ – ruplop Apr 8 '14 at 1:54
  • $\begingroup$ @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$. $\endgroup$ – alejopelaez Apr 8 '14 at 1:58
  • $\begingroup$ Yes. I'm confused because you said "And now the total number of non-surjective functions is 35−96+3=150". $\endgroup$ – ruplop Apr 8 '14 at 2:00
  • $\begingroup$ @ruplop Oh, sorry about that, it was a typo $\endgroup$ – alejopelaez Apr 8 '14 at 2:02
0
$\begingroup$

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 :

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

Let's start with the single element:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.