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

From Cardinality of Set of Surjections:

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

Sources

• 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $4$: Mappings: Exercise $4 \ \text{(iii)}$