Explanation of the recursion for number of surjections

I have a question about the recursion of the number of surjections from $\{1,\ldots,n\}$ to $\{1,\ldots,k\}$: $$\mathrm{Sur}(n,k) = k \cdot \mathrm{Sur}(n-1,k-1) + k \cdot \mathrm{Sur}(n-1,k).$$ My explanation of this is: We look at the element $k$ from $\{1,\ldots,k\}$. $k$ can be hit either by $1$ element from $\{1,\ldots,n\}$, or by $2$ or more.

In the first case, we remove that $k$ and that element from $\{1,\ldots,n\}$, and we're left with $n-1$ elements in the domain, and $k-1$ elements in the range. It also has to be a surjection, so we can pick them in $\mathrm{Sur}(n-1,k-1)$ ways.

In the second case, we remove that element from the domain, and we're left with $n-1$ elements in domain, and $k$ elements in the range. So we can pick the number of surjections in $\mathrm{Sur}(n-1,k)$ ways.

But, why is that factor $k$ there in both cases?

Solution 1:

You didn't account for the $n$ different choices of elements mapped to $k$. In your first case, that leads to a factor of $n$. The second case is more complicated because you also have a choice which of the elements mapped to $k$ to remove. To avoid these complications, you can derive the recurrence as in polkjh's answer instead.

Solution 2:

Let $f(n)$ be the image of element $n$.

If $n$ is the only element with $f(n)$ as it's image, then we can remove $n$ and $f(n)$ and look at $S(n-1,k-1)$. But there are $k$ ways to pick $f(n)$. So this accounts for $k.S(n-1,k-1)$ ways.

If $n$ is not the only element with $f(n)$ as it's image, then we can just remove $n$ and look at $S(n-1,k)$. And $f(n)$ can again be chosen in $k$ different ways. This gives another $k.S(n-1,k)$ surjections.

In your argument, in the case when $k$ has exactly one element hitting it, you can choose that element in $n$ ways. So that accounts for $n.S(n-1,k-1)$ surjections. But the other case gets more complicated. If there are $r$ elements pointing to $k$, there are $\binom{n}{r}$ ways to pick those $r$ elements. Then we can remove those $r$ elements and $k$ and look at $S(n-r,k-1)$. We cannot just remove one of these elements and look at surjections from $n-1$ to $k$ as these are not any general surjections (in these surjections, you need $r-1$ elements pointing to $k$).

This gives

$$ S(n,k) = \sum _{r=1}^{n} \binom{n}{r} S(n-r,k-1) $$

Solution 3:

This is just my quick impression, but it seems to be all about permutations.

First, we have our sets $A = \{a_1,...,a_n\}$, $B = \{b_1,...,b_k\}$ and some $f:A \rightarrow B$.

Try to think about what happens to $a_n$ in all the possible surjections.

My further thoughts are below in the spoiler:

If $a \epsilon A$, $b \epsilon B$ and we let $f(a)=b$, then there are two possibilities for our surjections: some other $a' \epsilon A$ also maps to $b$ or not. In the case where $f(a)$ uniquely maps to $b$, there are clearly $Sur(n-1,k-1)$ ways to do this.

Then

In the other case, $f(a')=b=f(a)$ for some arbitrary $a' \epsilon A$. That is, our surjection is $f(a)=b$ along with some surjection $g: A \backslash a \rightarrow B$. So the number of ways of doing this should be $Sur(n-1,k)$.

So

The number of surjections where $f(a)=b$ should come to $Sur(n-1,k-1) + Sur(n-1,k)$. But clearly the above arugment is symmetric across all $b$--of which there are $k$ of them--so multiply by $k$.

Q.E.D.