10. 二项式定理 Binomial Theorem

引理

令 $A(x)$ 是一个形式幂级数，同时 $A(0) = 1$, $d\in \mathbb N\backslash \{0\}$ 那么存在唯一的形式幂级数 $B(x)$ 使得 $B(0) = 1$ 且$B(x)^d = A(x)$. 那么我们写作 $B(x) = A(x)^{1/d}$

注

由于对于给定的指数 $d$, 我们都有唯一的 d 次方根使得对 $c\in \mathbb Z\backslash \{0\}，d\in \mathbb N\backslash\{0\}$ 有唯一 $A(x)^{c/d}$ 定义

组合数 combinatories

令 $m\in \mathbb Q$, 定义 $\begin{pmatrix}m \\ 0\end{pmatrix}:=1$ 那么组合数公式:

$\begin{pmatrix}m\\k\end{pmatrix}:=\frac{m(m-1)\cdots (m-k+1)}{k!}$

其中$k\in \mathbb {N} \backslash\{0\}$ 如果 $m\in \mathbb {N}\backslash\{0\}$ 那么我们有 $\begin{pmatrix}m\\ k\end{pmatrix} = \frac{m!}{k!(m-k)!}$

二项式定理

对于 $m\in \mathbb Q$, 我们有 :

$(1+x)^m = \sum_{k=0}^{\infty}\begin{pmatrix}m\\k\end{pmatrix}x^k$

引理

对于 $m\in \mathbb Q$, 且 $A(0) = 1$, 那么 $D(A(x)^m) = m\cdot (DA)(x)\cdot A(x)^{m-1}$ ， 这里 $D$ 函数表示 求导

注

这个引理用于证明多项式求导的通项公式

引理证明

对于 $m = p / q$ 其中 $p\in \mathbb Z, q\in \mathbb Q_+$, 我们有

$p\cdot (DA)(x) \cdot A(x)^{p-1} = D(A(x)^p) = D((A(x)^m)^q) = q\cdot (A(x)^m)^{q-1}\cdot D(A(x)^m)$

因此我们化简可以得到 $D(A(x)^m) = \frac{p\cdot D(A)(x)\cdot A(x)^{p-1}}{q\cdot(A(x)^m)^{q-1}} = m\cdot (DA)(x)\cdot A(x)^{m-1}$ $\square$

二项式定理证明

通过引理我们可以知道，对于二项式左边进行求导可以得到

$D((1+x)^m) = m(1+x)^{m-1}$

那么通过递归，我们可以回到任意指数 n

$D^n((1+x)^m) = m(m-1)\cdots (m-n+1)(1+x)^{m-n}$

因此这个公式可写作

$[x^n](1+x)^m = \frac{D^n(1+x)^m(0)}{n!} = \begin{pmatrix}m\\ n \end{pmatrix}\quad \square$

其中这里的$n!$ 是用来平衡求求导之后的系数的，且带入 x = 0 的时候得到的就是纯净的第n个系数了

二项式定理的应用

指数多项式到二项式变换

对于函数 $A(0) =1$, 且 $m\in \mathbb Q$, 那么

$A(x)^m = (1+(A(x)-1))^m = \sum_{n\ge 0}\begin{pmatrix}m \\ n\end{pmatrix} (A(x) - 1)^n$

这样可以将一个指数次数的多项式公式进行展开

负数次数的二项式 (广义二项式定理)

其实，作为并不天真的大学生，我们只有计算自然数指数的二项式会有有限个项，但是对于负数、分数指数，我们都会有无限个项即形成一个新的级数展开。
首先我们使用通向公式推导负数指数的情况

$\begin{pmatrix}m\\ k\end{pmatrix} = \frac{m!}{k!(m-k)!} = \frac{m(m-1)\cdots (m-k+1)}{k!}$

如果 $m<0$, 我们有 $m(m-1)\cdots (m-k+1) = (-1)^k(-m)(-m-1)\cdots (-m+k-1)$
例如，令 $m=-1$, 那么我们有 $\begin{pmatrix}-1\\ k\end{pmatrix} = (-1)^k$
那么 $(1+x)^{-1}=\sum_{n\ge 0}\begin{pmatrix}-1 \\ n\end{pmatrix} x^n = \sum_{n\ge 0} (-1)^n x^n$

几何级数 （重中之重）

将上面公式带入 $x = -x$ 那么我们会有 $(1-x)^{-1} = \sum_{n \ge 0} x^n$

二项式负数展开

$(1+x)^{-d} = \sum_{n\ge 0} \begin{pmatrix} -d \\ n \end{pmatrix} x^n = \sum_{n\ge 0}(-1)^n\begin{pmatrix} d + n - 1\\ n \end{pmatrix} x^n$

