一个具有n个元素的集合上的不同等价关系的个数若用B(n)来表示的话,如何证明:B(n+1)=∑[k=0到n]C(kn)B(k)n>=1C(kn)是组合数,n在下,k在上

Question

一个具有n个元素的集合上的不同等价关系的个数若用B(n)来表示的话,如何证明:B(n+1)=∑[k=0到n]C(k n)B(k) n>=1
C(k n)是组合数,n在下,k在上

Answer 1

等价关系和等价划分一一对应的,因此问题可转化为含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)