4.1 二项式系数与展开

先计数，再展开

二项式定理常被记成公式，但公式背后其实是计数。展开 $(x+y)^n$ 时，每个乘积都来自于在 $n$ 个括号中各选一个 $x$ 或 $y$。不同的选择可以产生同一个单项式，而它的系数正是产生这个单项式的选法数。因此，必须区分乘法过程中得到的乘积与合并同类项后留下的项。

核心问题是：有多少种方法可以选出提供 $y$ 的括号？这些括号的位置很重要，但列举这些位置时的先后次序并不重要。阶乘、排列与组合使这个区别变得精确，也说明了为什么二项式系数是整数，以及为什么寻找一个系数时不必写出整个展开式。

阶乘、排列、组合

定义

阶乘

对正整数 $n$，

$$n! = n(n-1)(n-2)\cdots 2\cdot 1.$$

约定 $0! = 1$。

把 $n$ 个不同对象不重复地排成一列，第一位置有 $n$ 种选择，第二位置剩下 $n-1$ 种，依此类推。把各步的选择数相乘，就得到阶乘。这是逐步计数的乘法原理：每个已经完成的部分排列，都有相同数目的下一步选择。零的阶乘取一，对应唯一的空排列，而不是没有排列。

定义

排列

设 $n,k$ 为整数且 $0 ≤ k ≤ n$。从 $n$ 个不同对象中不重复地取出 $k$ 个，并排成有次序的一列，称为一个 $k$-排列。其数量为

$$P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$

当 $k=0$ 时，乘积没有因子，称为空积，其值为 $1$。

乘积中恰好有 $k$ 个因子：最后一步已经用去 $k-1$ 个对象，所以还剩 $n-(k-1)=n-k+1$ 种选择。阶乘的商只是约去从 $n-k$ 到 $1$ 的未用因子，并没有增加一次选择。特别地，$P(n,n)=n!$ 计算全部对象的排列，而 $P(n,0)=1$ 计算唯一的空有序选择。

无序选择只说明选中了哪些对象；有序选择还要说明它们的位置；排列一个已经选定的集合，则只决定内部次序。例如，从字母 $A,B,C,D,E$ 中依次选出三个不同字母，共有 $P(5,3)=5\cdot4\cdot3=60$ 个结果。序列 $A,B,C$ 与 $C,B,A$ 是不同的有序结果，却对应同一个三元素集合。使用计数公式前，应先判断题目是否区分这样的两个结果。

定义

二项式系数

对满足 $0 ≤ k ≤ n$ 的整数 $n,k$，定义

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$

它计算一个 $n$ 元素集合的 $k$ 元素子集数，也称为 $k$-组合数。记号 $C(n,k)$ 表示同一个数。

每个固定的 $k$ 元素选择，都恰好有 $k!$ 种内部排列。因此，可以把有序选择分成大小相同的组：包含相同对象的有序选择属于同一组。按组计数得到

$$P(n,k)=\binom{n}{k}k!, \qquad \binom{n}{k}=\frac{P(n,k)}{k!}.$$

这既解释了为什么要除以阶乘，也说明所得的商一定是整数。在五个字母的例子中，每组有 $3!=6$ 种次序，所以无序选择共有 $60/6=10$ 种。这里能除以同一个数，是因为对象互不相同，每个选择都有同样多的内部次序。组合数已经消去了这些次序，不能再重复除一次。

例题

带限制的座位安排

有 $m$ 个不同的女生与 $n$ 个不同的男生排成一列，假设 $m\gt n$，且不允许两个男生相邻。我们区分每个人，因此交换两个女生或两个男生都会得到不同的座位安排。

先排列女生，共有 $m!$ 种方法。对每个固定的女生次序，都有 $m+1$ 个空隙：最前面一个，相邻女生之间各一个，最后面一个。每个空隙最多放一个男生；若同一空隙放入两个男生，他们就会相邻。

先从这些空隙中选出 $n$ 个，共有 $\binom{m+1}{n}$ 种选法；再把 $n$ 个男生安排到选定的空隙中，共有 $n!$ 种方法。空隙本身已有从左到右的次序，需要安排的是男生。因此，

$$\binom{m+1}{n}n!=P(m+1,n)=\frac{(m+1)!}{(m+1-n)!}.$$

再乘以女生的排列数，得到

$$m!\binom{m+1}{n}n!=m!P(m+1,n) =m!\frac{(m+1)!}{(m+1-n)!}.$$

