浅谈二项式系数与偏序集

· · 个人记录

《组合数学》Chapter 5笔记。

  1. 该公式在一些二项式暴力展开（比如愤怒的小N中的 60 部分分）题目里常见
(x+1)^n=\sum_{k=0}^n \dbinom{n}{k}x^k

同时这启发我们，对于形如 \dbinom{n}{0}\pm\dbinom{n}{1}\pm\dbinom{n}{2}+...+\dbinom{n}{n} ，一般来说符号是正负交错的。可以构造一个二项式的展开使得 x^ky^{n-k} 项约成一个固定常数而保留下二项式系数。最经典的固定常数就是 1. 一个应用是利用它说明 n 集合 S 的偶子集数目等于奇子集数目。即：

(1-1)^n=\dbinom{n}{0}-\dbinom{n}{1}+...+(-1)^n\dbinom{n}{n}=0
  1. 关于帕斯卡三角形上的行之和问题：

一次：

\sum_{k=0}^n\dbinom{n}{k}=2^{n}

二次：

\sum_{k=0}^n\dbinom{n}{k}^2=\dbinom{2n}{n}

对于二次的形式，我们有更一般的范德蒙德卷积。即若 m_1,m_2,n 为正整数，则有：

\sum_{k=0}^n\dbinom{m_1}{k}\dbinom{m_2}{n-k}=\dbinom{m_1+m_2}{n}

用组合意义对其证明。把 |S|=m_1+m_2 划分成集合 |A|=m_1 和 |B|=m_2.那么 S 中选 n 个的方案数等价于现在 A 中选 k 个，再在 B 中选 n-k 个的方案数之积，k的取值 是不超过 n 的任意非负整数。

3.系数固定和非固定的二项式系数转换。

这里的系数是指二项式系数前还带有乘数。由下面的等式可以让“系数”成为一个固定值。

k\dbinom{n}{k}=n\dbinom{n-1}{k-1}

由此得到的推论是：

\sum_{i=1}^ni\dbinom{n}{i}=n2^{n-1}
  1. 子集大小固定的情况

这里指多个二项式系数 \dbinom{n}{k} 其中 k 固定的情况。

有趣的是，下面的等式直接由递推公式 \dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1} 就能推出

\dbinom{n+1}{k+1}=\sum_{i=0}^n\dbinom{i}{k}

原集合大小（指 n）和子集大小（指 k）固定的时候可以体现在帕斯卡三角的行 / 列上。这个等式告诉我们，帕斯卡三角上第 n 行 k 列的值等于第 k-1 列上的 n-1 前缀和。

  1. 二项式系数的单峰性

显然对于 n 是定值的二项式系数 \dbinom{n}{k}。当 n 为偶数时 k=\frac{n}{2}，为奇数是 k=\frac{n-1}{2} 或 \frac{n+1}{2} 时 \dbinom{n}{k} 取到最大值。

  1. 补充（来自其它地方）：

考虑这样一个式子：

\sum_{k=0}^n \dbinom{n}{k}\dbinom{k}{j}=2^{n-j}\dbinom{n}{j}

从组合意义上对其证明：考虑到左半部分，容易视作从 n 个元素里选取 k 个，再从里面选取 j 个。那不妨直接改成从 n 个里选取 j 个，即 \dbinom{n}{j}。但这会减少计数，因为第一步选的 k 子集有多种情况是可以包含同一个子集的，比如 \{1,2,3,4,5\} 中，选 \{3,4\} 或者 \{3,4,5\} 都可以包含 \{3\}。考虑对于一个 j 子集，包含它的集合有 2^{n-j} 个，乘上即可。

  1. 集合 X 上的关系 R
