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

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}$
得证。