5
$\begingroup$

I'm having trouble on this question:

Let $f(n,r)$ be the number of surjections from a set $A$ having $n$ elements to a set $B$ having $r$ elements. Show that $f(n,r)=r\Big(f(n-1,r-1)+f(n-1,r)\Big)\;.$

Here is my idea about how to start:

Partition each set, $A$ and $B$, such that the top partition consists of $n-1$ or $r-1$ elements (for $A$ and $B$ respectively) and the bottom partitions consists of one element each.

Then there are $f(n-1,r-1)$ surjections from the top partition of $A$ onto the top partition of $B$.

There are $f(n-1,r)$ surjections from the top partition of $A$ to all of $B$.

Now consider the whole of $A$ (i.e. $(n-1)+1$ elements).

The total number of surjections is:

((total number of surjections from top partition of $A$ onto all of $B$) + (extra surjections due to extra element of $A$)) permuted to account for all combinations

But how do you calculate the extra surjections due to the extra element of $A$ and the correct number of permutations?

Thank you.

  • 1
    There is a natural correspondence between surjective functions and partitions, so this is the same thing as counting *ordered* partitions of a given set $A$ into $r$ non-empty subsets. The number of such partitions was used in this paper: Gupta, H.N. (1985): *A theorem in combinatorics and Wilson's theorem.* Amer. Math. Monthly, 92, 575–576. [jstor link](http://www.jstor.org/stable/2323167). If we omit the word ordered, we get [Stirling numbers of the second kind](http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind) and, indeed, for these numbers we can get very similar formula.2012-04-30

2 Answers 2

2

Assuming that the formula is supposed to be $f(n,r)=r\Big(f(n-1,r-1)+f(n-1,r)\Big)\;,$ something similar to your basic idea can be made to work.

Fix $a\in A$, let $A'=A\setminus\{a\}$, and suppose that $\varphi:A\to B$ is a surjection. There are two possibilities: either $\varphi[A']=B$, so that $\varphi\upharpoonright A'$ is a surjection of $A'$ onto $B$, or there is exactly one $b\in B\setminus\varphi[B]$, so that $\varphi\upharpoonright A'$ is a surjection of $A'$ onto $B\setminus\{b\}$. In the first case there is no restriction on $\varphi(a)$: it can be any member of $B$. In the second case, however, we must have $\varphi(a)=b$, since $\varphi$ is a surjection. Let $\Phi_1$ be the set of surjections of $A$ onto $B$ covered by the first case and $\Phi_2$ the set covered by the second case.

There are $f(n-1,r)$ surjections of $A'$ onto $B$. If $\psi$ is one of these surjections, there are $r$ surjections $\varphi\in\Phi_1$ such that $\varphi\upharpoonright A'=\psi$, one for each of the $r$ possible values of $\varphi(a)$. Thus, $|\Phi_1|=rf(n-1,r)$.

For each $b\in B$ there are $f(n-1,r-1)$ surjections of $A'$ onto $B\setminus\{b\}$, and there are $r$ possible choices of $b$, so $|\Phi_2|=rf(n-1,r-1)$.

The sets $\Phi_1$ and $\Phi_2$ are disjoint and exhaust the set of surjections of $A$ onto $B$, so $f(n,r)=r\Big(f(n-1,r-1)+f(n-1,r)\Big)\;.$

4

I'm going to go out on a limb and suppose the intended identity is $ f(n,r) = r(f(n-1,r-1) + f(n-1,r)). $

For convenience, let $A = \{1, \dots, n\}$ and $B = \{1, \dots, r\}$.

Let's call our sujection $g$. First, let's decide where to map the element 1 under $g$. There are clearly $r$ places it could go.

Now, one of two things could happen. Either $g(1) \neq g(j)$ for all $j \neq 1$ or not.

In the former case, there are $f(n-1,r-1)$ possible mappings, since we are required to find a surjection from $A - \{1\}$ onto $B - \{g(1)\}$.

In the latter case, there are $f(n-1,r)$ possible mappings, since we are required to find a surjection from $A - \{1\}$ onto $B$ (remember, in this case we are specifically requiring that something else gets mapped to $g(1)$).

Putting all this together gives the desired identity.