珍珠湾ART

标题: 最多能有几个 [打印本页]

作者: 新来的 时间: 2011-7-17 19:10
标题: 最多能有几个

集合U由n个不同的点组成。选择U的若干个子集构成一个集类，使得这个集类中的任意两个集合都不存在包含关系。问：这个集类最多能有几个子集组成？

作者: HF: 时间: 2011-7-18 03:15
标题: 回复：最多能有几个

C(n,n/2) for n even
C(n,(n+1)/2) for n odd

原贴：

文章来源: 新来的于 2011-7-17 11:10:19 (北京时间: 2011-7-17 23:10:19)
标题：最多能有几个

作者: HF: 时间: 2011-7-18 03:45
标题: 回复：回复：最多能有几个

We can assume that all subsets in an "optimal" family to be of the same size, and the conclusion above follows easily. The reason we can make such assumption is as follows:
Let's assume that A is an "optimal" family (meaning it has the most number of subsets of all families, subjecting to the constrain as mentioned in the question), and let's assume that B in A is a subset that has the least size among all subsets in A. For any subset C, let's denote S_C to be the family of subsets which have the same size as C and differ with C by exactly two elements. Now, consider S_B, there are two possibilities:
(1) S_B is a subset of A
(2) S_B is not a subset of A
In the latter case, there is a subset D in S_B, which is not in A; Let d be the element in D such that d is not in B. We construct another "optimal" family A': A' is the same as A, except that the subset B is replaced by union(
B, {d}), it is easy to show that A' satisfies the constrains.
Repeat this procedure whenever a case (2) exists. In the end, we will get an "optimal" family with case (1) only. Let's still denote such an family by A.
Now, we prove that all subsets in A have the same size. Let B be a subset in A which has the least size, and we know S_B is a subset of A. Now for any C in S_B, we again have that S_C is a subset of A, and so on, in this way, all subsets of size as B can be "reached", therefore is in A. And by the constrains of A, A consists of all subsets of size of B.

原贴：

文章来源: HF:® 于 2011-7-17 19:15:16 (北京时间: 2011-7-18 7:15:16)
标题：回复：最多能有几个

C(n,n/2) for n even
C(n,(n+1)/2) for n odd

原贴：

文章来源: 新来的于 2011-7-17 11:10:19 (北京时间: 2011-7-17 23:10:19)
标题：最多能有几个

欢迎光临珍珠湾ART (http://art.zhenzhubay.com/)