codeforces 569 D. Symmetric and Transitive (组合数学 第二类斯特林数 贝尔数)

D. Symmetric and Transitive
time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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:

  1. It is reflexive (for any a it is true that );
  2. It is symmetric (for any ab it is true that if , then );
  3. 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.

Input

A single line contains a single integer n (1 ≤ n ≤ 4000).

Output

In a single line print the answer to the problem modulo 109 + 7.

Sample test(s)
input

output

input

output

input

output

Note

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.

 

给出n个元素的集合上满足传递律,交换律,但不满足自反律的二元关系个数.

还以为是我离散数学没认真听才没做出来...

题解:http://blog.csdn.net/mengzhengnan/article/details/47424295

 

贝尔数(集合的划分数目)

http://baike.baidu.com/link?url=kw5Kxe3nSvRJR0TpJUpMrORcQL8fyZFpJlT9_o0RlGYOy0bKFobabPPSj3LxGfy7o1qGVycrYK4Iags3hMFq0a

在组合数合里,贝尔数给出了集合划分的数目,以数学家埃里克·坦普尔·贝尔(Eric Temple Bell)命名,是组合数学中的一组整数数列。[1]
以B0= B1=1为始, 首几项的贝尔数为:1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …(OEIS的A000110数列
Bn基数n集合划分数目。集合S的一个划分是定义为S的两两不相交的非空子集的族,它们的并是S。例如B3 = 5因为3个元素的集合{abc}有5种不同的划分方法:
  • {{a}, {b}, {c}}
  • {{a}, {bc}}
  • {{b}, {ac}}
  • {{c}, {ab}}
  • {{a, b, c}}

B0是1因为空集

正好有1种划分方法。划分的定义要求空集的划分中的每个成员都是非空集合,而它们的并是

本身。所以

是它自身的唯一划分。(这是定义所允许的因为

2公式编辑

贝尔数适合递推公式:
它们也适合“Dobinski公式”:

期望值为1的泊松分布的”n”次

它们也适合“Touchard同余”:若p是任意质数,那么
每个贝尔数都是”第二类Stirling数”的和
Stirling数S(n, k)是把基数为n的集划分为正好k个非空集的方法的数目。
把任一概率分布的n次矩以首n个累积量表示的多项式,其系数和正是第n个贝尔数。这种数划分的方法不像用Stirling数那个方法粗糙。
贝尔数的指数母函数

3贝尔三角形编辑

用以下方法建构一个三角矩阵(形式类似杨辉三角形):
(1) 第一行第一项是1(a_{1,1} = 1)

(2) 对于n>1,第n行第一项等同第n-1行最后一项。(

(3) 对于m,n>1,第n行第m项等于它左边和左上方的两个数之和。(

结果如下:(OEIS的A011971数列[2] )
每行首项是贝尔数。每行之和是第二类Stirling数
这个三角形称为贝尔三角形、Aitken阵列或Peirce三角形(Bell triangle, Aitken’s array, Peirce triangle)。