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

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,$$

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°. Можно ожидать, что $\alpha_n$ при $n > 1$ делится даже на $2^{3n}$: это верно при $n = 2, 3, 4$. Но доказывать этого мы не умеем.

Доказательство. Начнем с общего замечания, что если число $r$ нечетно, то $C_{2n}^{r}$ делится на $2^n$. В самом деле, поскольку $r$ нечетно, а $2^n$ не имеет простых делителей, кроме двойки, то числа $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$ и равно $-1$ при $n = 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}$ может получить при перемножении $x^{2n-1}$ из первого сомножителя и $x$ из второго, при перемножении $x^{2n-3}$ из второго сомножителя и $x^3$ из второго и т. д. Таким образом, коэффициент в $P(x)$ при $x^{2n}$, равный, как мы знаем $\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$ на высокие степени двойки в какой-то степени объясен. Но нечего подобное наблюдается и если заменить двойку тройкой, пятеркой, семеркой. Действительно,

$$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$.

Мы полагаем, что кто-либо из читателей «Кванта» может разобраться в этом сложном вопросе арифметики биомиальных коэффициентов.