n个元素有多少个等价关系

一个具有n个元素的集合上的不同等价关系的个数若用B(n)来表示的话,如何证明:B(n+1)=∑[k=0到n]C(kn)B(k)n>=1C(kn)是组合数,n在下,k在上... 一个具有n个元素的集合上的不同等价关系的个数若用B(n)来表示的话,如何证明:B(n+1)=∑[k=0到n]C(k n)B(k) n>=1
C(k n)是组合数,n在下,k在上
展开
 我来答
闽帅第五修
2020-02-17 · TA获得超过1133个赞
知道小有建树答主
回答量:1722
采纳率:100%
帮助的人:7.9万
展开全部
等价关系和等价划分一一对应的,因此问题可转化为含n个元素有多少个等价划分,也就是这n个元素有多少种分组的方法.
B(n)就表示这个n个元素有多少种分组的方法.
现在增加一个元素,有如下一些情况
1、增加的这个元素单独为一组,其余n个元素有B(n)种分法
2、增加的元素,与n个元素中任意一个元素为一组,有C(1,n)种组合,其余n-1个元素有B(n-1)种分法,一共就有C(1,n)B(n-1)种分法.
3、增加的元素,与n个元素中任意两个元素为一组,有C(2,n)种组合,其余n-2个元素有B(n-2)种分法,一共就有C(2,n)B(n-2)种分法.
...
i、增加的元素,与n个元素中任意i个元素为一组,有C(i,n)种组合,其余n-i个元素有B(n-i)种分法,一共就有C(i,n)B(n-i)种分法.
...
n、增加的元素,与n个元素全部为一组
因此n+1个元素所有情况的分法
B(n+1)=B(n)+C(1,n)B(n-1)+...C(i,n)B(n-i)+...1
=C(n,n)B(n)+C(n-1,n)B(n-1)+...+C(n-i,n)B(n-i)+...C(0,n)B(0) (B(0)=1,并利用C(i,n)=C(n-i,n))
=∑[k=0到n]C(k n)B(k)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

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

类别

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

说明

0/200

提交
取消

辅 助

模 式