Cardinality of Set of Surjections

Theorem

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

Then:

$C = n! \ds {m \brace n}$

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

Proof

Let $T$ be the codomain of a surjection $f$ from $S$ to $T$.

By the Quotient Theorem for Surjections, $f$ induces an equivalence $\RR_f$ on $T$:

$f = r \circ q_{\RR_f}$

where:

$\RR_f$ is the equivalence induced by $f$ on $T$

$r: S / \RR_f \to T$ is a bijection from the quotient set $S / \RR_f$ to $T$

$q_{\RR_f}: S \to S / \RR_f$ is the quotient mapping induced by $\RR_f$.

From the Fundamental Theorem on Equivalence Relations, $\RR_f$ induces a partition on $S$.

From Cardinality of Set of Induced Equivalence Classes of Surjection, $\RR_f$ has $m$ components.

From Number of Set Partitions by Number of Components, there are $\ds {m \brace n}$ different ways of performing such a partitioning.

From Cardinality of Set of Injections, there are $n!$ different bijections from $S / \RR_f \to T$.

The total number of surjections is then the product of these:

$C = n! \ds {m \brace n}$

$\blacksquare$

Examples

Example: $m = n + 1$

Let $m = n + 1$.

Then:

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

Example: $m = n + 2$

Let $m = n + 2$.

Then:

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