等价关系经典计数问题

题面¶

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

证明 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 \]