一、二项式定理与二项式系数

1.1 二项式定理

定理 1（二项式定理） 设 \(n\) 是正整数。对所有的 \(x\) 和 \(y\)，有 \[ (x+y)^n=\sum\limits_{k=0}^n\binom nk x^{n-k}y^k\tag 1 \]

证明考虑把 \((x+y)^n\) 展开，结果有 \(2^n\) 项，每一项都可以写成 \(x^{n-k}y^k\) 的形式。对于每个形式，相当于在 \(n\) 个因子中选择 \(k\) 个选择 \(x\)，故其系数为 \(\binom n k\)。

1.2 组合相关推论

如果对于二项式定理，取 \(y=1\)，则有如下特殊形式。

定理 2 设 \(n\) 为正整数。对于所有的 \(x\)，有 \[ (1+x)^n=\sum\limits_{k=0}^n \binom n k x^k\tag{2} \] 证明略去。

定理 3 对于正整数 \(n,k\)，有 \[ k\binom n k =n\binom {n-1}{k-1}\tag{3} \]

证明如果 \(k>n\)，则 \(\binom n k=0\)。否则，有 \[ k\binom n k =\dfrac{n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}\times k=\dfrac{n(n-1)\cdots (n-k+1)}{(k-1)(k-2)\cdots 1} \] 而又有 \[ n\binom {n-1}{k-1}=\dfrac{(n-1)(n-2)\cdots (n-k+1)}{(k-1)(k-2)\cdots 1}\times n=\dfrac{n(n-1)\cdots (n-k+1)}{(k-1)(k-2)\cdots 1}=k\binom n k \] 得证。

显然根据组合意义，有 \[ \sum\limits_{k=0}^n\binom n k=2^n\tag{4} \] 下面给出另一有关定理。

定理 4 对于正整数 \(n>1\)，有如下二式成立 \[ \begin{aligned} \binom n 0 +\binom n 2 +\binom n 4 + \cdots &= 2^{n-1} \\ \binom n 1 +\binom n 3 +\binom n 5 + \cdots &= 2^{n-1} \end{aligned} \tag{5} \]

证明对于二项式定理 \(\sum\limits_{k=0}^n\binom n k x^{n-k}y^k\)，取 \(x=1,y=-1\) 时可以得到 \[ \binom n 0 -\binom n 1+\binom n 2-\cdots +(-1)^n\binom n n =0 \] 移项可得 \[ \binom n 0+\binom n 2+\cdots =\binom n 1+\binom n 3+\cdots\ \] 根据 \((4)\) 式可以得到上式左右两边加和为 \(2^n\)，故可知左右两边分别等于 \(2^{n-1}\)。

得证。

定理 5 对于任意正整数 \(n\)，有 \[ nx(1+x)^{n-1}=\sum\limits_{k=1}^n k\binom n k x^k\tag 6 \]

证明对 \((2)\) 式两边关于 \(x\) 求导，得到 \[ n(1+x)^{n-1}=\sum\limits_{k=1}^nk\binom n k x^{k-1} \] 两边同乘 \(x\) 即可得证。

对于上述定理还有一个特殊形式，当 \(x=1\) 时，有 \[ n2^{n-1}=\sum\limits_{k=1}^nk\binom nk \tag 7 \] 如果对上述定理再同时关于 \(x\) 求导，可以得到 \[ n(n+1)2^{n-2}=\sum\limits_{k=1}^n k^2\binom nk\tag 8 \] 定理 6 关于帕斯卡三角形各行上的数字的平方和，有如下等式 \[ \sum\limits_{k=0}^n \binom nk^2=\binom {2n} n\tag 9 \]

证明设 \(S\) 为一个大小为 \(2n\) 的集合，将其分为 \(A,B\) 两个大小均为 \(n\) 的不交集合。考虑选出 \(S\) 的每一个 \(n\) 子集，设其中元素在 \(A\) 集合中的有 \(k\) 个，则在 \(B\) 集合中的有 \(n-k\) 个，其中 \(0\le k\le n\)。

按照 \(k\) 的大小建立 \(k+1\) 个集合 \(\mathscr{C}_k\)，表示由包含 \(k\) 个 \(A\) 集合中的元素与 \(n-k\) 个 \(B\) 集合组成的 \(n\) 子集的集合。显然有 \[ \binom {2n} n=\sum\limits_{i=0}^n | \mathscr C_i| \] 考虑每一个 \(\mathscr C_i\) 的元素个数，其中每个 \(n\) 子集包含的 \(k\) 个 \(A\) 中元素有 \(\binom n k\) 种，\(B\) 中元素有 \(\binom n {n-k}\) 中，故有 \[ \sum\limits_{i=0}^n |\mathscr C_i|=\sum\limits_{i=0}^n \binom n k\binom n {n-k}=\sum\limits _{i=0}^n \binom n k^2=\binom {2n} n \] 得证。

