Cardinality of Set of Surjections/Examples/m=n+2
Jump to navigation
Jump to search
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}$
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 + 2 \brace n}\) | Cardinality of Set of Surjections | |||||||||||
\(\ds \) | \(=\) | \(\ds n! \paren {\binom {n + 3} 4 + 2 \binom {n + 2} 4}\) | Stirling Number of the Second Kind of $n$ with $n - 2$ | |||||||||||
\(\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$
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $4$: Mappings: Exercise $4 \ \text{(iii)}$