$(1-x)^{-d} = \sum_{n\ge 0} \begin{pmatrix} -d \\ n \end{pmatrix} (-x)^n = \sum_{n\ge 0} \begin{pmatrix} d + n - 1\\ n \end{pmatrix} x^n$

二项式分式

$\frac{x^k}{(1-x)^{k+1}} = \sum_{n\ge 0} \begin{pmatrix} n \\ k \end{pmatrix} x^n$

这个公式实际上是对上面的 $(1-x)^{-d}$ 的变形得到的，令 $d = k+1$ 之后我们有 LHS = $\sum_{n=0}\begin{pmatrix}n+k\\k\end{pmatrix}x^{n+k}$ 再用重新定义 $n = n+k$ 对公式进行化简得到目标公式

注

我们会发现这里的公式和二项式定理的公式非常相似，但是这里迭代量是 $n$ 而不是 $k$ 且注意 $x$ 的指数也是 n 而不是 k

奇偶项阶乘变换

对于阶乘常见形式 $1\cdot 3\cdots\ \cdot (2n-1)$ 我们首先可以变换为 $\frac{(2n)!}{2^n\cdot n!}$

组合公式

$\sum_{k=0}^n \begin{pmatrix}k\\m\end{pmatrix} = \begin{pmatrix}n+1 \\ m+1\end{pmatrix}$

证明 1

首先证明 $\sum_{k=0}^\infty \sum_{k=0}^n \begin{pmatrix}k\\m\end{pmatrix}x^n = \sum_{n=0}^{\infty}\begin{pmatrix}n+1 \\ m+1\end{pmatrix}x^n$
LHS = $\sum_{k=0}^\infty \begin{pmatrix}k\\m\end{pmatrix}\sum_{n\ge k} x^n =\sum_{k=0}^\infty \begin{pmatrix}k\\m\end{pmatrix}\frac{x^k}{1-x} = \frac{1}{1-x}\sum_{k=0}^\infty\begin{pmatrix}k \\ m\end{pmatrix} x^k = \frac{1}{1-x} \cdot \frac{x^m}{(1-x)^{m+1}} = \frac{x^m}{(1-x)^{m+2}}$ RHS = $\frac 1 x \sum_{n=0}^\infty \begin{pmatrix}n+1 \\ m+1\end{pmatrix}x^{n+1} = \frac{1}{x}\cdot \frac{x^{m+1}}{(1-x)^{m+2}} = \frac{x^m}{(1-x)^{m+2}}$ $\square$
注意，这里的 $\sum_{n\ge k}x^n = \sum_{n=0}x^n \cdot x^k = \frac{x^k}{1-x}$

可数子集

性质

对于 $[n] = \{1,2\cdots ,n\}$, 那么模 k 的子集数量是 $\begin{pmatrix}n\\ k\end{pmatrix}$

组合理解

对于 $(1+x)^n$ 进行展开，对任意一个 $1+x$, 选择 1 就表示 不在子集里面，选择 $x$ 就表示在子集里面，那么我们找 $k$ 尺寸的子集就是在找 $x^k$ 的系数，即 $\begin{pmatrix}n\\ k\end{pmatrix}$

帕斯卡恒等式 Pascal’s Identity

对于正整数 n, k, 我们有:

$\begin{pmatrix}n\\ k\end{pmatrix} = \begin{pmatrix}n-1\\ k-1\end{pmatrix} + \begin{pmatrix}n-1\\ k\end{pmatrix}$

证明

由于 $(1+x)^n = (1+x)^{n-1} (1+x)$, 因此通过对比系数，我们有 $[x^k](1+x)^{n} = [x^k](1+x)^{n-1} + [x^{k-1}](1+x)^{n-1}$ $\square$

多项式定理

组合公式展开

对于 $k_1 + k_2 + \cdots + k_d = n$, 我们有多项式系数为 $\begin{pmatrix}n\\ k_1, k_2, \cdots , k_d\end{pmatrix} = \frac{n!}{k_1!k_2!\cdots k_d!}$

多项式定理

对于变量 $x_1, x_2, \cdots , x_d$, 我们有:

$(x_1 + x_2 + \cdots + x_d)^n = \sum_{k_1+k_2+\cdots + k_d = n}\begin{pmatrix}n\\ k_1, k_2, \cdots , k_d\end{pmatrix}x_1^{k_1}x_2^{k_2}\cdots x_d^{k_d}$

理解

我们假设一种情况，一共有10个房子，我们需要涂漆成4蓝2红3绿1橙，那么我们首先假设不同颜色的房子都是不一样的，那么一共有 $10!$ 种可能性
然后我们要排除各自相同颜色重复的case，即除以 $4!\cdot 2!\cdot 3!\cdot 1!$
因此我们就可以得到上述的多项式定理公式

