部分排序的数目问题

mathe · 发表于 2008-6-28 14:12:53

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

题目思想来源于:http://tieba.baidu.com/f?kz=145132870
给定n个数据，我们知道其中部分数据的大小关系，由此可以得到一个偏序关系集。请问对于给定的n,不等价的偏序关系集有多少个。
比如n=1，那么偏序关系集中只有一个元素，即没有任何关系。
而n=2时，偏序关系集中有两个不等价的元素，即
i)不知道两个元素大小关系
ii)一个元素大于另外一个元素。(比如A>B,而关系集B>A我们认为可以同A>B等价）
而n=3时，偏序关系集有5个相互不等价的元素
i)不知道三个元素间的大小关系
ii)仅知道A>B. (而仅知道B>A, 或仅知道B>C等都和它等价）
iii)知道A>B>C
iv)知道A>B&&A>C
v)知道A>C&&B>C
现在要求对于给定n，计算不等价的偏序关系的数目。

无心人 · 发表于 2008-6-28 14:20:55

哇，你改签名了阿

mathe · 发表于 2008-6-28 14:27:23

原帖由 无心人 于 2008-6-28 14:20 发表
哇，你改签名了阿

我怎么不知道？

说实在，就是变化了我也看不出来

无心人 · 发表于 2008-6-28 14:36:27

我在分解中
争取到晚上7点能看到分解结果
明天我要看看你签名内容

无心人 · 发表于 2008-6-28 14:37:19

对于4个的你能列举下么？
是否是17个？

mathe · 发表于 2008-6-28 14:39:19

映象中你分解过的，我应该没有修改过

4个我没有枚举过，我觉得用手工方法枚举已经太复杂了，就放弃了

无心人 · 发表于 2008-6-28 14:45:07

你签名能看到什么好玩的

mathe · 发表于 2008-6-28 14:48:35

一点也不好玩

无心人 · 发表于 2008-6-28 14:52:08

呵呵
看来有必要看看
谁要我这么好奇呢

无心人 · 发表于 2008-6-28 14:58:19

对于n个数之间完全知道的大小关系
是否能分成$\frac{n!}{2}$类

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 部分排序的数目问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。