《组合数学》详解 Chapter 5 二项式系数

· · 个人记录

二项式，是形如 (a+b)^n 的式子。这种式子在 OI 中应用及其广泛，若带入一些特殊值之后会有更多优美的性质与公式。

首先，我们先来看一个在初中就了解过的东西——帕斯卡三角形（又称杨辉三角）。

5.1 帕斯卡三角形

在 2.3 节，我们定义了组合数 \dbinom{n}{r} ，同时还知道了关于它的基本性质 2.3.2

\dbinom{n}{r}=\dbinom{n}{n-r}

以及定理 2.3.3

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

分析这个式子，我们会发现，如果我们知道了所有 \dbinom{n-1}{i} ，就可以推导出每一个 \dbinom{n}{i} ，这种推导求解的过程很像 IO 中的一种算法—— DP 。其中定理 2.3.3 就是我们的 DP 关系式。但是我们还缺少 DP 的另一个要素——初始值。我们可以分析，对于第一层 DP ，即 n=1 时， \dbinom{1}{0}=\dbinom{1}{1}=1 。同时，对于所有的 n ，都有 \dbinom{n}{0}=\dbinom{n}{n}=1 ，这就是我们的初始状态。

所以我们可以用以下代码生成组合数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n;
int c[N][N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    return 0;
}

得到的结果如下：（第一行是 \dbinom{0}{0}）

1 1,1 1,2,1 1,3,3,1 1,4,6,4,1 \cdots

这就是我们熟知的帕斯卡三角形。

5.2 二项式定理

二项式，即形为 (x+y)^n 的形式的式子。当我们把这个式子展开时，会得到一个形如 a_0x^n+a_1x^{n-1}y^1+a_2x^{n-2}y^2+\cdots+a_{n}y^n 的式子。那我们如何求得系数 a 呢？

我们考虑其中的每一项都是如何形成的。对于其中的项 x^ky^{n-k} 的系数，我们可以看成是在一个有 n 个位置中选出 k 个位置是 x ，剩下的都为 y 。根据定理 2.3.1 ，它等于 \dbinom{n}{k} 。所以，我们可以得到：

定理 5.2.1

设 n \in N^* ，则对于所有的 x 和 y 都有

(x+y)^n=\sum\limits_{k=0}^{n} \dbinom{n}{k}x^ky^{n-k}

这个定理告诉了我们在二项式中某一项的系数，所以它也被称之为“二项式定理”。

同时，我们还经常见到一些特殊情况，比如 y=1 ：

定理 5.2.2

设 n \in N^* ，则对于所有的 x 都有

(x+1)^n=\sum\limits_{k=0}^{n} \dbinom{n}{k} x^k

接下来，我们来看一下关于二项式系数的一些性质。

首先，我们来考虑相邻的两个二项式系数 \dbinom{n}{k} 和 \dbinom{n-1}{k-1} 。很容易得到

\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}=\dfrac{n \times (n-1)!}{k \times (k-1)!(n-k)!}=\dfrac{n}{k} \dbinom{n-1}{k-1}

即

等式 (5.1)

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

第二个与我们在 Chapter 2 讲到的定理 2.3.4 有关。

\sum\limits_{i=0}^{n}\dbinom{n}{i}=2^n

而根据上面的二项式定理，将 x=1,y=-1 代入，会得到

\sum\limits_{i=0}^{n}(-1)^i\dbinom{n}{i}=0

两式加/减，我们可以得到

2(\dbinom{n}{0}+\dbinom{n}{2}+\cdots)=2^n 2(\dbinom{n}{1}+\dbinom{n}{3}+\cdots)=2^n

即

等式 (5.2)

\dbinom{n}{0}+\dbinom{n}{2}+\cdots=\dbinom{n}{1}+\dbinom{n}{3}+\cdots=2^{n-1}

我们将定理 2.3.4 两边乘上 (n+1)

\sum\limits_{k=0}^{n}(n+1)\dbinom{n}{k}=(n+1)2^n

用等式 (5.1)

(n+1)\dbinom{n}{k}=(k+1)\dbinom{n+1}{k+1}

替换，得到

\sum\limits_{k=1}^{n+1}(k+1)\dbinom{n+1}{k+1}=(n+1)2^n

