等价关系经典计数问题

题面

设 $f:A\to B$ 是函数，定义 A 上的关系 R，$\mathrm{\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\mid f(x)=f(a)\},A/R=\{[a{]}_R\mid a\in A\}$。

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

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

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

设 |A|=n ，则 A 上有 m 个等价类的等价关系个数等于 A 到 $Z_m=\{0,1,\cdots ,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+\cdots +(-1{)}^{k}C(m,k)(m-k{)}^n+\cdots +(-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$$