二项式系数的算术

17

算术
二项式
ODDS

D.B.福克斯，M.B.福克斯

$(1+x)^2=1+2x+x^2$
$(1+x)^3=1+3x+3x^2+x^3$

任何小学生都知道这些公式。数字 1、2、1； 1, 3, 3, 1，以及以类似方式获得的数字的 4, 5, … 次方，称为生物项系数。本文讨论生物系数的各种属性。第一段阐述了“一般理论”：这里证明的大部分定理也包含在学校课程中。在第二段中，我们将展示如何在将任何生物系数除以任何素数时轻松找到余数。本段中的一些陈述是作为假设提出的。也许读者«Kvant»会尝试证明它们。

18

§ 1. 二项式系数的定义和最简单的性质

如果二项式（二项式）$1+x$用某种自然幂$n$进行加权，那么显然，结果是一个$n$次数的多项式（即$x$出现在该多项式中的最高次数将等于$n$）。例如：

$$(1+x)^0 = 1,$$
$$(1+x)^1 = 1+x,$$
$$(1+x)^2 = 1+2x+x^2,$$
$$(1+x)^3 = 1+3x+3x^2+x^3,$$
$$(1+x)^4 = 1+4x+6x^2+4x^3+x^4,$$
$$(1+x)^5 = 1+5x+10x^2+10x^3+$$
$$+5x^4+x^5,$$

这些多项式的系数称为二项式。它们有特殊的符号：$(1+x)^n$中$x^m$的系数用$C_n^m$表示。例如，$C_2^1=2$、$C_4^2=6$、$C_5^3=10$。在旧的代数教科书中，数字$C_n^m$被称为“$n$到$m$的组合数”。这是有原因的，但我们没有

从这里很容易得到

$$(a+x)^n = C_n^0a^n + C_n^1a^{n-1}x\ldots$$
$$\ldots + C_n^nx^n$$

（将公式（1）应用于$(1+x)a^n$的计算并将所得等式两边乘以$a^n$就足够了）。最后一个公式称为牛顿二项式。因此，系数被称为“二项式”。

显然，$C_n^m$是非负整数，$C_n^m=0$对应$m>n$（多项式$(1+x)^n$的次数为$n$，$x^m$和$m>n$不包含在其中）。很容易进一步验证$C_n^0=C_n^1=1$。其他二项式系数 $C_n^m$（其中 $0<m<n$）可以通过 $1+x$ 的各种幂得到。表中给出了 $n\leqslant10$ 的值。

我们看到二项式系数增长得相当快。细心的读者会注意到这些数字的排列有多种模式。通常，这种模式很容易从二项式系数的定义中导出。我们在这里仅证明主要的。让我们从最重要的开始——所谓的帕斯卡恒等式。

我们将在其中强调：对我们来说这并不重要。所以，

$$(1+x)^n = C_n^0+C_n^1x+C_n^2x^2+\ldots$$
$$\ldots +C_n^nx^n.$$

(1)

定理 1（帕斯卡恒等式）。

$$C_n^m = C_{n-1}^m+C_{n-1}^{m-1}$$

(2)

对于任何自然$n, m$。

19

证明。根据定义，$C_n^m$是多项式$(1+x)^n$中$x^m$的系数。为了找到这个系数，您需要乘以等于 $1+x$ 的 $n$ 多项式。将它们相乘$n-1$，我们得到多项式$1+C_{n-1}^1x + C_{n-1}^2x^2 + \dots + x^{n-1}$。执行最后一个乘法，我们得到

$$(1+x)(1+C_{n-1}^1x + C_{n-1}^2x^2 + \dots + x^{n-1}) = 1 + C_{n-1}^1x + C_{n-1}^2x^2 + \dots + x^{n-1} + x + C_{n-1}^1x^2 + C_{n-1}^2x^3 + \dots + x^n = 1 + (C_{n-1}^1 + 1)x + (C_{n-1}^2 + C_{n-1}^1)x^2 + \dots + x^n.$$

在结果表达式中，$x^m$的系数等于$C_{n-1}^m + C_{n-1}^{m-1}$。因此，

$$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}.$$

帕斯卡恒等式可以方便地用于计算生物系数。例如，如果我们想在表中再添加一行（第十一行），那么我们只需将上一行（第十行）中相邻的数字成对添加即可：