这个过程没有重复计数：每个最终座位安排都唯一决定女生次序、被占用的空隙，以及各空隙中的男生；反过来，每组这样的选择都会给出合法安排。原假设 $m\gt n$ 保证空隙足够，但同一论证实际上适用于满足 $n ≤ m+1$ 的非负整数。当 $m=0$ 时，把空的一列视为一个空隙。当 $n=m+1$ 时，所有空隙都被占用；当 $n\gt m+1$ 时，不可能避免男生相邻，答案为零，此时不能套用上面的阶乘商。

Pascal 恒等式

定理

基本二项式系数恒等式

设 $n$ 为非负整数。对满足 $0 ≤ k ≤ n$ 的整数 $k$，

$$\binom{n}{0}=\binom{n}{n}=1, \qquad \binom{n}{k}=\binom{n}{n-k}.$$

对满足 $0 ≤ k ≤ n-1$ 的整数 $k$，

$$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.$$

空子集只有一个，包含全部对象的子集也只有一个，所以两端的系数都是一。这也包括原集合为空时的 $\binom00=1$。对称性则来自取补集：每个选中的 $k$ 元素子集，都唯一对应未选中的 $n-k$ 元素子集；再取一次补集，就返回原来的选择。因此两种选择的数目相同。在阶乘公式中，这个对称性表现为分母中两个因子的交换。

最后一条是 Pascal 恒等式。上标增加一，是因为可供选择的对象增加了一个。要数 $n+1$ 个不同对象的 $k+1$ 元素子集，可先指定其中一个对象，再分成两种情况。包含指定对象的子集，还须从其余 $n$ 个中选 $k$ 个，有 $\binom nk$ 个；不包含指定对象的子集，则须从其余对象中选齐 $k+1$ 个，有 $\binom n{k+1}$ 个。这两类互不重叠，又覆盖所有可能，因此计数相加。指标范围保证两种选择都在上述阶乘定义的范围内。

证明

Pascal 恒等式的代数证明

对满足 $0 ≤ k ≤ n-1$ 的整数 $k$，计算

$$\binom{n}{k}+\binom{n}{k+1} =\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}.$$

取公分母 $(k+1)!(n-k)!$。第一项的分子须乘 $k+1$，第二项的分子须乘 $n-k$，所以分子之和为

$$n!(k+1)+n!(n-k)=n!(n+1).$$

因此

$$\binom{n}{k}+\binom{n}{k+1} =\frac{(n+1)!}{(k+1)!(n-k)!} =\binom{n+1}{k+1}.$$

最后一个阶乘的指标正确，因为 $(n+1)-(k+1)=n-k$。核对这个差，可以避免最后写出的上下标相差一位。

Pascal 三角形从第零行开始，把 $\binom nk$ 放在第 $n$ 行，$k$ 从零到 $n$。前五行为

$$\begin{array}{c} 1\\ 1\quad1\\ 1\quad2\quad1\\ 1\quad3\quad3\quad1\\ 1\quad4\quad6\quad4\quad1 \end{array}$$

每行的首尾都是一，每个内部数字等于上方相邻两个数字之和；补集对称性还使每行左右对称。这些规律都由计数恒等式解释，不需要把它们当成互不相关的口诀。

例题

格点路径

若每一步只能向右或向上走一格，从 $(0,0)$ 到 $(5,3)$ 有多少条路径？

每条路径都需要 $8$ 步，其中 $5$ 步向右、$3$ 步向上。选出八个位置中哪五个是向右的步，剩下的步就全部确定，从而整条路径也确定。反过来，每个这样的选择都会到达目标。因此路径数是

$$\binom{8}{5}=\binom{8}{3}=56.$$

这里不再乘 $5!$ 或 $3!$：向右的步没有各自的标签，交换两步向右的移动，不会改变路径。一般地，到达 $(k,n-k)$ 的路径数为 $\binom nk$。

这也给出 Pascal 恒等式的几何解释。到达 $(k+1,n-k)$ 的路径，最后一步要么从 $(k,n-k)$ 向右走，要么从 $(k+1,n-k-1)$ 向上走。按最后一步分类计数，便得到 $\binom nk+\binom n{k+1}=\binom{n+1}{k+1}$，其中 $0 ≤ k ≤ n-1$。

二项式定理

定理

二项式定理

对每个正整数 $n$，

$$(x+y)^n=\sum_{k=0}^n \binom{n}{k}x^{n-k}y^k.$$

概念视角组合

一个子集对应展开中的一组选择

