Combinatorics (Fall 2010)/Problem set 6
Problem 1
[math]\displaystyle{ 2m }[/math] 个小球，共m种颜色，每种颜色两个球，相同颜色的球不可区分。
取k个球，有多少种取法。
Problem 2
共有 [math]\displaystyle{ r\ge 5 }[/math] 种颜色。对于如下的图，有多少个对顶点的着色，使得任意相邻两点不共色。
Problem 3
[math]\displaystyle{ \phi(x_1,x_2,\ldots,x_n) }[/math] 为[math]\displaystyle{ n }[/math]个变量的[math]\displaystyle{ m }[/math]个子句 (clause) 的 conjunctive normal form (CNF) 逻辑表达式。
证明：对于任何如上的[math]\displaystyle{ \phi }[/math]，总存在一个[math]\displaystyle{ (x_1,x_2,\ldots,x_n)\in\{\text{true},\text{false}\}^n }[/math]的赋值，满足至少[math]\displaystyle{ \frac{m}{2} }[/math]个子句。
Problem 4
令[math]\displaystyle{ S_1,\ldots,S_m }[/math]一系列集合，满足
- 任何 [math]\displaystyle{ S_i }[/math] 有至少 [math]\displaystyle{ k }[/math] 个元素;
- 任何元素至多属于 [math]\displaystyle{ k }[/math] 个集合
证明：[math]\displaystyle{ S_1,\ldots,S_m }[/math] 有 system of distinct representatives (SDR)。
Problem 5
令 [math]\displaystyle{ \mathcal{F}\subseteq 2^{[n]} }[/math] 为一个antichain，即 [math]\displaystyle{ \forall S,T\in\mathcal{F}, S\not\subset T }[/math]。此外，[math]\displaystyle{ \forall S\in\mathcal{F}, |S|\le k }[/math]。
证明：[math]\displaystyle{ |\mathcal{F}|\le{n\choose k} }[/math]。
（使用课上教的某定理）