在数学中，函数在描述一个集合的元素如何与另一个集合的元素相关联方面起着核心作用。通常情况下，我们不仅对寻找一个函数感兴趣，更感兴趣的是知道在两个给定集合之间可以形成多少个不同的函数。这在集合论和组合学中引出了一个重要的计数问题。
从一个集合到另一个集合的函数数量
假设 X 和 Y 是两个集合，分别包含 m 和 n 个元素。在从 X 到 Y 的函数中，X 的每一个元素必须映射到 Y 的一个元素。因此，X 中的每个元素都有 ‘n’ 个备选元素可供选择。所以，函数的总数将是 n×n×n..（共 m 次）= $n^m$。
> 例如： X = {a, b, c} 且 Y = {4, 5}。从 X 到 Y 的函数可以如下图表示。
>
> 考虑到将 X 的元素映射到 Y 的元素的所有可能性，函数集可以用表 1 表示。
从一个集合到另一个集合的满射函数数量
设 X 和 Y 是两个有限集合，且 ∣X∣ = m，∣Y∣ = n。函数 f : X → Y 将 X 的每一个元素恰好分配给 Y 的一个元素。
- 对于 X 中的每个元素，在 Y 中都有 n 种选择。
- 由于 X 中有 m 个元素，因此函数的总数为 $n^m$。
> 注意：
>
> * 该公式仅在 m ≥ n 时有效。
> * 如果 m < n，满射函数的数量为 0，因为不可能用到 Y 的所有元素。
关于可能函数总数的例题
问题 1： 设 X, Y, Z 分别是大小为 x, y 和 z 的集合。设 W = X x Y。设 E 为 W 的所有子集的集合。从 Z 到 E 的函数数量是多少？
解决方案：
> 题目给定 W = X x Y，因此 W 中的元素数量为 xy。由于 E 是 W 的所有子集的集合，因此 E 中的元素数量为 $2^{xy}$。从 Z（包含 z 个元素的集合）到 E（包含 $2^{xy}$ 个元素的集合）的函数数量是 $(2^{xy})^z = 2^{xyz}$。所以正确的选项是 (D)。
问题 2： 设 S 表示所有函数 f: {0,1}^4 → {0,1} 的集合。用 N 表示从集合 S 到集合 {0,1} 的函数数量。Log2(Log2N) 的值是 。
解决方案：
> 如题所示，S 表示所有函数 f: {0, 1}^4 → {0, 1} 的集合。从 {0,1}^4（16 个元素）到 {0, 1}（2 个元素）的函数数量是 $2^{16}$。因此，S 有 $2^{16}$ 个元素。此外，题目给定 N 表示从 S（$2^{16}$ 个元素）到 {0, 1}（2 个元素）的函数数量。因此，N 有 $2^{(2^{16})}$ 个元素。计算所需值， Log2(Log2 ($2^{(2^{16})}$)) = Log2($2^{16}$) = 16。
问题 3： 从集合 X = {1, 2, 3, 4} 到集合 Y = {a, b, c} 的满射函数（映上函数）的数量。
解决方案：
> 使用 m = 4 和 n = 3，满射函数的数量为：
> $3^4 – C(3,1)(2^4) + C(3,2)(1^4) = 36$。
相关文章：
> * 数学 | 可能函数的总数
> * 可能函数的数量
> * 布尔函数的数量
练习题 – 可能函数的总数
问题 1： 从一个包含 3 个元素的集合到一个包含 2 个元素的集合，可以定义多少个函数？
问题 2： 如果集合 A 有 4 个元素，集合 B 有 3 个元素，从 A 到 B 可以定义多少个函数？
问题 3： 从一个包含 3 个元素的集合到一个包含 5 个元素的集合，可以定义多少个单射函数（一对一函数）？
问题 4： 从一个包含 4 个元素的集合到一个包含 3 个元素的集合，可以定义多少个满射函数（映上函数）？
问题 5： 如果集合 A 中有 4 个元素，集合 B 中有 3 个元素，并且 B 中的每个元素必须是 A 中恰好 2 个元素的像，那么可能有多少个这样的函数？
问题 6： 从一个包含 3 个元素的集合到其自身，可以定义多少个函数？
问题 7： 考虑一个从包含 4 个元素的集合到包含 2 个元素的集合的函数。存在多少个函数，使得陪域中的每个元素都至少被定义域中的一个元素映射？
问题 8： 从一个包含 3 个元素的集合到另一个包含 3 个元素的集合，有多少个双射函数（一对一且映上）？
问题 9： 从一个包含 2 个元素的集合到一个包含 4 个元素的集合，如果函数的值域必须恰好包含 2 个元素，可以定义多少个函数？
问题 10： 如果集合 A 有 5 个元素，集合 B 有 4 个元素，且 B 中恰好有 3 个元素必须被用作 A 中至少一个元素的像，那么从 A 到 B 有多少个函数？