再用 n 替换 n+1，k 替换 k+1，得到

等式 (5.3)

\sum\limits_{k=1}^{n}k\dbinom{n}{k}=n2^{n-1}

在原书上还有一种证明这个等式的方法。在此之前，我们需要先粗略地了解一下导数。

当然，即使你不会导数也没关系，在这里只需要记住两个公式：

对于定理 5.2.2

(x+1)^n=\sum\limits_{k=0}^{n} \dbinom{n}{k} x^k

两边求导，我们得到

等式 (5.4)

n(x+1)^{n-1}=\sum\limits_{k=1}^{n} \dbinom{n}{k} kx^{k-1}

将 x=1 代入

n2^{n-1}=\sum\limits_{k=1}^{n}k\dbinom{n}{k}

等式 (5.3) 得证。

不过到这里还没有结束，对于等式 (5.4) ，我们还可以做一些操作：

我们在等式两边乘 x

nx(x+1)^{n-1}=\sum\limits_{k=1}^{n} \dbinom{n}{k} kx^k

两边求导

n((x+1)^{n-1}+(n-1)x(x+1)^{n-2})=\sum\limits_{k=1}^{n} \dbinom{n}{k} k^2x^{k-1}

将 x=1 代入

n(2^{n-1}+(n-1)2^{n-2})=\sum\limits_{k=1}^{n} \dbinom{n}{k} k^2 n(n+1)2^{n-2}=\sum\limits_{k=1}^{n} \dbinom{n}{k} k^2

按照以上交替“乘 x — 求导”步骤，我们可以得到所有 p \in N^* 的 \sum\limits_{k=1}^{n} \dbinom{n}{k} k^p ，有兴趣的读者可以自己进行尝试。

在定理 2.3.4 的基础上，我们再进行加深，求各项系数平方和即

\sum\limits_{k=0}^{n}\dbinom{n}{k}^2

我们可以这样来计算：设一个有 2n 个元素的集合 S ，我们将 S 分成两个有 n 个元素的集合 A ， B ，对于每一个 \dbinom{n}{k}^2 ，我们可以把它转化成 \dbinom{n}{k}\dbinom{n}{n-k} ，把它看做是从 A 中选出 k 个元素，从 B 中选出 n-k 个元素的 n 子集的个数。那么 \sum\limits_{k=0}^{n}\dbinom{n}{k}^2 就是集合 S 的 n 子集个数即

等式 (5.5)

\sum\limits_{k=0}^{n}\dbinom{n}{k}^2=\dbinom{2n}{n}

根据上面的推导过程，我们可以扩展到更一般的情况。我们将集合 A 与 B 的元素个数变为 m_1 和 m_2 ，则可得到

等式 (5.6)

对于 0 \le n \le m_1+m_2 ，有

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

这个公式被称为范德蒙卷积公式。

还有两个与帕斯卡公式有关的式子。我们考虑对帕斯卡公式进行迭代。比如：对于

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

我们对右式的第一个再次使用帕斯卡公式分解

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

不断重复

\dbinom{n}{k}&=\dbinom{n-3}{k}+\dbinom{n-3}{k-1}+\dbinom{n-1}{k-2}+\dbinom{n-1}{k-1}\\ &=\dbinom{n-4}{k}+\dbinom{n-4}{k-1}+\dbinom{n-3}{k-1}+\dbinom{n-2}{k-1}+\dbinom{n-1}{k-1}\\ &\vdots\\ &=\dbinom{0}{k}+\dbinom{1}{k-1}+\cdots+\dbinom{n-2}{k-1}+\dbinom{n-1}{k-1}\\ \end{aligned}

用 n+1 代替 n ， k+1 代替 k ，得到

等式 (5.7)

\dbinom{n+1}{k+1}=\dbinom{1}{k}+\dbinom{2}{k}+\cdots+\dbinom{n-1}{k}+\dbinom{n}{k}

我们也可以对右式第二个迭代

\dbinom{n}{k}&=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\\ &=\dbinom{n-1}{k}+\dbinom{n-2}{k-1}+\dbinom{n-2}{k-2}\\ &\vdots\\ &=\dbinom{n-1}{k}+\dbinom{n-2}{k-1}+\cdots+\dbinom{n-k}{1}+\dbinom{n-k}{0}\\ \end{aligned}

