ThmDex – An index of mathematical definitions, results, and conjectures.
Result R5111 on D15: Set cardinality
Number of injections is proportional to number of subsets of given size
Formulation 0
Let $n, m \in \mathbb{N}$ each be a D996: Natural number such that
(i) \begin{equation} m \leq n \end{equation}
(ii) $\text{Inj}(\{ 1, \ldots, m \} \to \{ 1, \ldots, n \})$ is the D2222: Set of injections from $\{ 1, \ldots, m \}$ to $\{ 1, \ldots, n \}$
Then \begin{equation} |\text{Inj}(\{ 1, \ldots, m \} \to \{ 1, \ldots, n \})| = m ! |\mathcal{P}_m \{ 1, \ldots, n \}| \end{equation}
Formulation 1
Let $n, m \in \mathbb{N}$ each be a D996: Natural number such that
(i) \begin{equation} m \leq n \end{equation}
(ii) $\text{Inj}(\{ 1, \ldots, m \} \to \{ 1, \ldots, n \})$ is the D2222: Set of injections from $\{ 1, \ldots, m \}$ to $\{ 1, \ldots, n \}$
Then \begin{equation} |\text{Inj}(\{ 1, \ldots, m \} \to \{ 1, \ldots, n \})| = m ! \binom{n}{m} \end{equation}