$$C_{11}^0 = 1 \quad C_{11}^1 = C_{10}^1 + C_{10}^0 = 11 \quad C_{11}^2 = C_{10}^2 + C_{10}^1 = 55 \quad C_{11}^3 = C_{10}^3 + C_{10}^2 = 165 \quad C_{11}^4 = C_{10}^4 + C_{10}^3 = 330 \quad C_{11}^5 = C_{10}^5 + C_{10}^4 = 462$$

这说明将生物项系数写成三角表的形式是很方便的（见

3*

20

因此，公式（3）对于$n=1$成立，并且从其对于$n-1$的有效性可知它对于$n$也成立。这证明了对于任意$n$的公式(3)。

我们建议初次熟悉公式（3）的读者从中推导出已知的$C_n^0 = C_n^n = 1$和$C_n^m = 0$对于$m>n$的等式。

公式（3）很有趣，因为它右边的分数等于一个整数，即它的分母中的所有数字都会与分子中的数字相消。

将进一步使用以下定理。

定理3. 如果数字$n$和$m$互质（即数字$n$和$m$的最大公约数为1），则$C_n^m$能被$n$整除。

证明：

$$C_n^m = \frac{n(n-1)\ldots(n-m+1)}{1\cdot2\ldots m} = \frac{n}{m} \cdot \frac{(n-1)\ldots(n-m+1)}{1\cdot2\ldots(m-1)} = \frac{n}{m} \cdot C_{n-1}^m$$

因此，

$$mC_n^m = nC_{n-1}^m$$

即数字$mC_n^m$可以被$n$整除。但由于 $m$ 和 $n$ 互质，即 $m$ 不能被 $n$ 的任何素因数整除，因此 $C_n^m$ 可以被 $n$ 整除。

例如，$C_9^4 = 126$可以被9整除，$C_{10}^3 = 120$可以被10整除。

让我们指出生物系数的更多属性：

1. $C_n^m = C_{n-1}^m$
2. $C_n^m + C_{n+1}^m + \ldots + C_{m+k}^m = C_{m+k+1}^m$
3. $C_n^0 + C_n^1 + \ldots + C_n^n = 2^n$
4. $C_n^0 + C_n^2 + C_n^4 + \ldots = C_n^1 + C_n^3 + C_n^5 + \ldots$

我们将这些性质的证明留给读者。

§ 2. 生物系数除以素数的余数

在本段（以及下一段）中，我们经常需要使用“数字 $a$ 和 $b$ 除以 $p$ 时余数相等”的形式。通常，这种形式被缩写符号“$a \equiv b$（mod$p$）”代替。换句话说，公式“$a \equiv b$ (mod $p$)”意味着$a-b$可以被$p$整除。例如，$4 \equiv 1$ (mod 3)、$999999 \equiv 222222$ (mod 7) 等。公式“$a \equiv b$ (mod $p$)”有时读作如下：“数字$a$ 与数字$b$ 模$p$ 相当”（但是，我们也不会使用表达式）。

以下是符号 ≡ 的两个特性：

1. 如果 $a \equiv b$ (mod $p$) 和 $k$ 是整数，则 $ka \equiv kb$ (mod $p$)。

事实上，如果$a-b$能被$p$整除，那么$ka-kb = k(a-b)$也能被$p$整除。

2. 如果 $a \equiv b$ (mod $p$) 和 $b \equiv c$ (mod $p$)，则$a \equiv c$ (mod $p$)。

事实上，如果$a-b$能被$p$整除并且$b-c$能被$p$整除，那么$a-c = (a-b)+(b-c)$也能被$p$整除。

让我们回想一下，任何自然数$a$都可以除以自然数$p$“有余数”，即$a$可以唯一地写成$a=bp+c$的形式，其中$b$，$c$是整数，使得$0 \leq c < p$。

本节的主要目标是证明以下陈述。

定理4.设$p$为素数，$m$和$n$为自然数。此外，令$k$和$l$为数字$m$和$n$除以$p$的部分，$s$和$t$为余数（即$m=kp+s$、$n=lp+t$，其中$k$、 $l$、$s$、$t$ 为整数，$0 \leq s < p$、$0 \leq t < p$）。然后

$$C_n^* = C_l^* \cdot C_s^* \pmod p.$$

正如我们将在下面看到的，该定理使我们能够找到生物系数除以素数的余数，几乎无需执行任何计算。

23

这样$C_{119}^{33} \equiv 0$ (mod 3)，即$C_{119}^{33}$可以被3整除而没有余数。

