第5讲-集合的划分与覆盖.pptVIP

有限集合的所有划分个数 * §1.5 集合的划分与覆盖 分门别类的思想是我们认知世界的基本方法之一。我们在了解与掌握外部世界时习惯于采用分类处理的办法。集合的分类，即对所处理的对象进行科学分类正是这种思想的体现。 集合覆盖 集合覆盖 二 集合划分(分类) 1 定义 若把一个集合A分成若干个叫做块的非空子集，使得A中每个元素至少属于一个块，那么这些块的全体构成的集合叫做A的一个覆盖。 又若A中每个元素属于且仅属于一个块，那么这些块的全体构成的集合叫做A的一个划分（或分划，分类)。 设A是任意集合，??P(A)。如果下列3个条件成立： 1) ??； 2) 任意 Ai, Aj∈ ?，有 Ai∩Aj = ; 3) 则称?是集合A的一种划分。 1）划分是覆盖的特例情形，即划分一定是覆盖，但覆盖不一定是划分； 例： 设A={a,b,c}, 则{{a,b},{b,c}}是A的覆盖，但 不是A的划分。 2）对空集合一般不讨论划分问题，约定其划分不存在； 3）非空集合A的划分方法一般有多种。 例 设A = {a, b, c}, 则A的所有不同的划分有: 最大划分 最小划分 2 交叉划分 设集合A有两种划分 令 定理 则 是A的一种划分，称为是的 交叉划分。 给定集合A的两种按如上形式定义的划分?1, ?2，若对于任意Ai∈ ?1，均存在Bj ∈?2，使得 Ai ? Bj，则称划分?1是?2的加细划分。 例 定理：任何两种划分的交叉划分，都是这两种划分的加细。 设|A| = n，A的不同划分的个数为N，S(n, k)表示将n个元素的 集合划分成k个块的方案数，则 且有以下等式成立：