0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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.