Cardinality of Set of Surjections/Examples/m=n+2

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 + 2$.

Then:

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

$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 + 2 \brace n}$

$\ds $

$=$

$\ds n! \paren {\binom {n + 3} 4 + 2 \binom {n + 2} 4}$

$\ds $

$=$

$\ds n! \dfrac {n \paren {3 n + 1} \paren {n + 1} \paren {n + 2} } {24}$

Definition of Binomial Coefficient and some algebra

$\ds $

$=$

$\ds \dfrac {n \paren {3 n + 1} \paren {n + 2}!} {24}$

Definition of Factorial

$\blacksquare$