用 n+k+1 代替 n ，得到

等式 (5.8)

\dbinom{n+k+1}{k}=\dbinom{n+k}{k}+\dbinom{n+k-1}{k-1}+\cdots+\dbinom{n+1}{1}+\dbinom{n+1}{0}

在本小节的最后，我们将会把二项式系数扩展到 n \in R,k \in Z 的范围上。

我们定义实数意义下的二项式系数为

\begin{cases} \dfrac{n(n-1)(n-2)\cdots(n-k+1)}{k!}&(k \gt 0)\\ 1&(k=0)\\ 0&(k\lt0)\\ \end{cases}

例子

\dbinom{\frac{5}{2}}{4}=\dfrac{\frac{5}{2}\frac{3}{2}\frac{1}{2}\frac{-1}{2}}{4!}=-\dfrac{5}{128} \dbinom{-8}{2}=\dfrac{(-8)(-9)}{2!}=36

5.3 二项式系数的单峰性

在 OI 中，我们已经知道单峰性的定义，即对于满足 0 \le t \le n 的整数 t ，如果

a_0 \le a_1 \le \cdots \le a_t \ge a_{t+1} \ge \cdots \ge a_n

则称序列 a 是单峰的。当然，这里的 t 可以有不止一个。

我们重新观察帕斯卡三角形会发现，三角形的每一行似乎也是单峰的，也就是序列 \dbinom{n}{0} , \dbinom{n}{1} , \cdots , \dbinom{n}{n-1} , \dbinom{n}{n} 是一个单峰序列。

对此，我们可以考虑此序列中相邻两项的商

\dfrac{\dbinom{n}{k}}{\dbinom{n}{k-1}}=\dfrac{\dfrac{n!}{k!(n-k)!}}{\dfrac{n!}{(k-1)!(n-k+1)!}}=\dfrac{n-k+1}{k}

所以，对于 k \lt n-k+1 ， k = n-k+1 ， k \gt n-k+1 分别有 \dbinom{n}{k-1} \lt \dbinom{n}{k} ， \dbinom{n}{k-1} = \dbinom{n}{k} ， \dbinom{n}{k-1} \gt \dbinom{n}{k}

于是我们得到

定理 5.3.1

设 n \in N^* ，二项式系数序列满足

\dbinom{n}{0} \lt \dbinom{n}{1} \lt \cdots \lt \dbinom{n}{\frac{n}{2}-1} \lt \dbinom{n}{\frac{n}{2}} \gt \dbinom{n}{\frac{n}{2}+1} \gt \cdots \gt \dbinom{n}{n} \dbinom{n}{0} \lt \dbinom{n}{1} \lt \cdots \lt \dbinom{n}{\frac{n-1}{2}} = \dbinom{n}{\frac{n+1}{2}} \gt \cdots \gt \dbinom{n}{n}

以及一个很简单的推论

推论 5.3.2

设 n \in N^* ，二项式系数序列中最大值为

\dbinom{n}{\lfloor\frac{n}{2}\rfloor}=\dbinom{n}{\lceil\frac{n}{2}\rceil}

在原书的这一小节最后有一个关于反链的定理—— Sperner 定理，我们将其放到 5.6 节一起研究。

5.4 多项式定理

在 5.2 节，我们讲到了二项式定理，现在，我们要将其推导到更一般的形式，即求出 (x_1+x_2+\cdots+x_k)^n 中 {x_1}^{n_1} {x_2}^{n_2} \cdots {x_k}^{n_k} （满足 n_1+n_2+\cdots+n_k=n ） 的系数，我们将其记作 \dbinom{n}{n_1 \, n_2 \, \cdots \, n_k}。

我们假设，现在有 n 个篮子，我们手上有 n_1 个物品 x_1 ， n_2 个物品 x_2 ， \cdots ， n_k 个物品 x_k ，我们需要考虑的就是将这些物品放入篮子中。我们尝试构造一个长度为 n 的序列，其中序列的第 i 项的元素表示第 i 个篮子中放入的元素，也就是说，我们需要找到满足上面元素个数的排列个数。而这个数我们在定理 2.4.2 中已经计算过，为 \dfrac{n!}{n_1! n_2! \cdots n_k!} 。

