# Surjections Combinatorial Proof

Let $S(n,k)$ denote the number of surjective functions from a set of size $n$ to a set of sive $k$, where $n \geq k$.

Prove the following using a combinatorial proof:

$S(n+1,n) = nS(n,n-1) + n(n!)$

Workings:

Proof

LHS counts the number of surjections from a set of size $n+1$ to size $n$ or $S(n+1,n)$

RHS

Suppose you have a set of surjections of size $n$ to size $n-1$. This is $S(n,n-1)$ and you want to count the number of surjections from $n+1$ to $n$.

Now I'm not sure on what to do next any help will be appreciated.

Hint: Fix a set $A$ of size $n+1$, and pick a special element $a$. We will separate the surjections of $A$ onto a set of size $n$, B, into two sets:

• Surjections where $f^{-1}(f(a)) = \{a\}$: $f(a)$ can assume $n$ values, and $f|_{A \setminus \{a\}}$ is simply a surjection between $A \setminus \{a\}$ (which has $n$ elements) and $B \setminus \{f(a)\}$ (which has $n-1$ elements).

• Surjections where $f^{-1}(f(a)) = \{a,a'\}$. Here $f(a)$ can assume $n$ values, and the rest is simply a bijection between $A \setminus \{a\}$ and $B$. How many such bijections exist?

Hope this can get you started.

• There are $n-1$ bijections. – TillermansTea Feb 18 '15 at 16:45
• Are you sure? How many bijections are there between $\{1,2,3\}$ and itself? What about $\{1,2,3,4\}$? – Pedro M. Feb 18 '15 at 16:46
• Wait would it be $n!$ Since there are $6$ bijections for ${1,2,3}$ and $24$ for ${1,2,3,4}$ – TillermansTea Feb 18 '15 at 16:51
• Well, $1$ can be mapped to $n$ values, $2$ can be mapped to $n-1$ values and so on$\ldots$ – Pedro M. Feb 18 '15 at 16:53
• Which is the definition of $n!$. – TillermansTea Feb 18 '15 at 16:58