请注意，如果我们将定理 4 应用于 $C_n^m$，其中 $n \geq m$，那么通过写出 $m = kp + s$，$n = lp + t$，我们当然会得到 $l \geq k$；然而，无法预测$s$、$t$ 哪个数字更大。如果有$s > t$，那么根据我们的定理$C_n^m \equiv C_l^k C_s^t = 0$ (mod $p$)，即$C_n^m$能被$p$整除。正如我们所看到的，为了确定数字$C_n^m$除以$p$的余数，通常需要多次使用定理4；每当类似上述的现象发生时，每当这种情况发生时，这意味着类似的数字$C_n^m$可以被$p$整除。同样，我们得到$C_{119}^{33}$可以被3整除。

我们看到，$n$越大，$C_n^m$越有可能被$p$整除。很容易证明以下更精确的说法：$C_n^m$和$0 \leq n \leq p^r$、$0 \leq m \leq n$的数字总数还有$\frac{p^r (p^r + 1)}{2}$，其中不能被$p$整除的正好是$\frac{p^r (p + 1)^r}{2^r}$（这里$p$很简单，$r$很自然；证明仅基于定理3，我们留下给读者）。需要强调的是，对于大$r$，数字$\frac{p^r (p + 1)^r}{2^r}$比数字$\frac{p^r (p^r + 1)}{2}$小许多倍。

例如，在数字 $C_n^m$ 和 $0 \leq n \leq 3^5$、$0 \leq m \leq n$ 中，大约有 26.2% 不能被 3 整除；如果$0 \leq n \leq 3^{10}$，则约为3.6%，如果$0 \leq n \leq 3^{15}$，则约为0.45%。

最后，我们来说说定理 4 的视觉解释的权重，它可以通过考虑所谓的“根据 $p$ 模型的帕斯卡三角形”来获得。这是从帕斯卡三角形中得到的三角表的名称，如果其中的每个数字被除以 $p$ 时的余数替换。我们不证明关于这个三角形的任何定理，但我们邀请读者看两张描绘帕斯卡三角形模 2 和 3 的图片（封面上和第 22 页）。想想这些三角形在 图 上看不到的部分是如何排列的。尝试将定理 4 表述为关于帕斯卡三角形模 $p$ 结构的定理。

§ 3. 关于生物系数除以素数幂的余数的一些知识

我们不以任何一般方式考虑将生物系数除以合数的余数问题。 （不过，读者可以自己思考一下；例如，数字$C_{119}^{33}$除以4的余数是多少：一或trem？）我们将仅限于谈论一个我们尚未完全解释的惊人现象。

让我们从一些计算开始。使用生物系数公式（参见§1，公式（2）），我们得到

$$C_2^1 = 2,$$
$$C_4^2 = 6,$$
$$C_8^4 = 70,$$
$$C_{16}^8 = 12870,$$
$$C_{32}^16 = 601080390.$$

（当然，每个人都知道 1、2、4、8、16、32…是 2 的连续幂。）结果数字本身不应该以任何特殊方式使用；然而，它们的连续差异揭示了惊人的特性。让我们看看它们：

$$6 - 2 = 4 = 2^2,$$
$$70 - 6 = 64 = 2^6,$$
$$12870 - 70 = 12800 = 2^9 \cdot 25,$$

24

---

running_head:
folio:

$$601\ 080\ 390 - 12\ 870 = 601\ 067\ 520 = 2^{12} \cdot 146\ 745.$$

我们看到这些差异被分成了二的高次方——大到这种现象不会造成伤害。有可能证明一个至少部分解释它的定理。

定理 5. 如果 $n > 1$，则数
$$\alpha_n = C_{2n+1}^{2n} - C_{2n}^{2n-1}$$
能被$2^{2n+2}$整除。

扫地。
1°。假设 $n > 1$ 显着，因为 $\alpha_1$ 等于 4 并且不能被 $2^{2n+2} = 2^4 = 16$ 整除。
2°。人们可能认为$n > 1$的$\alpha_n$甚至可以被$2^{3n}$整除：对于$n = 2, 3, 4$也是如此。但我们不知道如何证明这一点。

证明。让我们从一般观察开始，如果数字 $r$ 是奇数，则 $C_{2n}^{r}$ 可以被 $2^n$ 整除。事实上，由于 $r$ 是奇数，并且 $2^n$ 除了 2 之外没有素因数，因此数字 $r$ 和 $2^n$ 是互质的，我们需要的陈述来自定理 3。

让我们把理论
$$P(x) = (1+x)^{2n+1} - (1-x^2)^{2n}.$$

