Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
Took too long writing this out, apparently. :-/ –  b-wilson Jan 17 '13 at 11:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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