定理 7 对于正整数 \(n,k\)，有 \[ \binom {n+1}{k+1}=\sum\limits_{i=0}^n\binom i k \]

证明对于二项式 \(\binom n k\) 不断应用基本公式 \(\binom n k=\binom {n-1} k+\binom {n-1}{k-1}\)，可以得到 \[ \binom nk=\binom 0k+\binom 0{k-1}+\cdots +\binom {n-2}{k-1}+\binom {n-1}{k-1} \] 根据 \(\binom 0k=0\) 消去该项，并用 \(n+1\) 取代 \(n\)，用 \(k+1\) 取代 \(k\) 得证。

1.3 二项式系数的单峰性

通过考察帕斯卡三角的某一行，不难发现单峰性 \[ \binom n1<\binom n2<\cdots <\binom nt,\binom nt>\binom n{t+1}>\cdots>\binom nn \] 当 \(n\) 为奇数时，最大值点 \(t=\lfloor\dfrac n2\rfloor\)。

当 \(n\) 为偶数时，有两个最大值点 \(\dfrac n2\) 和 \(\dfrac n2+1\)。

1.4 Sperner 定理

对于一个 \(n\) 元素集合 \(S\)，定义 \(S\) 的子集的集合 \(\mathscr C\) 是一条链，当且仅当对于 \(\mathscr C\) 的每一对子集，总有包含与被包含关系。

定义 \(S\) 的一条最大链为元素个数最多的子集集合 \(\mathscr C\)。

定义 \(S\) 的子集的集合 \(\mathscr C\) 是一条反链，当且仅当 \(\mathscr C\) 的每对元素都没有包含与被包含关系。

定理 8（Sperner 定理） 设 \(S\) 为 \(n\) 元素集合，则 \(S\) 的一个反链上至多包含 \(\dbinom n{\lfloor\frac n2\rfloor}\) 个集合。

证明考虑什么样的集合 \(\mathscr C\) 会成为最大链。不难发现，当形如 \(\mathscr C=\{\{a_1\},\{a_1,a_2\},\cdots,\{a_1,a_2,\cdots a_n\}\}\) 的时候会成为最大链，最大链长度为 \(n\)，其中 \(a_1,a_2\cdots a_n\) 为一个 \(1\sim n\) 的排列，最大链个数为 \(n!\)。

当我们考虑一个 \(S\) 的子集 \(A\) 的时候，固定 \(|A|=k\) 时，发现包含集合 \(A\) 的最大链的个数为 \[ k!(n-k)! \] 在构成的最大链中，其中有 \(k!\) 个是包含于 \(A\) 的集合数目，\((n-k)!\) 是包含 \(A\) 的集合数目。

同时不难发现：每条链至多能包含任意一个反链的一个成员，反证不难。

现在要求反链的最大长度，根据上述引理，可以唯一转化为求包含反链成员的不同最大链长度。

设 \(\mathscr A\) 是反链，\(A\) 是反链中的一个元素，\(\mathscr C\) 是包含 \(A\) 的最大链。设 \(\beta=|\mathscr A|\) 同时等于合法的最大链 \(\mathscr C\) 的个数。根据上述论证，有 \(\beta\le n!\)。如果 \(|A|=k\)，则有 \(k!(n-k)!\) 个包含 \(A\) 的最大链 \(\mathscr C\)。

设 \(\alpha _k\) 是反链 \(\mathscr A\) 中大小为 \(k\) 的元素个数，有 \(|\mathscr A|=\sum\limits_{k=0}^n \alpha_k\)，于是 \[ \beta=\sum\limits_{k=0}^n \alpha_k k!(n-k)!\le n! \] 通过化简得到 \[ \sum\limits_{k=0}^n\dfrac{\alpha_k}{\dbinom nk}\le 1 \] 根据二项式系数的单峰性，当 \(k=\lfloor \dfrac n2 \rfloor\) 的时候 \(\dbinom nk\) 最大，于是有 \[ |\mathscr A|\le \sum\limits_{k=0}^n\alpha _k\le \binom n {\lfloor \dfrac n2 \rfloor} \] 得证。