多项式$P(x)$包含$x^{2n}$，系数为$C_{2n+1}^{2n} - C_{2n}^{2n-1} = \alpha_n$（这里我们使用$n > 1$这一事实：当$(1-x^2) = 1 + (-x^2)$出现$2^n$次方时，我们得到系数$C_{2n}^{2n-1}$不是$x^{2n}$，而是(-x^2)^{2n-1} = (-1)^{2n-1}x^2^n，而数字$(-1)^{2n-1}$为1 $n > 1$ 且在 $n = 1$ 处等于 $-1$。

另一边，
$$P(x) = (1+x)^{2n+1} - (1+x)^{2n} = (1+x)^{2n}[(1+x)^{2n} - (1-x)^{2n}].$$

同时
$$(1+x)^{2n} - (1-x)^{2n} = (1+x)^{2n} - (1+(-x))^{2n} = 1 + C_{2n}^{1}x + C_{2n}^{2}x^2 + C_{2n}^{3}x^3 + \dots + x^{2n} - 1 - C_{2n}^{1}(-x) - C_{2n}^{2}(-x)^2 - C_{2n}^{3}(-x)^3 - \dots - (-x)^{2n} =$$
（因为 $(-x)^k$ 等于 $x^k$ 对于甚至 $k$ 且相等 $-x^k$ 对于奇数 $k$)
$$= 2\left(C_{2n}^{1}x + C_{2n}^{3}x^3 + C_{2n}^{5}x^5 + \dots + C_{2n}^{2n-1}x^{2n-1}\right).$$

我们强调，所得多项式 $x$ 仅以奇数次幂出现。

我们想知道 $x^{2n}$ 以什么系数进入 $P(x)$，即进入乘积
$$(1+x)^{2n}[(1+x)^{2n} - (1-x)^{2n}] = 2\left(1 + C_{2n}^{1}x + C_{2n}^{2}x^2 + C_{2n}^{3}x^3 + \dots + x^{2n}\right) \times \left(C_{2n}^{1}x + C_{2n}^{3}x^3 + C_{2n}^{5}x^5 + \dots + C_{2n}^{2n-1}x^{2n-1}\right).$$

显然，第一个因子乘以$x^{2n-1}$，第二个因子乘以$x$，第二个因子乘以$x^{2n-3}$，第二个因子乘以$x^3$，等等即可得到$x^{2n}$。因此，$x^{2n}$的$P(x)$中的系数等于$\alpha_n$，也等于
$$2\left(C_{2n}^{1}C_{2n}^{2n-1} + C_{2n}^{3}C_{2n}^{2n-3} + \dots + C_{2n}^{2n-1}C_{2n}^{1}\right).$$

众所周知，每个数字$C_{2n}^{1}, C_{2n}^{3}, \dots, C_{2n}^{2n-1}$都可以被$2^n$整除。因此，括号中的每一项都除以$2^n \cdot 2^n = 2^{2n}$；此外，两者位于整个表达式之前，

25

此外，括号中的每个术语出现两次。因此，根据需要，$\alpha_n$ 可以被 $2^{2n+2}$整除。

这样，数$\alpha_n$能被2的高次方整除的奇怪现象就在一定程度上得到了解释。但如果你用三、五、七代替二，就不会观察到类似的情况。真的吗，

$$C_9^3 - C_3^1 = 84 - 3 = 81 = 3^4;$$

$$C_{27}^9 - C_9^3 = 4686825 - 84 = 4686741 = 3^7 \cdot 2143;$$

$$C_{81}^{27} - C_{27}^9 = 2306279447501851002720 - 4686825 = 2306279447501846315895 = 3^{10} \cdot 39057044954221855;$$

$$C_{25}^5 - C_5^1 = 43130 - 5 = 43125 = 5^5 \cdot 69;$$

$$C_{49}^7 - C_7^1 = 85900584 - 7 = 85900577 = 7^5 \cdot 5111.$$

简而言之，对于素数 $p$ 来说，这个数字似乎是正确的

$$C_{pn+1}^{p^n} - C_{pn}^{p^n-1}$$

可以被数字 $p$ 的高次幂整除。但我们不知道如何证明这一点。

顺便说一句，如果 $p$ 不是素数，则不会观察到任何此类情况。例如，

$$C_{16}^4 - C_4^1 = 1820 - 4 = 1816$$

甚至不能被$4^2$整除；

$$C_{36}^6 - C_6^1 = 1947792 - 6 = 1947786$$

甚至不能被$6^2$整除。

我们相信«Kvant»的读者之一能够理解生物系数算术这个复杂的问题。