Арифметика биномиальных коэффициентов

17

АРИФМЕТИКА
БИНОМИАЛЬНЫХ
КОЭФФИЦИЕНТОВ

Д. Б. Фукс, М. Б. Фукс

$(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, …, называются биомиальные коэффициентами. В этой статье расссказывается о различных свойствах биомиальных коэффициентов. В первом параграфе излагается «общая теория»: большинство из доказываемых здесь теорем входило равше в школьную программу. Во втором параграфе мы показем, как можно совсем легко найти остаток от деления любого из биомиальных коэффициентов на любое простое число. Некоторые утиверждения этого параграфа сформулированы в виде гипотез. Можно быть, читатели «Кванта» попробуют их доказать.

18

§ 1. Определение и простейшие свойства биномiales коэффициентов

Если двучлен (бином) $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,$$

Коэффициенты этих многочленов называются биномиальным. Для них есть специальные обозначения: коэффициент при $x^m$ в $(1+x)^n$ обозначает через $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$ приведены в таблице.

Мы видим, что биномиальные коэффициенты — довольно-tаки быстро растущее числа. Наблюдательный читатель заметит в расположении этих чисел ряд закономерностей. Как правило, такие закономерности легко выводятся из определения биномиальных коэффициентов. Мы доказем здесь только главные из них. Начнем с главного из главных — с так называемого тожества Паскала.

Будем выделять в них: для нас это не важно. Итак,

$$(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$ есть коэффициент при $x^m$ в многочлене $(1+x)^n$. Для того чтобы найти этот коэффициент, нужно перемножить $n$ многочленов, равных $1+x$. Перемножив $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$. Этим формула (3) доказана при любом $n$.

Мы рекомендуем читателю, впервые познакомившись с формулой (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$ по модulo $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$ не делятся на 3 примерно 26,2%; если $0 \leq n \leq 3^{10}$, то примерно 3,6%, а если $0 \leq n \leq 3^{15}$, то примерно 0,45%.

В заключение скажем несколько слов о весыта наглядной интерпретации теоремы 4, которое можно получить, рассматривая так называемый «треугольник Паскала по модели $p$». Так называется треугольная таблица, которая получится из треугольника Паскала, если в нем заменить каждое число его остатком от деления на $p$. Мы не доказываем про этот треугольник никаких теорем, но предлагаем читателю посмотреть две картины (на обложке и на стр. 22), на которых изображены треугольники Паскала по модулям 2 и 3. Подумайте, как устроены эти треугольники в той части, которая не видна на рисунке. Постраайтесь формулировать теорему 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, … — это последовательные степени двойки.) Сами полученные числа исчем особенным не применять; их последовательные разности, однако, обнаруживают порAZительные свойства. Посмотрим на них:

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