0
$\begingroup$

Let $S(n,k)$ be the number of surjections from an $n$-set to a $k$-set.

Prove use a combinatorial proof that:

$S(n+1,k) = kS(n,k) + kS(n,k-1)$, where $n \geq k$

Workings:

this equation counts the class of distributions of $n+1$ balls labeled, $1, ..., n+1$ among $k$ urns labeled $u_1, ..., u_k$, with no urn left empty. The LHS counts by definition of $S(n+1, k)$.

RHS

The RHS splits this into two situations:

(1) The case when ball 1 is placed in an urn all by itself

(2) The case when ball 1 is placed in a urn with at least one other ball.

Case 1 would be $kS(n,k)$ and Case 2 would be $kS(n,k-1)$

This counts all cases. So the proof is complete.

I'm not sure if this is correct. Any help will be appreciated.

$\endgroup$
0
$\begingroup$

Stirling numbers of second kind is what you are looking for. You can read the answer given by AndrewG here to learn more about them. Your proof is correct.

$\endgroup$
  • $\begingroup$ Oh it is the Stirling Numbers. I was wondering if they were. Thanks for the help. $\endgroup$ – MrTambourineMan Jan 31 '15 at 22:08

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.