设 $n\ge1$、$0\le k\le n$ 为整数，并把 $x,y$ 视为可交换的变量。 给 $(x+y)^n$ 的 $n$ 个因子标上 $1,\ldots,n$。

选择观点。 标签的 $k$ 元素子集 $S$ 恰好指定哪些因子提供 $y$，其余因子均提供 $x$。 改变列举 $S$ 中元素的次序不会改变选择，所以计数为 $\binom nk$，无需再乘 $k!$。

代数观点。 分配律让每组选择贡献一个乘积；交换律使选取 $k$ 个 $y$ 的乘积 都成为同一单项式 $x^{n-k}y^k$。反过来，产生这些形式指数的每组选择都确定唯一的上述子集。 合并贡献后，系数便是 $\binom nk$。该系数恒等式随后适用于所有实数代入，包括零。

这里 $k$ 数的是 $y$ 的选择数；若改数 $x$，指标便换成 $n-k$。 端点子集 $S=\varnothing$ 与 $S=\{1,\ldots,n\}$ 各给出一种选择。 遍历所有子集大小，合并前共有 $2^n$ 个乘积。

每个乘积的总次数都是 $n$，即两个指数之和为 $n$。当 $k$ 从零增加到 $n$ 时，$x$ 的指数逐渐减少，$y$ 的指数逐渐增加，合并后共有 $n+1$ 个单项式位置。两端是 $x^n$ 和 $y^n$，系数均为一。若改为记录提供 $x$ 的因子数，就得到另一种等价写法：

$$(x+y)^n=\sum_{k=0}^n\binom nk x^k y^{n-k}.$$

两种约定都正确，但同一次计算必须始终使用所选的约定。把求和次序倒过来时，补集对称性保证对应的系数相同。

Pascal 恒等式也解释了归纳步骤。把 $n$ 次方的展开式乘以 $x+y$，内部项 $x^{n+1-j}y^j$ 有两个来源：原来指标为 $j$ 的项乘 $x$，以及原来指标为 $j-1$ 的项乘 $y$。当 $1 ≤ j ≤ n$ 时，合并系数得到 $\binom nj+\binom n{j-1}=\binom{n+1}j$。两端的项则各出现一次。从一次方开始，就能逐行推出所有正整数次方的公式。

例题

展开小次方

当 $n=3$，

$$(x+y)^3=x^3+3x^2y+3xy^2+y^3.$$

$x^2y$ 的系数三，数的是乘积 $yxx$、$xyx$、$xxy$：三个因子中恰好一个提供 $y$。同样，选择两个位置提供 $y$，得到贡献给 $xy^2$ 的三个乘积。不选任何 $y$ 或全部选择 $y$，则得到两端的项。因此，合并前的 $8$ 个乘积变成 $4$ 个单项式，系数为 $1,3,3,1$，而系数之和仍然数尽全部八种选择。

代入特定数值，可以把这个观察推广。取 $x=y=1$，每个单项式都变成一，所以系数之和为 $2^n$；取 $x=1$、$y=-1$，各项交替带正负号，总和为零。对正整数 $n$，即

$$\sum_{k=0}^n\binom nk=2^n, \qquad \sum_{k=0}^n(-1)^k\binom nk=0.$$

第二个等式表示偶数元素子集与奇数元素子集的数目相等。这里正整数条件不能忽略：若 $n=0$，交错和只含一个值一。两次代入都直接使用已经证明的有限二项式定理。

抽取系数

只寻找某一项时，二项式定理尤其方便。先写一般项，把原括号中的每个完整加数看作一个整体，再把组合数、数值因子、正负号与变量指数分开处理。指数帮助我们确定指标，却不会单独给出系数。

对于 $(ax^p+bx^q)^n$，其中 $a,b$ 是数值常数，$p,q$ 是整数指数，代入有限二项式定理得到

$$T_k=\binom nk (ax^p)^{n-k}(bx^q)^k =\binom nk a^{n-k}b^k x^{p(n-k)+qk}, \qquad k=0,1,\ldots,n.$$

若出现负指数，须有 $x\ne0$。要求 $x^r$ 的系数，就解方程 $p(n-k)+qk=r$，只保留满足 $0 ≤ k ≤ n$ 的整数指标。对每个合法指标，计算 $\binom nk a^{n-k}b^k$，包括常数带来的正负号。没有合法指标时，系数为零。当 $p\ne q$ 时，至多只有一个指标符合；若多项具有同一指数，就必须把它们的系数相加。

例题

寻找常数项

找出

