【离散数学】gpt教我学数学6-Toy模板网

这篇具有很好参考价值的文章主要介绍了【离散数学】gpt教我学数学6。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

设A是n元集（n>=1)，则从A到A的函数中有几个双射函数，有几个单射函数？

设 $A$ 为 $n$ 元集，下面分别计算从 $A$ 到 $A$ 的双射函数和单射函数的数量：

一个双射函数 $f:A\rightarrow A$ 必须是一一对应的，即 $f$ 必须是一个双射。因此，可以先考虑如何选取 $A$ 中的元素，使得它们在 $f$ 中的像是 $A$ 中的 $n$ 个元素的一个排列。方法如下：

选取 $A$ 中的一个元素 $a_1$ ，将其映射到 $A$ 中的任意一个元素上，共有 $n$ 种选法；
选取 $A$ 中的另一个元素 $a_2$ ，将其映射到 $A$ 中剩下的 $n - 1$ 个元素中的一个上，共有 $n - 1$ 种选法；
以此类推，选取 $A$ 中的第 $i$ 个元素 $a_i$ ，将其映射到 $A$ 中剩下的 $n - i + 1$ 个元素中的一个上，共有 $n - i + 1$ 种选法。

因此，从 $A$ 到 $A$ 的双射函数的数量为 $n\times(n-1)\times\cdots\times 2\times 1=n!$ 。

一个单射函数 $f:A\rightarrow A$ 必须满足对于任意 $x_1,x_2\in A$ ，如果 $x_1\neq x_2$ ，则 $f(x_1)\neq f(x_2)$ 。因此，可以按照如下方式计算单射函数的数量：

选取 $A$ 中的一个元素 $a_1$ ，将其映射到 $A$ 中的任意一个元素上，共有 $n$ 种选法；
选取 $A$ 中的另一个元素 $a_2$ ，将其映射到 $A$ 中除了 $a_1$ 以外的 $n - 1$ 个元素中的一个上，共有 $n - 1$ 种选法；
以此类推，选取 $A$ 中的第 $i$ 个元素 $a_i$ ，将其映射到 $A$ 中除了 $a_1,\ldots,a_{i-1}$ 以外的 $n - i + 1$ 个元素中的一个上，共有 $n - i + 1$ 种选法。

因此，从 $A$ 到 $A$ 的单射函数的数量为 $n\times(n-1)\times\cdots\times(n-i+1)\times\cdots\times 2\times 1=n!/(n-i)!$ ，其中 $i$ 表示选取的元素个数。

需要注意的是，当 $i > n$ 时，单射函数的数量为 $0$ ，因为无法选取 $n + 1$ 个不同的元素映射到 $n$ 个元素上。因此，从 $A$ 到 $A$ 的单射函数的数量为：

$\sum_{i=0}^n \frac{n!}{(n-i)!} = n!\sum_{i=0}^n \frac{1}{(n-i)!}$

这里将求和式拆开，分别考虑 $i=0,1,\ldots,n$ 的情况，其中 $i = 0$ 时， $\frac{n!}{(n-i)!}=n!$ 。因此：

$\sum_{i=0}^n \frac{n!}{(n-i)!} = 1+n!+\frac{n!}{2!}+\cdots+\frac{n!}{n!} = \sum_{i=0}^n \frac{n!}{i!}$

这是因为 $n!$ 乘以 $\sum_{i=0}^n \frac{1}{i!}$ 就是 $n$ 的阶乘级数的前 $n + 1$ 项之和，而 $n$ 的阶乘级数的前 $n + 1$ 项之和就是 $e^n$ ，因此：

$\sum_{i=0}^n \frac{n!}{(n-i)!} = n!\sum_{i=0}^n \frac{1}{(n-i)!} = n!e^n$

因此，从 $A$ 到 $A$ 的单射函数的数量为 $n!e^n$ 。

为啥单射函数的数量不是n！

您的疑问是正确的，我之前的回答中有误。从 $A$ 到 $A$ 的单射函数的数量应该是 $n!$ 。

一个单射函数 $f$ 从 $A$ 到 $A$ 的定义是：对于任意 $x_1, x_2 \in A$ ，如果 $x_1 \neq x_2$ ，则 $f(x_1) \neq f(x_2)$ 。我们可以按照如下方式计算单射函数的数量：

选取 $A$ 中的一个元素 $a_1$ ，将其映射到 $A$ 中的任意一个元素上，共有 $n$ 种选法；
选取 $A$ 中的另一个元素 $a_2$ ，将其映射到 $A$ 中除了 $a_1$ 以外的 $n - 1$ 个元素中的一个上，共有 $n - 1$ 种选法；
以此类推，选取 $A$ 中的第 $i$ 个元素 $a_i$ ，将其映射到 $A$ 中除了 $a_1,\ldots,a_{i-1}$ 以外的 $n - i + 1$ 个元素中的一个上，共有 $n - i + 1$ 种选法。