Combinatorics (Fall 2010)/Problem set 6

Problem 1

[math]\displaystyle{ 2m }[/math] 个小球，共m种颜色，每种颜色两个球，相同颜色的球不可区分。

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

Problem 2

[math]\displaystyle{ [n] }[/math] 的排列 [math]\displaystyle{ \pi }[/math] 的一个不动点是满足 [math]\displaystyle{ \pi(i)=i }[/math] 的[math]\displaystyle{ i }[/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]。

（使用课上教的某定理）