# 题面

设 $f:A\to B$ 是函数，定义 A 上的关系 R， $\forall a,b \in A$ ，a R b 当且仅当 f (a) = f (b) 。

证明 R 是等价关系，并给出它的等价类和商集，求这样的等价关系有多少个？

# 证明 R 是等价关系

显然 R 是等价关系，因为对∀a, b, c\in A，f (a)=f (a), f (a)=f (b) 蕴涵 f (b) = f (a) , f (a) = f (b) 且 f (b) = f (c) 蕴涵 f (a) = f (c) ，即 R 是自反、对称、传递的。

对任意 a\in A， $[a]_R= \{x∣f(x)=f(a) \},A/R=\{[a]_R∣a\in A\}$ 。

实际上，对任意 a\in A，若 f (a)=y\in B，则 $[a]_R=f^{-1} (y)$ 。

因此若 f 是满函数，则 $A/R=\{f^{-1} (\{b\})∣b\in B\}$ ，即商集 A/R 中的等价类与 B 的元素一一对应。

对集合 A 上的任意等价关系 R ，自然映射 $ρ:A→A/R,ρ(a)=[a]_R$ 是满函数，因此 A 上的等价关系与以 A 为定义域的满函数对应。

设 |A|=n ，则 A 上有 m 个等价类的等价关系个数等于 A 到 $Z_m=\{0, 1, ⋯, m-1\}$ 的满函数个数除以 m! (在 Z_m 的元素作为原像的所有可能排列中选一个即可)。

设 |A|=n ，则 A 上不同的等价关系有多少个？

等价于：设 | A|=n，则 A 上含 m 个等价类的等价关系有多少个？

当 | A|=n, |B|=m，n≥m，A 到 B 的满函数个数是：

$m^n- C(m, 1)(m-1)^n+ ⋯+ (-1)^k C(m, k) (m-k)^n+ ⋯+ (-1)^{m-1} C(m,m-1)\cdot 1^n$

因此 n 元素集合 A 上有 m 个等价类的等价关系有：

$B(n, m)=\frac{\sum_{k=0}^{m-1}(-1)^k C(m,k) (m-k)^n }{m!}$

从而 n 元素集合 A 上的不同等价关系个数有：

$B(n)=\sum_{m=1}^n\frac{\sum_{k=0}^{m-1}(-1)^k C(m,k) (m-k)^n}{m!}$

用 B (n) 表示 n 元素集合上不同等价关系的个数，教材给出了如下递推关系式：

$B(n+1)=\sum_{k=0}^n C(n, k)B(k)$

这个递推关系式的理解是：对于有 n+1 元素集合 (不妨假定为 {0,1, ⋯, n}) 的划分，按照最后一个元素 n 所在的划分块进行分类：

若 n 不与 {0, ⋯, n-1} 的任意元素在一个划分块，即 n 单独在一个划分块，这种划分的个数就等于 {0, ⋯, n-1} 的划分个数，即等于 B (n)
若 n 与 {0, ⋯, n-1} 的某 j=n-k (k=0, ⋯, n) 个元素在一个划分块，则这 j 个元素有 C (n, j) = C (n,n-k) = C (n,k) 种选择，而每种选择的划分个数等于剩下的 k 个元素构成集合的划分个数，即等于 B (k)，因此有 C (n,k) B (k) 个划分

当 | A|=3，则 A 上等价关系个数：

$1+\frac{2^3-C(2,1)}{2!}+\frac{3^3-C(3,1) 2^3+ C(3,2)}{3!}=1+3+1=5$

当 | A|=4，则 A 上等价关系个数:

$1+\frac{2^4-C(2,1)}{2!}+\frac{3^4-C(3,1) 2^4+C(3,2)}{3!}+\frac{4^4-C(4,1) 3^4+C(4,2)2^4-C(4,3)}{4!}=15$