posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

离散学习笔记 - 二元关系

Posted on 2007-07-25 11:03 ZelluX 阅读(360) 评论(0)  编辑  收藏 所属分类: Mathematics
1.闭包 Closure
(1) 自反 reflexive
对称 symmetric
传递 transitive
(2) 其中,设R属于A*A(A为非空集合),则r(R) = R与A上恒等关系的并,s(R) = R与R的逆的并,
t(R) = R 并 R^2 并 R^3 并...并 R^l。
(3) rs(R) = sr(R)
rt(R) = tr(R)
st(R) 属于 ts(R)


2. 等价关系和划分
(1) 设R属于A*A,若R是自反的、对称的和传递的,则称R为A上的等价关系。
(2) 令[x]R为x的关于R的等价类,在不引起混乱时可简记为[x]。
(3) 以关于R的全体不同的等价类为元素的集合称为A关于R的商集,记作A/R。
(4) 设A为非空集合,若存在A的一个子集族S满足
a. S中不包含空集元素
b. 对于一切x,y属于S,且x,y不相等,则x与y不相交的(disjoint)
c. S中所有集合的并为A
则称S为A的一个划分,S中元素称为划分块。
(5) 非空集合A上的等价关系与A的划分是一一对应的。
(6) 第二类Stirling数,表示将n个不同的球放入r个相同的盒子中的方案数,可以由下列递归式计算:
f(n, r) = r * f(n - 1, r) + f(n - 1, r - 1)
很容易理解的一个递归式,其中初始状态为
f(n, 0) = 0, f(n, 1) = 1, f(n, 2) = 2^(n-1) - 1, f(n, n - 1) = C(n, 2), f(n, n) = 1
(7) A上等价关系的数量可以通过Stiring数求出,以A={a,b,c,d}为例
f(4,1) + f(4,2) + f(4,3) + f(4,4) = 15

只有注册用户登录后才能发表评论。


网站导航: