给定一个集合A,|A|=n,求在A上有多少个不同的等价关系?

给定一个集合A,|A|=n,求在A上有多少个不同的等价关系?
给定一个集合A,|A|=n,求在A上有多少个不同的等价关系?

给定一个集合A,|A|=n,求在A上有多少个不同的等价关系?
这个的答案是：贝尔数（Bell Number）
没有准确求出Bell Number的公式,只能递推.
A上的等价关系与集合A的划分一一对应,所以只要求出A的划分数即可.
所谓A的划分,是指把A分成子集A1、A2、……,这些集合非空、两两不相交、且并集为A.
每一个等价关系对应一个划分：元素a、b等价当且进当它们属于同一子集.
A的划分数就叫贝尔数B(n).
下面求贝尔数.
S(n,k)代表元素数量为n的集合A划分成k个子集的方法.
B(n)=S(n,1)+S(n,2)+...+S(n,n)
主要的递推关系是求S(n,k)的.
S(n,k) = S(n-1,k-1) + k S(n-1,k)
这个公式的意思是这样：
把n个元素划分成k个子集,有两种情形：
1.最后一个元素an单独构成一个子集.
这相当于其它n-1个元素被划分成k-1个子集,然后再加上{an}这个子集.
所以,这种情形的数量是：S(n-1,k-1)
2.最后一个元素an不单独构成一个子集.
这相当于其它n-1个元素被划分成k个子集,然后再挑选一个子集（k种方式挑选）把an放入.
所以,这种情形的数量是：k S(n-1,k)
把1、2种情形相加,就是上面那个递推公式了.
为了用上面那个递推公式求出值来,还需要初始条件：
S(n,1) = S(n,n) = 1
如果你想找更多的资料,可以看下面的链接.
在下面参考资料的链接中,我们这里的S(n,k)被称为：
二型斯特林数（Stirling Number of the Second Kind）.

合上每个等价关系对应集合的一种划分,集合的每一种划分又对应于该集合的一个等价关系,不同的等价关系对应于集合的划分也不同,因此集合有多少不同划分,就有多少不同等价关系,三个元素的集合共有5种不同划分,(含有1块和3块各有1种,含有2块有3种),故含有三个元素的集合，可以确定5种等价关系. 如A={1，2，3}，则5种不同划分为 {{1}, {2}, {3}};{{1}, {2,3}};{{1,3},...

全部展开

合上每个等价关系对应集合的一种划分,集合的每一种划分又对应于该集合的一个等价关系,不同的等价关系对应于集合的划分也不同,因此集合有多少不同划分,就有多少不同等价关系,三个元素的集合共有5种不同划分,(含有1块和3块各有1种,含有2块有3种),故含有三个元素的集合，可以确定5种等价关系. 如A={1，2，3}，则5种不同划分为 {{1}, {2}, {3}};{{1}, {2,3}};{{1,3}, {2}};{{1,2}, {3}};{{1, 2, 3}}; 对应的等价关系为 R1={(1,1),(2,2),(3,3)};R2={(1,1),(2,2),(2,3),(3,2),(3,3)}; R3={(1,1),(1,3),(3,1),(2,2),(3,3)}; R4={(1,1),(1,2),(2,1),(2,2),(3,3)}; R5={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)}; 一般地,对有n个元素的集合有Bn种不同的划分(等价关系),Bn=2n!/((n+1)n!n!),如4个元素的集合，可以确定14种等价关系.

收起

两个或零个。
A={0}或{1，-1}或{2，-2}或{3，-3}或……额

我还不知道等价关系是什么，先去查一查。

看了，看不懂。

你不要相信他，它是复制的其他题目的回答。你看：

给定一个集合A,|A|=n,求在A上有多少个不同的等价关系? 求解：给定一个数组a[N],我们希望构造数组b[N],其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]. 下面是完整题目给定一个数组a[N],我们希望构造数组b[N],其中b[i]=a[0]*a[1]*...*a[N-1]/a[i].在构造过程：不允许使用除法 给定集合A,由集合A的所有子集组成的集合,称为集合A的幂集,记为P(A).设A={a,b,c},求P(A) 集合A,|A|=n,求在A上有多少个不同的等价关系? 给定集合A,B 定义A*B={X,X=M-N,M属于A,N属于B},若A={4,5,6} B={1,2,3}则集合A*B中的所有元素之和为? 给定集合S={a,b,c,d,e},R={,,,,}为S上的二元关系,在关系R的基础上求一个相容关R‘（添加的序偶最少）并求出R'中的最大相容类 给定集合S={a,b,c,d,e},R={,,,,}为S上的二元关系,在关系R的基础上求一个相容关R‘（添加的序偶最少）帮下忙.... 给定集合A.B定义为A*B={x|x=m.n,m∈A.n∈B}若A={4,5,6},B={1,2,3}则A所以元素合为? 1.若集合M={2,a,b}、集合N={2a,2,b^2},且M=N、求a,b的值2.在集合A={x/ax^2-2x+1=0} B={X/X^2-2X+a=0} 中已知集合A只有一个元素、求集合A和B哪一个是错的啊？ 已知集合A={x∈N/8/6-x∈Z},试求集合A. 排列组合：给定n个相同的集合,每个集合中有m个元素,从每个集合中任意选一元素,这些元素的组合数是多少例如：n = 2, m = 2 ,假设集合S = {a, b} 时,一共有 aa,ab,bb,这3种不同的组合.求通式和过程 已知集合A={x|x=3n,n∈N},集合B={x|x=6n,n∈N},求集合A交集合B,A并集合B 已知数列有如下递推关系F(N)=(1+X%)F(N-1)-A;给定F1,N,F(N),A 求x% 已知集合A={a|a^2+ka-k-1=0},A中的元素不在集合{4,7,10}中,A中只有一个元素在集合{2,3,4,7,10}中,求集合A?已知集合A={a|a^2+ka-k-1=0},A中的元素不在集合{4,7,10}中,A中只有一个元素在集合{2,3,4,7,10}中,求集合 数学集合的基础疑问x=空集 集合A=N为什么x不属于集合A?求详解 设有两集合A={3n+2|n∈N},B={4n+1|n∈N},若将集合A∩B的元素按从小到大顺序排列在网上看到答案了,还有,我求了一个12k+5,是A交B吗?只答案的半毛分都不给!但是本题答案是4025怎么来的啊? 已知集合A={1,3,5,7,9},B={2,4,6,8,10},在集合A中任取一个元素m,在集合B中任取一个元素n,m＞n的概率? 用C语言设计这样一个程序：设集合A=｛a[1],a[2],a[3]...a[m]｝集合B=｛b[1],b[2],b[3]...b[n]｝求A交B