本文共 1280 字，大约阅读时间需要 4 分钟。

        一个集合S中有n个元素，问S->S的所有二元关系中，有多少个关系满足对称，传递，但不满足自反的。

        做这个题需要了解bell数。先定义一下C(n,k)表示从n个不同的元素中取k个的方案数；B(n)表示bell数，即将拥有n个元素的集合S划分为若干子集的方案数。B(0)=1，B(1)=1，B(2)=2，B(3)=5，B(4)=15...

        bell数满足这样的递推公式：B(n+1)=C(n,0)*B(0)+C(n,1)*B(1)+C(n,2)*B(2)+...+C(n,n)*B(n)。为什么这个公式成立呢。。举个例子，你现在已经知道了B(0)~B(3)，需要推出B(4)，也就是在集合{a,b,c}的基础上，加上一个d，然后划分集合{a,b,c,d}。对于原集合{a,b,c}，我们可以在其中选0个元素分离出来(有C(3,0)种方案)，任意分割(有B(0)种方案)，把d加入剩下的3个元素中，也就是C(n,0)*B(0)。同理，我们还可以把{a,b,c}中的1个元素、2个元素、3个元素分离出来。。。加起来就能得到上面的递推式。

        然后我们分析题目，因为不能满足自反，一定要满足对称和传递，所以一定会有若干元素不能出现在ρ中。如果ρ中只有0个元素，它的方案数是C(n,0)*B(0)，同理ρ中有1、2个元素时，方案数是C(n,1)*B(1)、C(n,2)*B(2)，ρ中最多会有n-1个元素，此时方案数为C(n,n-1)*B(n-1)。

        于是：

ans=C(n,0)*B(0)+C(n,1)*B(1)+C(n,2)*B(2)+...+C(n,n-1)*B(n-1)=B(n+1)-C(n,n)*B(n)=B(n+1)-B(n)

        注意利用了C(n,n)=1。

        求解过程可以利用一个叫bell三角的东西，不多说了，大家可以搜索。

import java.util.Scanner;public class Main {    public static void main(String[] args) {        final int mod=1000000007;        int[][] bell = new int[4010][4010];        bell[0][0]=1;        Scanner scan=new Scanner(System.in);        int n = scan.nextInt();        for(int i=1;i<=n;i++){            bell[i][0]=bell[i-1][i-1];            for(int j=1;j<=i;j++){                bell[i][j]=bell[i-1][j-1]+bell[i][j-1];                bell[i][j]%=mod;            }        }        System.out.println(bell[n][n-1]);    }}

转载地址：https://blog.csdn.net/squee_spoon/article/details/47617861 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！