等价关系的个数

等价关系 : 设 R 为集合 A 上的关系, 如果 R 是自反的, 对称的, 传递的, 则称 R 为 A 上的等价关系.

等价类 : 设 R 是集合 A 上的等价关系, 对任意的 a \(\in\) A , 令

则称 [a]_R 为元素 a 关于 R 的等价类, 简称为 a 的等价类, 简记为 [a] , 即

所有等价类的集合称为集合 A 关于 R 的商集, 记为 A/R , 即 \(A/R = \{[a]_R|a \in A\}\).

那么 |A| = n 的等价关系有多少个 ?

A 中每个元素都有自已的等价类, 它们的等价类可以相同, 于是, 求等价关系的总数可类比于以下问题 :

有 n 个球, r 个盒子, 在保证每个盒子都非空的条件下, 球有几种放法.

可以用 dp 的集合划分思想考虑 :
\begin{aligned}
f[i][j] &: 表示在j个盒子放i个球所有合法选法的集合. \\
f[i][j] &= f[i - 1][j - 1] + j * f[i - 1][j].
\end

代码 :

#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
inline int lowbit(int x) { return x & (-x); }
#define ll long long
#define pb push_back
#define PII pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
const int N = 100;
int f[N][N];

int main() {
    IO;
    int n, ans = 0;
    cin >> n;
    
    for (int i = 1; i <= n; ++i) f[i][i] = f[i][1] = 1;

    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            f[i][j] = j * f[i - 1][j] + f[i - 1][j - 1];
             
    for (int i = 1; i <= n; ++i) ans += f[n][i];
    cout << ans;
    
    return 0;
    
}