$\forall x \in X,xRx$ 不成立，则 $R$ 是**反自反**的 $\forall x,y \in X,xRy$，满足 $yRx$，则称 $R$ 是**对称的** $\forall x,y \in X,xRy$，满足 $y\not Rx$，则称 $R$ 是**反对称**的 $\forall x,y,z \in X,xRy,yRz$，满足 $xRz$，则称 $R$ 是**传递**的 **偏序关系**意味着自反，反对称与传递，代表关系是 $\le$，严格偏序关系意味着反自反，反对称与传递，代表关系是 $\lt$。等价关系意味着自反，对称与传递，代表关系是 $=$. 通常地，我们用上述三种代表关系代表这三种关系。所以这里这三种关系的意义都发生了变化。不再是单纯的数值比较。 2. 偏序集，链，最小元 偏序集 $(X,\le)$ 是一个定义了某种偏序关系的集合。$\forall x,y \in X$，它们可能可以比较，也可能不可比。 **链** $C \subseteq X$ 满足 $\forall x,y \in C$，都有 $x \le y$ 或者 $y \le x$，换言之，$x,y$ 是可比的。这样的最大的一个 $C$ 称作偏序集的最长链。 **反链** $A \subseteq X $ 满足 $\forall x,y \in C$，$x,y$ 都不可比。这样的最大的一个 $A$ 称作偏序集的最长反链。最长反链 $A$ 的一个显然性质是，$\forall x \in A,y\in \overline{A}$，$x,y$ 可比。 **最小元**是指这样一个元素 $a \in X$，满足 $\forall b \in X,a \leq b$.类似地有最大元的定义。 3.偏序集和 DAG 的关系 OI 中最常见的偏序集就是 DAG。经典的两个偏序集题目 导弹拦截 和 祭祀 都可以抽象在 DAG 上。定义偏序关系 $x\leq y$ 代表在 DAG $G=(V,E)$ 上 $x$ 可以走到 $y$，则 $(V,\leq)$ 是一个偏序集。 同时，对于 $\forall x,y \in X,x \neq y$，若 $x \leq y$，则我们连有向边 $(x,y)$，那么这张图一定是一个 DAG. 4. Dilworth定理 **狄尔沃斯定理**： 偏序集最长反链 = 最小链覆盖 其对偶定理： 偏序集最长链 = 最小反链覆盖 让我们先解释一下链覆盖的意思。就是把偏序集分成若干个链。使得每个元素都恰好属于一条链。划分出来的链最少的方案就是一个最小链覆盖。同理定义了最小反链覆盖（通常链与反链都是对偶相关的）。 首先注意到最小链覆盖 $>=$ 最长反链，同理最小反链覆盖 $>=$ 最长链。这是由一个基本事实保证的： 偏序集的一个链 $C$ 和一个反链 $A$ 的交最多只有一个元素。所以对于一条反链，它的任意两个元素不能划分进同一条链中。同理对于一条链，它的任意两个元素不能划分进同一条反链中。 证明对偶定理是比较简单的，令 $m$ 为最长链长度： 对抽象出来的 DAG 进行拓扑排序，每次选出无入度点，全部取出，形成一个反链。去掉这些点，重复这些过程。那么反链个数显然等于 DAG 最长链（即偏序集最长链）。 形式化的证明： 如果我们依次进行 $p$ 次操作，每次取出当前 $A$ 中所有最小元构成 $A_i$，然后去掉，$p$ 次后 $A$ 成为空集。那么 $A$ 被划分成了： $$A_1,A_2,...A_p$$ 这 $p$ 个反链。注意到从每个 $A_i$ 中各取一个元素并起来，会出现一条反链，那么 $p<=m$，否则与最长链定义矛盾。而我们又知道 $p>=m$，所以 $p=m$，我们就构造出来一种把偏序集划分成 $m$ 条反链的方案。（注意到其本质上还是拓扑排序） 然后证明定理本身，通过归纳法解决，$n=1$ 是很显然成立的。现在假设 $n>1$. 如果存在一个最长反链 $A$ 既不是所有最小元的集合也不是所有最大元的集合。那么设 $A^+$ 是 $\{x:x \in a, \exists a \in A,a<=x \}$，$A^-$ 是 $\{x:x \in a ,\exists a \in A,x<=a\}$.那么： $A^+ \cap A^-=A A^+ \cup A^- = X

对于 A^+ 可以构造 m 条链 E_1,E_2,...E_m. 每一条都以一个 A 中元素作为链头。对于 A^- 可以构造 m 条链 F_1,F_2,...F_m. 每一条都以 A 中一个元素作链尾。那么一一配对就把 X 划分成了 m 条链。

如果最小元或者最大元数量 =m，我们找出任意一个最小元 x 和最大元 y，显然 x<=y 是一条链。必要的时候 x,y 可以退化成一个元素。显然此时 X 去掉 \{x,y\} 后的集合最长反链是 m-1，加上我们构造的这条反链，也能划分成 m 条反链。

证毕。

Dilworth学会以后，我们就可以乱杀【NOIP1999】导弹拦截和 【CTSC2008】祭祀了（似乎第二个题在构造方案上还另外有点毒瘤）