环论(二项式定理)

前置

• 环论(幂运算)

二项式定理

$(x+y{)}^n$ 的每个因子选 $x$ 或 $y$。展开写成对选择函数求和；证明对因子个数归纳，反复使用分配律。

引理

设 $R$ 是含幺交换环，$1$ 为其乘法单位元，$I$ 为有限集，$a_i,b_i\in R$。记 $c_{i,0}=a_i$，$c_{i,1}=b_i$。空乘积规定为 $1$。乘法交换且结合，故 ${\prod }_{i\in I}$ 与把 $I$ 排成序列的方式无关。则

$$\prod _{i\in I}(a_i+b_i)=\sum _{f:I\to \{0,1\}}\prod _{i\in I}{c}_{i,f(i)}.\text{\hspace{1em}(4)}$$

证明

对 $n=|I|$ 归纳。取双射把 $I$从 $A_n^0=1$ 递推，得到
积约定为 $1$。$\varnothing \to \{0,1\}$ 只有空函数，其空乘积也是 $1$，两边相等。

设等式对某个 $n$ 成立。第 $n+1$ 个因子拆出来，再用归纳假设：

$$\prod _{i=1}^{n+1}(a_i+b_i)=(\prod _{i=1}^n(a_i+b_i))(a_{n+1}+b_{n+1})=\left(\sum _{f:[n]\to \{0,1\}}\prod _{i=1}^n{c}_{i,f(i)}\right)(c_{n+1,0}+c_{n+1,1}).\text{\hspace{1em}(5)}$$

对和式中的每一项用分配律，并按最后一个因子的取值分开：

$$=\sum _{f:[n]\to \{0,1\}}\left(\prod _{i=1}^n{c}_{i,f(i)}\right)c_{n+1,0}+\sum _{f:[n]\to \{0,1\}}\left(\prod _{i=1}^n{c}_{i,f(i)}\right)c_{n+1,1}.\text{\hspace{1em}(6)}$$

每个 $f:[n]\to \{0,1\}$ 与 $\epsilon \in \{0,1\}$ 决定唯一的 $\tilde{f}:[n+1]\to \{0,1\}$，

$$\tilde{f}(i)=\{\begin{array}{ll}f(i),& 1\le i\le n,\\ \epsilon ,& i=n+1.\end{array}\text{\hspace{1em}(7)}$$

因此 (6) 等于

$$\sum _{\tilde{f}:[n+1]\to \{0,1\}}\prod _{i=1}^{n+1}{c}_{i,\tilde{f}(i)}.\text{\hspace{1em}(8)}$$

这就是 $n+1$ 时的等式。由归纳，引理对一切有限 $I$ 成立。$n=1$ 是从空乘积走出的第一步，右边恰为 $a_1+b_1$。

定理

设 $R$ 是含幺交换环，$1$ 为其乘法单位元，$n$ 为非负整数，$x,y\in R$。对 $z\in R$ 约定 $z^0=1$，且当 $m\ge 0$ 时 $z^{m+1}=z^{m}z$。非负整数 $m$ 作用在 $a\in R$ 上是累加：把 $a$ 加 $m$ 次，$m=0$ 时得加法零元 $0$。$n=0$ 时把 $(x+y{)}^0$ 规定为 $1$。则

$$(x+y{)}^n=\sum _{k=0}^n{C}_n^k{x}^k{y}^{n-k}.\text{\hspace{1em}(9)}$$

右端的 $C_n^k$ 是组合数，按上述整数倍作用在 $x^k{y}^{n-k}$ 上。系数环为含幺交换环时，多项式环仍是含幺交换环，未定元是其中的元素，故同一等式对未定元成立。

证明

对 $i\in [n]$ 取 $a_i=x$，$b_i=y$，从而 $c_{i,0}=x$，$c_{i,1}=y$。引理给出

$$(x+y{)}^n=\sum _{f:[n]\to \{0,1\}}\prod _{i=1}^n{c}_{i,f(i)}.\text{\hspace{1em}(10)}$$

按取到 $x$ 的次数分组。记

$$F_k=\{f:[n]\to \{0,1\}:|f^{-1}(0)|=k\}.\text{\hspace{1em}(11)}$$

这些集合两两不交，且

$$\{f:[n]\to \{0,1\}\}=F_0\bigsqcup \cdots \bigsqcup F_n,\text{\hspace{1em}(12)}$$

所以 (10) 按 $k$ 写成

$$(x+y{)}^n=\sum _{k=0}^n\sum _{f\in F_k}\prod _{i=1}^n{c}_{i,f(i)}.\text{\hspace{1em}(13)}$$

若 $f\in F_k$，则有 $k$ 个因子为 $x$，其余 $n-k$ 个为 $y$。乘法交换，乘积与这些因子的位置无关：

$$\prod _{i=1}^n{c}_{i,f(i)}=x^k{y}^{n-k}.\text{\hspace{1em}(14)}$$

(13) 的内层和是把这个元素相加 $|F_k|$ 次，

$$\sum _{f\in F_k}\prod _{i=1}^n{c}_{i,f(i)}=|F_k|x^k{y}^{n-k}.\text{\hspace{1em}(15)}$$

$f\in F_k$ 由 $S=f^{-1}(0)$ 决定，且 $S\in C(n,k)$。反过来，每个 $S\in C(n,k)$ 给出

$$f_S(i)=\{\begin{array}{ll}0,& i\in S,\\ 1,& i\notin S,\end{array}\text{\hspace{1em}(16)}$$

并且 $f_S^{-1}(0)=S$，故 $f_S\in F_k$。$f\mapsto f^{-1}(0)$ 与 $S\mapsto f_S$ 互逆，因此 $|F_k|=|C(n,k)|=C_n^k$。代入 (15)，再代入 (13)，得到 (9)。