Little Johnny has recently learned about set theory. Now he is studying binary relations. You've probably heard the term "equivalence relation". These relations are very important in many areas of mathematics. For example, the equality of the two numbers is an equivalence relation.
A set ρ of pairs (a, b) of elements of some set A is called a binary relation on set A. For two elements a and b of the set A we say that they are in relation ρ, if pair 
, in this case we use a notation 
.
Binary relation is equivalence relation, if:
-
It is reflexive (for any a it is true that
); -
It is symmetric (for any a, b it is true that if , then
); -
It is transitive (if and
, than 
).
Little Johnny is not completely a fool and he noticed that the first condition is not necessary! Here is his "proof":
Take any two elements, a and b. If , then (according to property (2)), which means (according to property (3)).
It's very simple, isn't it? However, you noticed that Johnny's "proof" is wrong, and decided to show him a lot of examples that prove him wrong.
Here's your task: count the number of binary relations over a set of size n such that they are symmetric, transitive, but not an equivalence relations (i.e. they are not reflexive).
Since their number may be very large (not 0, according to Little Johnny), print the remainder of integer division of this number by 109 + 7.
A single line contains a single integer n (1 ≤ n ≤ 4000).
In a single line print the answer to the problem modulo 109 + 7.
1
1
2
3
3
10
If n = 1 there is only one such relation — an empty one, i.e. 
. In other words, for a single element x of set A the following is hold: 
.
If n = 2 there are three such relations. Let's assume that set A consists of two elements, x and y. Then the valid relations are ,ρ = {(x, x)}, ρ = {(y, y)}. It is easy to see that the three listed binary relations are symmetric and transitive relations, but they are not equivalence relations.
题目大意：
一个由若干个数对$\left(a,b\right)\left(a,b\in A\right)$组成的集合$\rho$被称为一个集合A上的二元关系。若$\left(a,b\right)\in\rho$，则a，b满足二元关系$\rho$，记作$a\mathop{\sim}^\rho b$。
如果满足一下三个性质，一个二元关系是相等关系。
1. 自反性：$\forall a,\,a\mathop{\sim}^\rho a$
2. 对称性：$\forall a\mathop{\sim}^\rho b,\,b\mathop{\sim}^\rho a$
3. 传递性：$\forall a\mathop{\sim}^\rho b,b\mathop{\sim}^\rho c,\,a\mathop{\sim}^\rho c$
Little Johnny发现第一条是没有必要的，因为$a\mathop{\sim}^\rho b\Rightarrow b\mathop{\sim}^\rho a\Rightarrow a\mathop{\sim}^\rho a$。
显然他的证明是错误的，所以求一个有n个元素的集合上的满足对称性和传递性但不满足自反性的二元关系的个数。
只要$\exists a\in A,\nexists a\mathop{\sim}^\rho b\left(b\in A\right)$就行了，所以答案是$\sum_{i=0}^{n-1}C_n^i\times B_i$。
$C_n^i$表示在n个元素中任选i个元素的方法数，这i个元素和其他元素有关系，剩余的元素则没有。
$B_i$是贝尔数，把i个元素分成若干个非空集合的方法数。表示把有关系的i个元素分成若干个非空集合，在同一个集合中的元素满足关系。
代码在此。
评论 (0)
