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

 我来答
舒适还明净的海鸥i
2022-07-17 · TA获得超过1.7万个赞
知道小有建树答主
回答量:380
采纳率:0%
帮助的人:69.9万
展开全部
这个的答案是:贝尔数(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).
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式