这样，我们就得到了

定理 5.4.1

设 n \in N^* ，有

(x_1+x_2+\cdots+x_k)^n=\sum \limits_{n_1+n_2+\cdots+n_k=n} \dbinom{n}{n_1 \, n_2 \, \cdots \, n_k} {x_1}^{n_1} {x_2}^{n_2} \cdots {x_k}^{n_k}

这小节好短啊

5.5 牛顿二项式定理

在 5.2 中，我们聊到了二项式定理即

(x+y)^n=\sum\limits_{k=0}^{n} \dbinom{n}{k}x^ky^{n-k}

而实际上，我们可以理解它为

(x+y)^n=\sum\limits_{k=0}^{\infty} \dbinom{n}{k}x^ky^{n-k}

不过在 k>n 时 \dbinom{n}{k}=0 。

在这个小节，我们将二项式定理扩展到任意实数

定理 5.5.1

设 \alpha \in R ，则对于所有满足 0 \le |x| \lt |y| 的 x 和 y 都有

(x+y)^\alpha = \sum \limits_{k=0}^{\infty} \dbinom{\alpha}{k}x^{k}y^{\alpha-k}

这里的 \dbinom{\alpha}{k} 是我们在 5.2 中定义过的实数意义下的二项式系数即

\begin{cases} \dfrac{n(n-1)(n-2)\cdots(n-k+1)}{k!}&(k \gt 0)\\ 1&(k=0)\\ 0&(k\lt0)\\ \end{cases}

然而，这个定理在书中并没有详细证明，因为大多数时候，上述的式子会有无限项，这还得涉及到无穷级数的收敛性等问题，要解决此问题需要高等数学知识，笔者尚未掌握，故不详细阐述。

不过，我们还是可以讨论这个式子的一些特殊情况。

设 z=x/y ，则有

(x+y)^{\alpha} = (yz+y)^{\alpha} = y^{\alpha}(1+z)^{\alpha}

所以我们可以将

(x+y)^\alpha = \sum \limits_{k=0}^{\infty} \dbinom{\alpha}{k}x^{k}y^{\alpha-k}

转化为

y^{\alpha}(1+z)^{\alpha} = \sum \limits_{k=0}^{\infty} \dbinom{\alpha}{k}x^{k}y^{\alpha-k} (1+z)^{\alpha} = \sum \limits_{k=0}^{\infty} \dbinom{\alpha}{k}\dfrac{x^{k}y^{\alpha-k}}{y^{\alpha}} (1+z)^{\alpha} = \sum \limits_{k=0}^{\infty} \dbinom{\alpha}{k}\dfrac{x^{k}}{y^k}

等式 (5.9)

(1+z)^{\alpha} = \sum \limits_{k=0}^{\infty} \dbinom{\alpha}{k}z^k

当然，由于 z=x/y ，所以这个式子只对于满足 |z| \lt 1 的 z 成立。

但是，我们会发现这个式子中依旧存在一个不太好处理的东西，那就是二项式系数，所以我们考虑：

设 n \in N^{*} ，将 -n 带入等式 (5.9) 的 \alpha ，则此时

\dbinom{\alpha}{k}=\dbinom{-n}{k} &=\dfrac{(-n)(-n-1)\cdots(-n-k+1)}{k!}\\ &=(-1)^k\dfrac{n(n+1)\cdots(n+k-1)}{k!}\\ &=(-1)^k\dbinom{n+k-1}{k}\\ \end{aligned}

所以有

(1+z)^{-n} = \sum \limits_{k=0}^{\infty} (-1)^k\dbinom{n+k-1}{k}z^k

即

\dfrac{1}{(1+z)^n} = \sum \limits_{k=0}^{\infty} (-1)^k\dbinom{n+k-1}{k}z^k

对于这个式子，我们会发现，当 n=1 时，\dbinom{n+k-1}{k}=\dbinom{k}{k}=1 ，所以有

等式 (5.10)

\dfrac{1}{1+z} = \sum \limits_{k=0}^{\infty} (-1)^kz^k

再用 -z 代替 z

等式 (5.11)

z^k

在第 7 章里，我们将会就生成函数继续拓展二项式定理。

