从非空有限集到另一集合的满射映射数量及双射证明相关技术问询

嘿，上周我在课堂上学函数的时候，教授抛给我们几个得用排列来证明的映射计数公式，我把相关的核心逻辑整理出来了，咱们一起过一遍：

先明确基础设定：我们取两个非空的有限集合 $X$ 和 $Y$，其中 $X$ 的元素个数是 $m$，$Y$ 的元素个数是 $n$，这里 $m$ 和 $n$ 都是正整数（$m,n \in \Bbb{N}$）。

首先有个基本结论：从 $X$ 到 $Y$ 能存在**单射（one-one mapping）**的充要条件是 $m \leq n$。

接下来用排列的知识，我们可以证明这种单射的总数量是 $^nP_m$，具体推导过程如下：

先把两个集合的元素明确写出来：
$X = {x_1, x_2,....,x_m }$
$Y = {y_1, y_2,....,y_n }$

对于映射 $f: X \rightarrow Y$ 来说，要满足单射的要求（每个 $X$ 中的元素都对应 $Y$ 中唯一的元素，没有重复），我们可以逐个给 $X$ 里的元素找对应对象：

• 给 $x_1$ 选对应元素时，$Y$ 里的 $n$ 个元素都可以选，有 $n$ 种选择；
• 给 $x_2$ 选的时候，不能和 $x_1$ 的对应元素重复，所以剩下 $n-1$ 种选择；
• 以此类推，到第 $m$ 个元素 $x_m$ 时，已经用了 $m-1$ 个 $Y$ 里的元素，所以还剩 $n - m + 1$ 种选择；

把这些选择数相乘，得到的总数量就是 $n \times (n-1) \times ... \times (n-m+1)$，而这正好就是排列数 $^nP_m$ 的定义——从 $n$ 个元素里选 $m$ 个进行有序排列的数量，所以我们就证明了从 $X$ 到 $Y$ 的单射数量是 $^nP_m$。

（注：原文里的映射定义没写完，我就基于常规的单射证明逻辑补全了核心推导部分，方便大家理解～）

备注：内容来源于stack exchange，提问作者Sudarshan Bhuyan