例子：密西西比的排列可能性

将单词 MISSISSIPPI 进行排列，我们一共有 $\frac{11!}{4!4!2!1!}$ 种可能性

证明

我们需要通过索引 d 进行数学归纳法分析
Base Case: $d =1$ 我们会发现等号两边的值都是 $x_1^n$
Inductive Case: $d>1$ 我们假设对于 $d-1$ 的情况成立，同时我们假设 $x = x_1 + \cdots + x_d$ 那么我们有:

$(x_1 + \cdots + x_d)^n = \sum_{m=0}^n\begin{pmatrix}n\\ m\end{pmatrix}(x_1 + \cdots + x_{d-1})^m x_d^{n-m}$

那么我们再对 $(x_1 + \cdots + x_{d-1})^m$ 进行展开，我们有:

$(x_1 + \cdots + x_{d-1})^m = \sum_{k_1 + \cdots + k_{d-1} = m}\begin{pmatrix}m\\ k_1, \cdots , k_{d-1}\end{pmatrix}x_1^{k_1}\cdots x_{d-1}^{k_{d-1}}$

接下来我们令 $k_d = n-m$, 那么我们有:

$\begin{pmatrix}n \\ n-k_d\end{pmatrix}\begin{pmatrix}n-k_d\\ k_1, \cdots , k_{d-1}\end{pmatrix} = \begin{pmatrix}n\\ k_1, \cdots , k_{d-1}, n-k_d\end{pmatrix}$

集合的计数：多项式法

多重子集 multisubset

对于集合 $[d]$, 其尺寸为 n 的多重集的数量有 $\begin{pmatrix}n+d-1\\ n\end{pmatrix}$ 种

证明（多项式法）

我们计算 $[x^n](1+x+\cdots)^d$ 的系数，我们发现这个系数就是 $\begin{pmatrix}n+d-1\\ n\end{pmatrix}$

理解：小球和挡板

我们对于一个有 n 个球的盒子进行分割，一共有 d - 1 个隔板（因为总共有 d 个类别）且每个类可以没有元素，那么不考虑顺序，总共有 $(n+1)\cdot (n+2)\cdots (n+d-1)$种可能，再除以顺序 $n!$ 就得到了上述的公式

有理数解的数量

对于 $x_1 + \cdots + x_d = n$, 我们首先区分不同变量的定义域限制
我们使用多项式进行筛选，即 $1 + x^2 + x^3 + \cdots$ 进行相乘，并且选取其第 $n$ 次项的系数就是解的可能性（其实在求这个值的过程中就已经计算过解的数量了）

例

对于 $x_1 + x_2 + x_3 + x_4 = n$ 且 $x_1, x_2 \ge 0, x_3\in [2,5], x_4>0$ 那么我们可以表述结果为

$[x^n] (1+x+x^2 + \cdots)^2(x^2 + x^3 + x^4 + x^5)(x+x^2 + \cdots)$

再通过几何级数等式，我们有

$[x^n]\frac{x^3 + x^4 + x^5 + x^6}{(1-x)^3}$

Catalan Numbers

问题引入

小明家 $(0,0)$走到少年宫的路程 中会有 $n\times n$ 个路口，使用对角线连接小明的家和少年宫，那么请问小明有多少种走法永远不到对角线上方？

解法

首先考虑所有的可能性，即一共 2n 步，其中我们要选择 n 步往上走，那么就是 $\begin{pmatrix}2n\\ n\end{pmatrix}$ 种可能性
然后去除到过对角线上方的路径的可能性数量：我们已知到达上半图的路径必然会经过 $y =x+1$ 这条线，那么我们将之后的路径围绕 $y = x+1$ 进行对称 (这一步叫反射定理)，那么我们就可以得到一个新的路径，这个路径的数量就是 $\begin{pmatrix}2n\\ n+1\end{pmatrix}$ 种
因此我们得到总的可能性数量是

$C_n = \frac{1}{n+1}\begin{pmatrix}2n\\ n\end{pmatrix}$

递归形式

$C_{n+1} = \sum_{k=0}^n C_kC_{n-k}$

十二重方法 Twelvefold way

在组合数学中，我们将计数问题分为 12 种类型，分别是：

这里我们主要注意前两行的六种情况

第二类斯特林数

在上图中我们看到了满射的时候有 $\genfrac\{\}{0pt}{}{n}{k}$ 这些就是第二类斯特林数的表述，这个数表示将 k 个不同的球放到 n 个相同的盒子中分类的可能性

例子

$\genfrac\{\}{0pt}{}{15}{12}$ 首先我们用小球 - 盒子解释这个公式: 将 15 个不同的小球放到 12 个相同盒子的可能性数量