# Cardinality of Set of Surjections/Examples/m=n+1

## Example of Cardinality of Set of Surjections

Let $S$ and $T$ be finite sets.

Let $\card S = m, \card T = n$.

Let $C$ be the number of surjections from $S$ to $T$.

Let $m = n + 1$.

Then:

$C = \dfrac {n \paren {n + 1}!} 2$

## Proof

$C = n! \ds {n + 1 \brace n}$

where $\ds {n + 1 \brace n}$ denotes a Stirling number of the second kind.

 $\ds C$ $=$ $\ds n! {n + 1 \brace n}$ Cardinality of Set of Surjections $\ds$ $=$ $\ds n! \dbinom {n + 1} n$ Stirling Number of the Second Kind of $n$ with $n - 1$ $\ds$ $=$ $\ds n! \dfrac {n \paren {n + 1} } 2$ Binomial Coefficient with Two $\ds$ $=$ $\ds \dfrac {n \paren {n + 1}! } 2$ Definition of Factorial

$\blacksquare$