$$\left(x^3-\frac{1}{x}\right)^9, \qquad x\ne0$$

的常数项。

第二个加数是完整的 $-1/x$，所以选择它 $k$ 次，既会产生 $(-1)^k$，也会产生 $x^{-k}$。一般项为

$$\binom{9}{k}(x^3)^{9-k}\left(-\frac1x\right)^k =\binom{9}{k}(-1)^k x^{27-4k}.$$

常数项的指数为零。方程 $27-4k=0$ 给出 $k=27/4$，不是整数。因此展开式没有常数项，即常数项系数为零。把指标四舍五入，会选中另一个次方，并不能得到所谓近似的常数项。

比较相近的表达式 $(x^2-1/x)^9$，仍取 $x\ne0$。第一个加数的指数改变后，一般项成为

$$\binom9k(x^2)^{9-k}\left(-\frac1x\right)^k =\binom9k(-1)^k x^{18-3k}.$$

此时 $18-3k=0$ 给出 $k=6$，是范围内的整数，所以常数项为 $\binom96(-1)^6=84$。选了六个负因子，故符号为正。这两个表达式说明，每次都必须重新计算指数，并检验解是否为合法指标。

寻找指定系数时，可依照以下步骤：

1. 写出一般项，并说明指标记录哪一种选择。
2. 化简变量指数，同时保留所有数值因子的次方与正负号。
3. 令指数等于题目要求的次方。
4. 检查每个解是否为满足 $0 ≤ k ≤ n$ 的整数。
5. 把合法指标代入数值系数；若有多个贡献属于同一次方，则相加。

常见错误

二项式索引必须是范围内的整数

指标记录被选中的因子数，所以不能是分数、负数，或大于因子的总数。不合法的指标意味着所求的项没有出现。即使指标合法，系数通常也不只是组合数：两个加数中的数值因子及其正负号仍须计算。常数项是指数为零的项，不是把变量代入零；当原式含倒数次方时，代入零尤其没有意义。

快速检查

思考检查

为什么 $C(n,k)$ 要除以 $k!$，但 $P(n,k)$ 不需要？

比较有序与无序。

解答 · 答案

$P(n,k)$ 计算有次序排列；$C(n,k)$ 计算无次序选择，所以要除去每个已选集合内部的 $k!$ 种排列。对象互不相同，保证每个选定集合恰好都有这么多种次序。

思考检查

从 $(0,0)$ 到 $(4,2)$，每步只可向右或向上，共有多少条路径？

数向右步的位置。

解答 · 答案

总共 $6$ 步，其中 $4$ 步向右，所以共有 $\binom64=15$ 条。改选两步向上的位置，由补集对称性得到相同答案。

思考检查

设整数 $n ≥ 2$，$(x+y)^n$ 中 $x^{n-2}y^2$ 的系数是什么？

使用二项式定理。

解答 · 答案

系数是 $\binom n2$：恰好选出两个因子提供 $y$，其余因子全部提供 $x$。

练习

1. 计算 $\binom{7}{3}$，并说明其计数意思。
2. 用阶乘公式证明 $\binom{n}{k}=\binom{n}{n-k}$。
3. 求 $(2x-3)^6$ 中 $x^4$ 的系数。
4. 求 $(x^2+1/x)^6$ 中 $x^0$ 的系数，其中 $x\ne0$。

引导解答

解答 · 参考解答 1

$\binom73=7!/(3!4!)=(7\cdot6\cdot5)/(3\cdot2\cdot1)=35$，代表七元素集合的三元素子集数。每个子集对应六个有序选择，除法消去了这些内部次序。

解答 · 参考解答 2

对整数 $0 ≤ k ≤ n$，代入公式：$\binom{n}{n-k}=n!/((n-k)!(n-(n-k))!)=n!/((n-k)!k!)=\binom nk$。由 $0!=1$，两个表达式在端点也都有定义。

解答 · 参考解答 3

一般项为 $\binom6k(2x)^{6-k}(-3)^k$。令 $6-k=4$，得合法整数指标 $k=2$。系数为 $\binom62 2^4(-3)^2=15\cdot16\cdot9=2160$。两个数值因子的次方都不能遗漏，负数的偶次方使这一项的系数为正。

解答 · 参考解答 4

一般项为 $\binom6k(x^2)^{6-k}x^{-k}=\binom6k x^{12-3k}$。令 $12-3k=0$，得合法整数指标 $k=4$，系数为 $\binom64=15$。两个加数的数值系数均为正，所以没有额外负号；这一次，指数方程确实有合法解。