Combinatorics (Fall 2010)/Problem set 6

From EtoneWiki
Jump to: navigation, search

Problem 1

个小球,共m种颜色,每种颜色两个球,相同颜色的球不可区分。

取k个球,有多少种取法。

Problem 2

共有 种颜色。对于如下的图,有多少个对顶点的着色,使得任意相邻两点不共色。

File:Color graph.png

Problem 3

个变量的个子句 (clause) 的 conjunctive normal form (CNF) 逻辑表达式。

证明:对于任何如上的,总存在一个的赋值,满足至少个子句。

Problem 4

一系列集合,满足

  • 任何 有至少 个元素;
  • 任何元素至多属于 个集合

证明: 有 system of distinct representatives (SDR)。

Problem 5

为一个antichain,即 。此外,

证明:

(使用课上教的某定理)