5.6 偏序集

在原书中，偏序集内容的前半段属于 5.3 ，笔者为了方便在这一小节中统一讲解。

首先，我们先来了解偏序关系和偏序集。

偏序关系通俗地来说就是一种二元的比较关系，不过这种比较关系不需要对于任意的两个数都可比。例如 \le 就是一种偏序，而 \mid （整除）也是一种偏序。如果 a 和 b 满足 a \mid b ，那么我们就说 a 和 b 满足 \mid 的偏序关系。而如果 a \nmid b ，则 a 和 b 不满足此偏序关系。

我们形式定义偏序关系为：

假设此关系为 \le ，这此关系满足

同时，我们根据其满足

或

将偏序关系分为非严格偏序（满足自反性）和严格偏序（满足反自反性）（或者称为自反偏序和反自反偏序）。我们一般用 \le 表示非严格偏序， \lt 表示严格偏序。同时用 \ge 和 \gt 表示它们的逆关系。我们通常所说的偏序关系一般指非严格偏序。

而偏序集则指的是一个具有偏序关系的集合。在这个集合中，我们用一个偏序关系来比较集合中的元素的大小。我们通常用 (S,\le) 来表示一个偏序集，其中， S 是这个偏序集的元素的集合， \le 是这个偏序集的偏序关系。

在一个偏序集中，我们定义集合 A 是 (S, \le ) 的一条链满足

或者通俗地说，一条有 n 个元素的链满足存在一种排列元素的方式使得 a_1 \le a_2 \le \cdots \le a_n 。

同样，我们可以定义链的反概念反链 A 为

例如，设 S = \{x \mid x \in N^* , x \in [1,10]\} ，则偏序集 (S, \le ) 中，最长链其中之一为 \{1,2,4,8\} ，最长反链其中之一为 \{4,5,6,7,9\} 。

根据定义，不难得出链与反链之间的性质：

这个性质也很明显，因为如果存在两个元素 a 和 b 同时在链和反链中，则由定义可知 a \le b 且 a \lneq b ，显然矛盾，故得证。

接下来，我们将会证明一个偏序集中链与反链之间的一些关系。我们先给出这两个定理

定理 5.6.1

设 (S, \le ) 是有限偏序集， r 是链的最大大小，则 S 可被划分成 r 条反链，但不能划分成少于 r 条反链。

以及

定理 5.6.2

设 (S, \le ) 是有限偏序集， r 是反链的最大大小，则 S 可被划分成 r 条链，但不能划分成少于 r 条链。

这两个定理十分对称。

（证明暂咕）

5.7 练习题

part 1 简单的二项式定理应用

T8

用二项式定理证明

2^n=\sum \limits_{k=0}^{n} (-1)^{k}\dbinom{n}{k}3^{n-k}

证：

\sum \limits_{k=0}^{n} (-1)^{k}\dbinom{n}{k}3^{n-k} &=\sum \limits_{k=0}^{n} \dbinom{n}{k}(-1)^{k}3^{n-k}\\ &=(3+(-1))^n=2^n\quad(5.2.1) \end{aligned}

end.

T9

求和

\sum \limits_{k=0}^{n}(-1)^{k}\dbinom{n}{k}10^{k}

解：

\sum \limits_{k=0}^{n}(-1)^{k}\dbinom{n}{k}10^{k} &=\dfrac{1}{(-1)^{2k-n}}\sum \limits_{k=0}^{n}(-1)^{n-k}\dbinom{n}{k}10^{k}\\ &=\dfrac{(-1)^n}{(-1)^{2k}}(10-1)^{n}\\ \end{aligned}

由于 (-1)^{2k}=1 ，所以

\sum \limits_{k=0}^{n}(-1)^{k}\dbinom{n}{k}10^{k}=(-1)^{n}9^{n}

end.

part 2 组合推理证明

T11

用组合推理证明

\dbinom{n}{k}-\dbinom{n-3}{k}=\dbinom{n-1}{k-1}+\dbinom{n-2}{k-1}+\dbinom{n-3}{k-1}

证：

设集合 S 满足 |S|=n 且存在三个互不相同的元素 a,b,c 有 a \in S ，b \in S ，c \in S 。

易证。 end. **T13** （未完）