Популярные лекции

ПО МАТЕМАТИКЕ

В.А.УСПЕНСКИЙ

ТРЕУГОЛЬНИК ПАСКАЛЯ

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 43

В. А. УСПЕНСКИЙ

ТРЕУГОЛЬНИК ПАСКАЛЯ

ИЗДАНИЕ ВТОРОЕ, ДОПОЛНЕННОЕ

МОСКВА «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1979

22. 130 У 77 УДК 511

АННОТАЦИЯ

Настоящая лекция доступна учащимся восьмилетней школы. В ней рассматривается одна важная числовая таблица (которая и называется треугольником Паскаля), полезная при решении ряда задач. Попутно с решением таких задач затрагивается вопрос, что означают слова «решить задачу». Предыдущее издание вышло в 1966 г.

Владимир Андреевич Успенский

ТРЕУГОЛЬНИК ПАСКАЛЯ

М„ 1979 г., 48 стр. с илл. Редактор В. В. Донченко

Техн. редактор А. Я. Колесникова Корректор Н. Д. Дорохова

Сдано в набор 14.08.78. Подписано в печать 24.01.79. Бумага 84X108Ус. тип. № 1. Литературная гарнитура. Высокая печать. Условн. печ. л. 2,52. Уч.-изд. л. 2,42. Тираж 200000 экз. Заказ № 1230 Цена книги 10 коп.

Издательство «Наука> Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15

Ордена Трудового Красного Знамени Ленинградская типография № 2 имени Евгении Соколовой «Союзполиграфпрома» при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 198052, Ленинград, Л-52, Измайловский, проспект, 29

© Главная редакция физико-математической литературы издательства «Наука», 1979, г., с изменениями.

СОДЕРЖАНИЕ

Предисловие................. 4

§ 1. Задача из VIII олимпиады......... 5

§ 2. Что значит решить задачу.......... 8

§ 3. Треугольник Паскаля............ 12

§ 4. Немного истории............. 19

§ 5. Операция Паскаля............. 24

§ 6. Биномиальные коэффициенты........ 27

§ 7. Число частей данного множества....... 32

§ 8. Связь с факториалами........... 40

§ 9. Наибольший общий делитель внутренних членов строки Паскаля............. 43

ПРЕДИСЛОВИЕ

Того читателя, который еще не знает, что такое треугольник Паскаля, нужно предупредить, что это не геометрический треугольник с тремя углами и тремя сторонами. Треугольником Паскаля называют одну важную числовую таблицу, с помощью которой можно решать ряд вычислительных задач. Рассматривая некоторые из таких задач, мы попутно коснемся вопроса о том, что вообще могут означать слова «решить задачу».

Изложение не предполагает каких-либо предварительных знаний, выходящих за рамки программы восьмилетней школы.

§ 1. ЗАДАЧА ИЗ VIII ОЛИМПИАДЫ

На VIII Московской математической олимпиаде (1945 г.) ее участникам из 9-х и 10-х классов была предложена следующая задача1):

Имеется сеть дорог (рис. 1). Из точки А выходят 21000 человек. Половина идет по направлению /, половина— по направлению т. Дойдя до первого перекрестка, каждая группа разделяется: половина идет по направлению /, половина — по направлению т. Такое же разделение происходит на каждом перекрестке. Сколько людей придет в каждый из перекрестков тысячного ряда2)?

Заметим прежде всего, что мы пока не знаем, имеет ли задача решение, т. е. может ли движение людей происходить так, как требуется условием задачи. Ведь если на какой-то перекресток, на котором предстоит очередное деление людского потока пополам, придет нечетное число людей, то движение застопорится. Следовательно, чтобы задача имела решение, необходимо и достаточно, чтобы в каждый перекресток любого из первых тысячи рядов, от нулевого до девятьсот девяносто девятого,

Рис. 1.

1) См. Яглом А. М. и Яглом И. М. Неэлементарные задачи в элементарном изложении. — М.: Гостехиздат, 1954, с. 10, «Номера задач, предлагавшихся на Московских математических олимпиадах», задача 606.

2) Имеется в виду, что ряды перекрестков занумерованы, начиная с нулевого, так что в нулевом ряду — один перекресток (Л), в первом — два, во втором — три и т. д.

пришло четное число людей. Мы убедимся, что это так, решая задачу.

Начнем с того, что введем обозначения для количеств людей, прошедших через каждый перекресток нашей сети дорог. Будем нумеровать перекрестки каждого ряда слева направо, начиная с нулевого; перекрестки л-го ряда, следовательно, будут нумероваться от 0-го до п-го. Число людей, прошедших через £-й перекресток я-го ряда, обозначим Нкп. Поскольку пока еще не известно, имеет ли задача решение, мы не можем быть уверены, что все числа U\ существуют, т. е. что существует каждое из чисел Нп при любом п от 0 до 1000 и любом k от 0 до п. Некоторые из них, во всяком случае, существуют. Так, в силу введенных обозначений

(1.1)

Посмотрим теперь, как связаны между собой числа

при условии, что все они существуют. Изучая эту связь, мы сможем затем установить, что все числа #„ при л ^ 1000 действительно существуют. Рассмотрим п-й и (п+1)-й ряды перекрестков и соединяющие их участки дорог; против каждого перекрестка поставим обозначение соответствующего числа людей (см. рис. 2).

Рис 2.

Количество людей, вышедших из 0-го перекрестка л-го ряда (т. е. //„), разделится пополам и одна половина придет в 0-й перекресток (п+ 1)-го ряда; поэтому

(1.2)

Другая половина от Н°п придет в 1-й перекресток (п+1)-то ряда и там соединится с половиной людей,

вышедших из 1-го перекрестка п-го ряда, т. е. с половиной от Нп. Поэтому Hn+i =---• И вообще, количество людей, пришедших на k-и перекресток (п+1)-го ряда, слагается из половины количества людей, вышедших из (k—1)-го перекрестка п-го ряда (эта половина равна —) и половины количества людей, вышедших из &-го перекрестка п-го ряда (эта половина равна -т- I. Таким образом,

(1.3)

Наконец, число людей, пришедших на (п+1)-й перекресток (п+1)-го ряда, равно половине числа людей, вышедших из п-го перекрестка п-га ряда:

(1.4)

Соотношения (1.1) — (1.4) позволяют установить, что задача действительно имеет решение. В самом деле, из равенств (1.2) — (1.4) вытекает, что если при каком-либо фиксированном n все числа п-го ряда: Н°п, Нхпу ...

— существуют и делятся на 2а, то числа (п+1)-го ряда: H°n+U Hln+u ..., Н\\%\ — существуют и делятся на а. Поэтому, поскольку все числа 0-го ряда (а их всего одно — Но) существуют и делятся на 21000 (в силу (1.1)), то все числа 1-го ряда

существуют и делятся на 2999; все числа 2-го ряда

существуют и делятся на 2998; ... ; все числа 999-го ряда

существуют и делятся на 2; все числа 1000-го ряда

существуют (и делятся на 1).

Соотношения (1.2) — (1.4) не только доказывают существование решения задачи, но и показывают, как из строчки чисел

получается строчка

Применяя последовательно эти соотношения, начиная с нулевой строки (т. е. используя соотношение (1.1)), мы в принципе можем вычислить значения Я* для всех 501 501 перекрестков, содержащихся в рядах до тысячного включительно, в частности, для всех перекрестков тысячного ряда, и тем самым решить задачу. Так, для первых рядов непосредственным вычислением находим:

§ 2. ЧТО ЗНАЧИТ РЕШИТЬ ЗАДАЧУ

Итак, задача из § 1 решена...

«Как решена? — удивится неискушенный читатель (искушенный знает наперед, что скажет автор, и ничему не удивляется). — Я не заметил, чтоб мы ее решили.»

Автор. Ну, конечно, решили. Ведь решить задачу — значит найти ее решение. Вот мы и нашли решение.

Читатель (возмущенно). Разве ж это решение?

Автор (притворяясь, что не понимает, в чем дело). А что, разве оно неверно?

Читатель. Нет, «оно» верно, но «оно» вообще не решение.

Автор. А что же такое решение?

Читатель. Строчка чисел, показывающих, сколько человек придет в перекрестки тысячного ряда.

Автор. Но в этой строчке должно быть 1001 число. Неужели устроители VIII олимпиады надеялись, что кто-нибудь напишет 1001 число?

Читатель (задумывается).

Автор. У меня есть предложение. Давайте, чтобы не осложнять ситуацию длинными строчками, выберем какой-нибудь перекресток и будем интересоваться числом побывавших в нем людей. Согласны?

Читатель (соглашается).

Автор. Так вот — что считать решением следующей задачи: сколько людей побывает в третьем перекрестке четвертого ряда?

Читатель. Как что? Число.

Автор. Как записанное?

Читатель (удивленно). Ну, в десятичной системе. Автор. А такой ответ: «#4» — не будет решением? Читатель. Конечно, нет. Какое же это решение?!

Автор. Продолжив цепочку вычислений, начатую в конце предыдущего параграфа, легко убедиться, что в 3-м перекрестке 4-го ряда побывает 2998 человек. Ответ «2998» будет решением задачи?

Читатель (еще не видя подвоха). Да, конечно.

Автор. Но ведь выражение «2998» не есть запись числа в десятичной системе счисления. Это выражение состоит из двух десятичных записей чисел, «2» и «998», относительное расположение которых показывает, какую операцию следует произвести с этими числами, чтобы получить нужное значение.

Читатель. Но выражение «2998» легко превратить в десятичную запись.

Автор (назидательно). Не так-то легко. Попробуйте-ка возвести 2 в 998-ю степень. Но дело даже не в этом, а в том, что Вы противоречите сейчас своим прежним заявлениям. Вы ведь сами соглашались считать решением лишь число, записанное в десятичной системе. С точки зрения этого определения, выражение «2998» еще не является решением (это, так сказать, «полуфабрикат», из которого решение должно быть изготовлено). Такая точка зрения, конечно, возможна, если только ее последовательно проводить. Но возможна и другая точка зрения, согласно которой 2998 — решение. Такая точка зрения Вам, вероятно, будет больше импонировать — ведь довольно часто ответы на те или иные математические задачи даются не прямо в виде чисел, записанных в десятичной системе, а в аналогичной «косвенной» форме. Но все же на каком понимании термина «решение» надлежит остановиться в нашем случае — для задачи о 3-м перекрестке 4-го ряда?

Читатель. В нашем случае решением надо считать всякое выражение, обозначающее какое-то число, для которого (выражения, а не числа) есть способ, позволяющий перейти от этого выражения к десятичной записи соответствующего числа. 2998 будет именно таким выражением. Способ перехода к десятичной записи (997 последовательных умножений) хотя и долгий, но в принципе осуществимый.

Автор. А почему тогда Hl не решение? Здесь тоже есть способ перехода к десятичной записи. Он задается соотношениями (1.1) — (1.4).

Читатель (растерян).

Автор (доволен, что ему удалось загнать читателя в тупик, — неискушенного читателя, конечно; искушенный сам загонит автора в тупик). Дело в том, что возможны по крайней мере три понимания того, что такое решение задачи о числе людей, побывавших на данном перекрестке:

ПЕРВОЕ ПОНИМАНИЕ. Решением считается число, записанное в десятичной системе счисления.

ВТОРОЕ ПОНИМАНИЕ. Решением считается такое обозначающее число выражение, для которого известен способ, позволяющий перейти от этого выражения к десятичной записи обозначенного им числа (т. е. к решению в первом понимании).

ТРЕТЬЕ ПОНИМАНИЕ. Решением считается такое обозначающее число выражение, которое составлено из чисел (записанных в десятичной системе) и некоторых операций, считающихся стандартными (например, арифметических действий)1). Потребуем, чтобы каждая стандартная операция сопровождалась способом, позволяющим переходить от десятичных записей чисел, к которым она применяется, к десятичной записи результата (именно таковы, например, арифметические действия). Тогда и для всего выражения в целом будет существовать способ, позволяющий перейти от десятичных записей участвующих в нем чисел к десятичной записи обозначаемого этим выражением числа, — так что решение в третьем понимании автоматически будет решением во втором понимании.

При первом понимании ни Н\, ни 2т не являются решением задачи о третьем перекрестке четвертого ряда. Чтобы получить решение, надо найти для 2998 десятичную запись; эта запись, однако, должна содержать свыше 300 знаков, и автору неизвестно, была ли она когда-либо написана2).

При втором понимании и Я? и 2998 будут решениями.

Что же касается третьего понимания, то здесь все зависит от выбора исходных стандартных операций: если в их число включается возведение в степень, то 2998 будет решением, если не включается, то не будет. Точно так же, если включить в число стандартных операций операцию «аш», вычисляющую по п и k число Нкп (а способ такого вычисления задают соотношения (1.1) — (1.4), так что требование, наложенное нами на стандартные операции, здесь выполнено), то Н\ будет решением задачи; в противном случае — не будет.

Возникает вопрос, произвольно ли мы можем выбирать стандартные операции. Формально говоря, да. А не-

1) Набор стандартных операций должен быть указан заранее. Полезно подчеркнуть, что третье понимание зависит от выбора этого набора. Так, выражение 2998 будет служить решением при третьем понимании, только если в число стандартных операций включено возведение в степень.

2) В книге: Литцман В. Великаны и карлики в мире чисел.— М.: Физматгиз, 1959, с. 27 в качестве наибольшей из вычисленных степеней числа 2 приводится — в десятичной записи — 2400,

формально, конечно, в качестве стандартных операций— через которые нужно выражать решение любой задачи! — следует выбирать такие операции, которые встречаются при решении многих задач или, если уж не многих, то важных. Именно таковы четыре арифметических действия и некоторые другие операции, например, операция возведения в степень и операция взятия факториала (о последней см. ниже, § 8). Если бы операция «аш» была нужна для разных задач или если бы сама наша задача о перекрестках была очень важной, то операцию «аш», пожалуй, стоило бы отнести к числу стандартных. Однако операция «аш» пока этого не заслужила и вряд ли заслужит. В § 5 мы рассмотрим одну сходную с «аш» операцию, которая, как нам кажется, заслуживает быть включенной в число стандартных.

А сейчас вернемся к нашей первоначальной задаче о перекрестках тысячного ряда. Ее решение можно искать в трех разных видах, соответствующих трем изложенным выше пониманиям слова «решение»:

1) в виде строчки из 1001 числа, записанного в десятичной системе; не будем искать решение в таком виде (куда уж нам, когда мы для одного перекрестка четвертого ряда и то не можем найти решение в такой форме);

2) в виде выражения, позволяющего в принципе для каждого перекрестка тысячного ряда вычислить число (т. е. найти десятичную запись числа) пришедших в него людей; такое решение мы уже нашли: //fooo» причем процесс вычисления задается равенствами (1.1) — (1.4);

3) в виде выражения, не только позволяющего вычислять #îooo при любом k от 0 до 1000, но образованного с помощью некоторых стандартных операций; в таком виде мы и будем пытаться найти решение; какие именно операции при этом будут считаться стандартными, станет ясным из дальнейшего изложения.

§ 3. ТРЕУГОЛЬНИК ПАСКАЛЯ

Рассмотрим какую-нибудь строчку чисел rf0, du ... .., dn, n = 0, 1, 2, ... (при n = 0 эта строчка «вырождается» в строчку, состоящую из единственного числа

do). Образуем из нее новую строчку чисел по следующему правилу:

(3.1) (3.2) (3.3)

Про эту новую строчку будем говорить, что она получена из предыдущей по закону Паскаля1). Например, из строчки 2, 0, —2 по закону Паскаля получается строчка 2, 2, —2, —2, а из этой, в свою очередь, 2, 4, 0, —4, —2.

Замечание 1. Если строчка ß получена из строчки а по закону Паскаля, то сумма членов строчки ß равна удвоенной сумме членов строчки а. Действительно, если выполняются соотношения (3.1) — (3.3), то

(3.4)

Замечание 2. Назовем строчку чисел do, •.., dn симметричной, если при любом целом k от 0 до п имеет место равенство

(3.5)

Строчка чисел 50, sn+\, получающаяся по закону Паскаля из симметричной строчки do, ..., dn, сама является симметричной. Для обнаружения этого надлежит проверить равенство

(3.6)

1) Паскаль, Блез (Pascal, Blaise) (1623—1662) —великий ученый Франции. Паскаль, в частности, исследовал свойства треугольной числовой таблицы, каждая строка которой получается из предыдущей по закону, задаваемому соотношениями (3.1) — (3.3). Эта таблица, которую мы еще будем рассматривать ниже, получила общепринятое наименование «треугольник Паскаля». Поэтому закон, положенный в основу ее образования, мы назовем законом Паскаля, а ее строки — строками Паскаля.

при k = О, 1, ..., n + 1. Но при k = 0 и k = п + \ равенство (3.6) вытекает из соотношений (3.1), (3.3) и равенства do = dn (получающегося из (3.5) при ft = 0). Если же 1 k ^ /2, то имеем:

(3.7)

Рассмотрим теперь строку, состоящую из одного числа — единицы. Назовем эту строку нулевой строкой Паскаля. Образуем из нее по закону Паскаля новую строку, которую назовем первой строкой Паскаля. Из первой строки Паскаля по закону Паскаля образуем вторую строку Паскаля и т. д. Поскольку при переходе к каждой следующей строке число членов этой строки возрастает на единицу, то в п-й строке Паскаля будет п + 1 число. Не производя никаких вычислений, а лишь принимая во внимание замечания 1 и 2, можно утверждать, что

1) сумма чисел п-й строки Паскаля равна 2п (потому что при переходе от каждой строки к следующей сумма членов удваивается, а для нулевой строки она равна 2°=1);

2) все строки Паскаля симметричны (потому что при переходе от каждой строки к следующей свойство симметричности сохраняется, а нулевая строка симметрична).

Запишем строки Паскаля, начиная с нулевой, друг под другом, так чтобы каждое число каждой строки оказалось между теми числами предыдущей строки, суммой которых оно является. Мы получим бесконечную таблицу, называемую арифметическим треугольником Паскаля, а также просто арифметическим треугольником, или треугольником Паскаля. Вся таблица в целом как бы заполняет внутренность некоторого угла; любое ее начало, образованное 0-й, 1-й, п-й строками, имеет форму равнобедренного треугольника. На стр. 15 выписано начало треугольника Паскаля, образованное первыми его 15 строками от нулевой до четырнадцатой. Вследствие симметрии строк Паскаля, треугольник Паскаля симметричен относительно своей биссектрисы.

Члены каждой строки Паскаля обычно нумеруются слева направо, начиная с нулевого. Так, второе место в пятой строке занимает число 10. Число, стоящее на k-ы месте в п-н строке, будем обозначать через Г„, так что, например, Го=1, 71=10, Ги=1001. Выражение Тп определено, очевидно, при любом п^О и k = 0, 1, ..., п.

В этих обозначениях подмеченные выше два свойства строк Паскаля могут быть записаны так:

(3.8) (3.9)

Впоследствии мы обнаружим еще два свойства строк Паскаля:

(3.10) (3.11)

В силу своего определения числа Тп подчинены следующим соотношениям:

(3.12) (3.13)

(3.14)

Этими соотношениями числа Тп полностью задаются; пользуясь равенствами (3.12) — (3.14), можно построить сколько угодно строк треугольника Паскаля.

Выражение Тп можно естественным образом доопределить так, чтобы оно было осмыслено при любом целом неотрицательном п и любом целом k. Для этого положим Гл = 0, если tt>0, а 4 таково, что для него не выполнено хотя бы одно из двух неравенств: 0<è и Таким образом, Т* = 0 для всех пар (я, k), у которых п^О, k < 0, и всех пар (п, k)> у которых п^О, k>n. Теперь соотношение Тп = Т*~{ + Т* будет выполняться для всех k (а не только для k от 1 до п9

как в (3.14)), и числа Тп будут полностью задаваться следующими равенствами:

(3.15) (3.16) (3.17)

Сказанное позволяет дать следующую наглядную картину возникновения треугольника Паскаля. Рассмотрим бесконечную таблицу, составленную из нулей, расположенных в шахматном порядке, как показано ниже:

... 0 0 0 0 ... ... 0 0 0 0 0 ...

... 0 0 0 0 ... ... 0 0 0 0 0 ...

Разумеется, для такой таблицы будет выполняться закон Паскаля, заключающийся в том, что каждое число является суммой двух ближайших к нему чисел предыдущей строки1). Представим себе теперь, что в начальной строке этой таблицы один из нулей заменился на единицу. Если мы потребуем, чтобы закон Паскаля сохранялся, то «возмущение» будет «распространяться углом», подобно волнам от воткнутой в ручей палки — в виде треугольника Паскаля:

... 0 0 1 0 0 ... .... 0 0 1 1 0 0 ....

... 0 1 2 1 0 ... .... 0 13 3 10 ....

Треугольник Паскаля при расположении его членов, рассмотренном выше (как на стр. 15), естественно называть треугольником Паскаля в равнобедренной форме,

1) Будем считать, что бесконечная строка

получена из бесконечной же строки

по закону Паскаля, коль скоро sk = dk-i + dk при каждом k. Тогда определение закона Паскаля для конечных строк получается отсюда, если каждую конечную строку

отождествить с бесконечной строкой

или, короче, равнобедренным треугольником Паскаля. Часто бывает удобным расположить члены треугольника несколько иначе, чтобы каждое начало имело форму прямоугольного треугольника. Такую бесконечную таблицу естественно называть треугольником Паскаля в прямоугольной форме, или просто прямоугольным треугольником Паскаля. В прямоугольном треугольнике Паскаля на пересечении п-й горизонтали и k-й вертикали (при том, что счет идет с нулевой горизонтали и нулевой вертикали) стоит число Г*:

На п-и горизонтали здесь располагается п-я строка Паскаля; числа, стоящие на фиксированной вертикали, также достойны изучения (см. ниже § 4). Помимо вертикалей и горизонталей, в прямоугольном треугольнике Паскаля легко прослеживаются диагонали. Различают восходящие диагонали (они выделены в приведенной только что таблице) и нисходящие диагонали. По главной нисходящей диагонали стоят единицы; по каждой из параллельных ей нисходящих диагоналей располагается— в силу симметрии строк Паскаля — та же последовательность чисел, что и по соответствующей вертикали; поэтому рассмотрение бесконечных рядов чисел, расположенных на нисходящих диагоналях, не дает ничего нового. Восходящие диагонали нумеруются, начиная с первой. На каждой из них стоит конечный ряд чисел: на первой диагонали 1; на второй 1; на третьей 1, 1; на четвертой 1, 2; на пятой 1, 3, 1 и т. д. Вообще, на п-й диа-

гонали стоят числа Тп-\, Тп-ъ •••» Tn+k (они продолжаются до тех пор, пока k ^ п— 1 — k, т. е. k ^

Замечание 3. Из двух чисел пятой горизонтали — 10 и 5 — по закону Паскаля получается число 15 шестой горизонтали. Эти числа 10, 5, 15 расположены соответственно на девятой, десятой и одиннадцатой восходящих диагоналях. Легко видеть, что, вообще, любое число (п + 2)-й диагонали, кроме самых крайних единиц, является суммой двух чисел, находящихся на двух предшествующих диагоналях, п-й и (п+1)-й; оговорка относительно крайних единиц станет излишней, если мы продолжим n-ю и (п+1)-ю диагонали некоторым количеством нулей (возникающих в силу сделанного выше доопределения выражения Ткп). При этом для различных чисел (п + 2)-й диагонали образующие их пары чисел двух предыдущих диагоналей не имеют между собой общих членов, и все такие пары путем суммирования их членов участвуют в образовании чисел (п + 2)-й диагонали. Поэтому сумма чисел (п + 2)-й диагонали равна сумме чисел п-й диагонали, сложенной с суммой чисел (п+ 1)-й диагонали.

§ 4. НЕМНОГО ИСТОРИИ

Способ образования треугольника Паскаля можно было бы, конечно, задать и не прибегая к понятиям «закон Паскаля» или «строка Паскаля»: треугольник Паскаля — это просто бесконечная числовая таблица «треугольной формы», в которой по боковым сторонам стоят единицы и всякое число, кроме этих боковых единиц, получается как сумма двух предшествующих чисел. В такой форме треугольник Паскаля появился в сочинении Паскаля «Трактат об арифметическом треугольнике», изданном в 1665 г. уже после смерти автора. Более точно, в указанном сочинении была опубликована следующая таблица1), в которой каждое число А равно

1) См. Pascal В. Oeuvres complètes, t. III. — Paris: Hachette et C,e, 1908, p. 244.

сумме предшествующего числа в том же, что и Л, горизонтальном ряду, и предшествующего числа в том же, что и Л, вертикальном ряду:

Таким образом, наш равнобедренный треугольник Паскаля отличается от «треугольника», рассматривавшегося самим Паскалем, поворотом на 45°.

Паскаль подробно исследовал свойства и применения своего «треугольника»; некоторые из применений будут рассмотрены в следующих параграфах. Сейчас мы приведем для примера лишь три свойства «треугольника», найденные самим Паскалем; при этом мы (только в этом месте нашего изложения!) будем исходить из того расположения «треугольника» на плоскости, которое было указано Паскалем, и говорить о горизонтальных и вертикальных рядах.

Свойство 1. Каждое число А в таблице равно сумме чисел предшествующего горизонтального ряда, начиная с самого левого вплоть до стоящего непосредственно над числом А (см. рис. 3, в котором клетки, содержащие слагаемые, дающие в сумме Л, заштрихованы).

Свойство 2. Каждое число А в таблице равно сумме чисел предшествующего вертикального ряда, начиная с самого верхнего вплоть до стоящего непосредственно левее числа А (рис. 4).

Свойство 3. Каждое число А в таблице, будучи уменьшено на единицу, равно сумме всех чисел, заполняющих прямоугольник, ограниченный теми вертикальным и горизонтальным рядами, на пересечении которых стоит число А (сами эти ряды в рассматриваемый прямоугольник не включаются) (рис. 5).

Доказательство этих свойств предоставляем читателю (указание; третье свойство легко вывести из первых двух).

Однако еще за столетие до выхода в свет трактата Паскаля его таблица — только не в «треугольной», а в «прямоугольной» форме — была опубликована в «Общем трактате о числе и мере» (1556—1560), вышедшем частично также только после смерти его автора, которым был выдающийся итальянский математик Никколо Тарталья. Таблица Тартальи имела следующий вид1):

Здесь верхняя строка состоит из единиц; в каждой из остальных строк самое левое число есть единица, а каждое следующее число образуется посредством сложения двух чисел, стоящих непосредственно перед ним и над ним. Таблицу, предложенную Тартальей, естественно было бы называть прямоугольником Тартальи.

За два с половиной века до Тартальи другой выдающийся итальянский математик — Леонардо из Пизы, более известный сейчас под именем Фибоначчи, — написал свою знаменитую «Книгу об абаке2)». Одна из задач этой книги — задача о размножении кроликов — приводила к последовательности чисел 1, 1, 2, 3, 5, 8, 13,

Рис. 3.

Рис. 4.

Рис. 5.

1) См. Цейтен Г. Г. История математики в XVI и XVII веках, пер. с немецкого.—М.; Л.: ГОНТИ, 1938, с. 116.

2) Абак — счетная доска.

21,..., в которой каждый член, начиная с третьего, представляет собой сумму двух предыдущих членов. Эта последовательность носит название ряда Фибоначчи; члены ряда Фибоначчи называются числами Фибоначчи1). Обозначая п-е число Фибоначчи через ип, имеем по определению и\ = 1, и% = 1, ип+2 = ип + ип+\ при п > 1.

Между рядом Фибоначчи и треугольником Паскаля существует любопытная связь. Образуем для каждой восходящей диагонали прямоугольного треугольника Паскаля сумму всех стоящих на этой диагонали чисел. Получим для первой диагонали 1, для второй 1, для третьей 2, для четвертой 3, для пятой 5. Мы получили не что иное, как пять начальных чисел Фибоначчи. Оказывается, что всегда сумма чисел п-й диагонали есть п-е число Фибоначчи. Действительно, для п — 1 и п = 2 совпадение усматривается непосредственно, для дальнейших значений п совпадение обеспечивается тем, что (см. замечание 3 в конце § 3) суммы, вычисленные для любых двух последовательных диагоналей, будучи сложены друг с другом, дают сумму, вычисленную для диагонали, непосредственно следующей за этими двумя. Нетрудно показать2), что сумма п первых чисел ряда Фибоначчи равна ип+2—1. Поэтому сумма всех членов треугольника Паскаля, лежащих как на самой n-й диагонали, так и выше этой диагонали, равна ип+2— 1-

Ряды чисел, заполняющих отдельные вертикали прямоугольного треугольника Паскаля, волновали умы математиков в еще более ранние времена.

На k-k вертикали прямоугольного треугольника Паскаля стоят числа

В прямоугольнике Тартальи эти числа заполняют &-й столбец, а также fc-ю строку.

При k = О получаем последовательность

1, 1, b 1, 1, 1,

1) Свойства ряда Фибоначчи и составляющих его чисел подробно излагаются в брошюре: Воробьев H. Н. Числа Фибоначчи (серия «Популярные лекции по математике», Вып. 6). — М.; Л.: Гостехиздат, 1951; изд. 2-е. — М.: Наука, 1964; изд. 3-е. — М.: Наука, 1969; изд. 4-е. —М.: Наука, 1978.

2) См. указанную в предыдущей сноске брошюру H. Н. Воробьева, § 1, п. 1,

состоящую из одних единиц (нулевая строка или нулевой столбец прямоугольника Тартальи).

При k = 1 получаем натуральный ряд

1, 2, 3, 4, 5, 6, ...

(первая строка или первый столбец прямоугольника Тартальи). При k = 2 получаем последовательность

1, 3, 6, 10, 15, 21, ...

(вторая строка или второй столбец прямоугольника Тартальи). Члены этой последовательности называются треугольными числами: 1 — первое треугольное число, 3 — второе треугольное число, 6 — третье и т. д.; т-е треугольное число равно Т2п+{. Такое название дано им потому, что эти числа указывают количества шаров или иных одинаковых предметов, уложенных в виде треугольника (см. рис. 6); т-е треугольное число, в частности, показывает, сколько членов треугольника Паскаля содержится в первых m его строках — от нулевой до (m— 1)-й. (Укладки шаров в виде квадрата характеризуются квадратными, или четырехугольными, числами: 1, 4, 9, 16, 25, 36, в виде пятиугольника — пятиугольными числами: 1, 5, 12, 22, 35, 51, ... и т. д.)

Положив k = 3, получим последовательность

1, 4, 10, 20, 36, 56, ...

(третья строка или третий столбец прямоугольника Тартальи). Члены этой последовательности называются пирамидальными числами или, более точно, тетраэдрическими числами: 1 — первое тетраэдрическое число, 4 — второе, 10 — третье и т. д., так что т-е тетраэдрическое число равно 7^+2- Эти числа показывают, сколько шаров может быть уложено в виде треугольной пирамиды (тетраэдра) (рис. 7).

Многоугольные и пирамидальные числа (и те и другие являются частными случаями так называемых фигурных чисел) вызывали интерес еще в Древней Греции, где им приписывались мистические свойства. Наиболее ранним из дошедших до нас сочинений, в котором рассматриваются эти числа, является, по-видимому, «Введение в арифметику» древнегреческого математика Никомаха из Геразы,

Рис. 6.

жившего около 100 г. н. э.1). Впрочем, по косвенным данным, многоугольные числа были известны значительно раньше, во II в. до н. э.2) и даже еще ранее, в V в. до н. э., знаменитому математику Пифагору и его ученикам — пифагорейцам3).

Рис. 7.

§ 5. ОПЕРАЦИЯ ПАСКАЛЯ

Задавшись произвольными пик (п = 0, 1, 2, k = 0, 1, я), можно, если располагать достаточными временем и терпением, найти Г*. Для этого надо начать выписывать треугольник Паскаля и продолжать до тех пор, пока мы не дойдем до k-ro числа п-й строки. Или же можно просто воспользоваться соотношениями (3.12) — (3.14); эти соотношения позволят, совершив конечное число сложений, найти Г„.

Задача (для самостоятельного решения читателем). Сколько сложений надо произвести, чтобы, применяя соотношения (3.12) — (3.14), вычислить Г„? (Постарайтесь уменьшить число этих сложений, воспользовавшись симметрией треугольника Паскаля.)

1) См. Стройк Д. Я. Краткий очерк истории математики, пер. с немецкого. — М.: Наука, 1978, с. 77; ван дер Варден Б. Л. Пробуждающаяся наука, пер. с голландского. — М.: Физматгиз, 1959, с. 134, 136; Цейтен Г. Г. История математики в древности и в средние века, пер. с французского. — М.; Л.: ГОНТИ, 1938, с. 164.

2) См. указанную в предыдущей сноске книгу Б. Л. ван дер Вардена, с. 364.

3) См. с. 132 названной книги Б. Л. ван дер Вардена, с. 37 названной книги Г. Г. Цейтена, с. 59 названной книги Д. Я. Стройка.

Операцию, состоящую в нахождении по числам пик числа Тп, условимся называть операцией Паскаля. Операция Паскаля определена для любых п и А, для которых я^О, 0 ^ k ^ n1). А если доопределить Г* так, как было указано выше на стр. 16, то операция Паскаля будет определена для любого целого неотрицательного п и для любого целого k.

При помощи операции Паскаля легко записываются числа Нп, служащие ответом на олимпиадную задачу из § 1. С целью найти такую запись положим (для m = 0, 1, 1000; q = 0, 1, ..., m)

(5.1)

так что

(5.2)

Тогда из соотношений (5.1) и (1.1) получаем

(5.3)

Подставим в соотношения (1.2), (1.4) и (1.3) вместо чисел Hm их выражения через Zqm согласно (5.2). Мы получим из (1.2)

откуда

(5.4)

Точно так же мы получим из (1.4)

откуда

(5.5)

1) Сам Паскаль, впрочем (исходя из предложенного им расположения таблицы на плоскости — см. с. 20), рассматривал в своем трактате другую операцию, а именно, операцию нахождения по числам X и у числа, стоящего на пересечении х-го вертикального ряда и У'ГО горизонтального ряда (при нумерации рядов, начиная с первого, так что эта операция определена при х ^ 1, у ^ 1). Если обозначить искомое число через Р(х,у), то, как легко обнаружить,

Наконец, из (1.3) мы получим

откуда

(5.6)

Равенства (5.4) — (5.6) показывают, что каждая строка

где п = 0, 1, 999, получается из предшествующей строки

по закону Паскаля. Поскольку, как видно из равенства (5.3), начальная строка

есть нулевая строка Паскаля, то следующая за ней строка (ôi есть первая строка Паскаля, строка ©2 есть вторая строка Паскаля и т. д.; при каждом m от 0 до 1 ООО1) строка cûm есть m-я строка Паскаля, и

(5.7)

Следовательно, в силу (5.2), при каждом m = 0, 1, ... ..., 1000 и каждом k = 0, 1, ..., m

(5.8)

В частности,

(5.9)

Итак, количества людей, пришедших на перекрестки тысячного ряда, суть не что иное, как члены тысячной же строки Паскаля. Если считать операцию Паскаля стандартной операцией, то равенство (5.9) даст решение задачи из § 1 (в третьем из видов, указанных в конце § 2). В следующих двух параграфах мы увидим, как при помощи операции Паскаля можно найти решения двух важных задач.

1) При m > 1000 строка <ûm не определена.

§ 6. БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ

В этом параграфе мы покажем, как при помощи операции Паскаля можно выразить так называемые биномиальные коэффициенты. Биномиальные коэффициенты определяются следующим образом.

Возьмем бином 1 + х и начнем возводить его в степени 0, 1, 2, 3 и т. д., располагая получающиеся при этом многочлены по возрастающим степеням буквы х. Мы получим

(6.1) (6.2) (6.3) (6.4)

и т. д.

Вообще для любого целого неотрицательного числа п

(6.5)

где ао, аь .... ар— некоторые числа. При желании было бы нетрудно убедиться, что р — п и а0 = ар= 1. Однако нам это сейчас не нужно. Мы получим это несколько позже как следствие более общей формулы. На данном этапе нам достаточно знать, что результат возведения бинома 1 +х в степень п (где п — целое неотрицательное число) можно записать в виде расположенного по возрастающим степеням буквы х многочлена с числовыми коэффициентами, как показано в соотношении (6.5). Многочлен, стоящий в правой части этого соотношения, называется разложением бинома для показателя п. Его коэффициенты (и их количество р) зависят, конечно, от п. Чтобы подчеркнуть эту зависимость, часто используют специальные обозначения для этих коэффициентов, в состав которых входит п. Именно, коэффициент при xk в разложении бинома для показателя п

обозначается через ( ^ ) • Числа ( £ ) и называются

биномиальными коэффициентами.

Соотношение (6.5) можно переписать теперь в виде

(6.6)

а из соотношений (6.1) — (6.4) получаем

Мы видим, что для показателей /1 = 0, 1, 2, 3 строки биномиальных коэффициентов совпадают соответственно с 0-й, 1-й, 2-й и 3-й строками треугольника Паскаля. Сейчас мы убедимся, что это верно при всяком #п. С этой целью посмотрим, как строчка коэффициентов для показателя п + 1 получается из строчки коэффициентов для показателя п. Воспользуемся формулой

(1+х)п+1 = (\+х)п(1+х). (6.7)

Выпишем для левой и правой частей этой формулы разложения по возрастающим степеням буквы х. Для левой части формула (6.6) дает — при замене п на п+ 1:

(6.8)

где q — некоторое число. Для правой части в силу той же формулы (6.6) имеем:

(6.9)

В силу (6.7) правые части соотношений (6.8) и (6.9) равны друг другу. Поэтому q = р + I; приравнивая коэффициенты при одинаковых степенях буквы х, получим

(6.10) (6.11) (6.12)

Соотношения (6.10) — (6.12) показывают, что строка коэффициентов разложения для показателя п+1 получается из строки коэффициентов разложения для показателя п по закону Паскаля. Поскольку строка коэффициентов разложения для показателя 0 совпадает с нулевой строкой Паскаля, то все последующие строки коэффициентов будут также совпадать с соответствующими строками треугольника Паскаля. Поэтому числа ( ? ) определены лишь при k = 0, 1, ..., n, причем

(6.13)

Замечание. На вопрос, «с какими коэффициентами входят х~3 и X20 в разложение бинома для показателя 5?», можно ответить: «с коэффициентами, равными нулю». Поэтому естественно доопределить выражение ( £ ) на случай k < 0 и k > пу полагая в этих случаях (^) = 0. Тогда равенство (6.13), в силу сделанного в предыдущем параграфе доопределения символа Г„, будет справедливо при всех неотрицательных п и всех целых k.

Итак, мы выразили биномиальные коэффициенты через операцию Паскаля. Соотношение (6.6) мы можем теперь переписать следующим образом:

(6.14)

Формулу (6.14) иногда называют формулой бинома Ньютона или просто биномом Ньютона1). Другой, более традиционный вид этой формулы будет указан в § 8.

Можно считать, что в настоящем параграфе мы рассматривали следующую «задачу о биномиальных коэффициентах»: найти выражение для (^)- Как мы знаем из § 2, можно по-разному понимать, что является решением для задачи подобного рода. Если, например, решением считать выражение, позволяющее от п и k перейти к соответствующему биномиальному коэффициенту

(в десятичной записи), то само будет таким решением. Будем требовать, чтобы решение выражало через числа n, k и стандартные операции; такое понимание решения будет зависеть от выбора стандартных операций. Если считать стандартной операцию Паскаля, то формула (6.13) даст решение задачи о биномиальных коэффициентах. Другое решение этой задачи — при других стандартных операциях — будет приведено в § 8.

Положим в тождестве (6.14) х = —1. Мы получим объявленное в § 3 равенство (3.10).

Теорема. Пусть /, m, п—целые неотрицательные числа. Тогда

(6.15)

Доказательство. Тождественное равенство

(6.16)

перепишем, согласно (6.14), в виде

(6.17)

1) Формула (6.14) была известна задолго до Ньютона — в частности, уже упоминавшемуся Тарталье. Имя Ньютона связывается с обсуждаемой формулой лишь потому, что он указал в 1676 г. способ обобщения этой формулы на случай произвольного рационального (в том числе отрицательного) показателя. Если к треугольнику Паскаля и биному Ньютона прибавить еще и формулу Кардано, служащую для нахождения корней кубического уравнения — а, как известно, Дж. Кардано, опубликовавший эту формулу, узнал ее от Тартальи, дав клятву не разглашать, — то следует признать, что посмертная судьба Тартальи была несколько несправедлива к его имени.

Подсчитаем коэффициент при х1 в каждой из частей этого равенства. Коэффициент в левой части равен левой части соотношения (6.15), а коэффициент в правой части равен правой части того же соотношения. Приравнивая эти коэффициенты, и получаем (6.15). Теорема доказана.

Следствие. (Г°„)2 + (Л)2 + ... + (П)2 = Тп2п. (Это -обещанное равенство (3.11) из § 3.)

Доказательство. В (6.15) полагаем 1 = щ = п и принимаем во внимание (3.9).

Важное замечание. В этом параграфе мы неоднократно опирались на следующий основной факт теории многочленов действительной переменной: если два многочлена от переменной х тождественно равны, т. е. равны при всех действительных значениях переменной х, то у этих многочленов равны и коэффициенты при одинаковых степенях х. Мы использовали этот факт, когда только что приравнивали коэффициенты при х1 в левой и правой частях тождества (6.17) и еще раньше, когда делали то же самое для тождества (6.9). Более того, на этот факт мы опирались при самом определении биномиальных коэффициентов, предполагая, что разложение (6.6) задает их однозначно. Чтобы обосновать указанный основной факт, достаточно установить его частный случай, когда один из двух многочленов есть просто О, т. е. установить следующее утверждение: если многочлен тождественно равен нулю, то все его коэффициенты равны нулю; действительно, если это утверждение верно, то, образовав разность двух тождественно равных друг другу многочленов, мы получим многочлен, тождественно равный нулю и, следовательно, имеющий нулевые коэффициенты, — а это значит, что коэффициенты исходных многочленов совпадали. Набранное курсивом утверждение равносильно, в свою очередь, следующей лемме.

Лемма. Пусть многочлен имеет хотя бы один ненулевой коэффициент. Тогда существует такое значение переменной, при котором значение многочлена отлично от нуля.

Доказательство леммы. Пусть п—наибольшее из таких чисел m, что коэффициент при хт отличен от нуля. (Такое число п называется степенью многочлена.) Наш многочлен Р(х) имеет, следовательно, вид апхп + an-ixn-1 + ... + а\х + a0f где ап Ф 0. Возьмем

любое действительное число а такое, что одновременно

(6.18) (6.19)

Покажем, что Р{а)Ф 0. В самом деле, из (6.18)

(6.20)

а из (6.20) и (6.19)

(6.21)

В силу (6.18), число а положительно; поэтому из (6.21)

(6.22)

Поскольку

(6.23)

достаточно обнаружить, что выражение в скобках отлично от нуля; докажем, что оно положительно. В самом деле, в силу (6.22)

(6.24)

§ 7. ЧИСЛО ЧАСТЕЙ ДАННОГО МНОЖЕСТВА

Всякая совокупность предметов называется в математике множеством. Так, например,

а) совокупность всех страниц настоящей брошюры;

б) совокупность всех целых чисел;

в) совокупность всех четных чисел;

г) совокупность всех карандашей в какой-либо данной коробке

— все это будут множества.

Если указаны некоторый предмет и некоторое множество, то могут быть два случая:

1) рассматриваемый предмет принадлежит рассматриваемому множеству;

2) рассматриваемый предмет не принадлежит рассматриваемому множеству.

В первом случае рассматриваемый предмет называется элементом рассматриваемого множества. Например, число 3 является элементом множества всех целых чисел и не является элементом множества всех четных чисел.

Может случиться, что все элементы некоторого множества А являются одновременно элементами некоторого другого множества В (так, например, все элементы множества всех четных чисел являются элементами множества всех целых чисел). В таком случае множество А называют частью, или подмножеством, множества В. Очевидно, каждое множество является частью самого себя. Если множество А является частью множества В и множество В является частью множества Л, то это значит, что А и В состоят из одних и тех же элементов, т. е. совпадают (являются «одним и тем же множеством») .

Множества бывают конечные (как множества из приведенных выше примеров а) и г)) и бесконечные (как множества из приведенных выше примеров б) и в)). Конечные множества (а только такими множествами мы будем заниматься в этом параграфе) составляют предмет изучения специальной математической дисциплины — комбинаторики.

Среди конечных множеств выделяется одно особое множество, а именно — множество, не содержащее никаких элементов; такое множество называется пустым. Так, не исключена возможность, что, открыв коробку, мы обнаружим, что множество заключенных в ней карандашей пусто. Вот что пишет о пустом множестве П. С. Александров1):

«Пустое множество, по определению, не содержит элементов; число элементов пустого множества есть нуль. Необходимость рассмотрения пустого множества видна из того, что когда мы определяем тем или иным способом множество, то мы можем и не знать заранее,

1) Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977, с. 7—8.

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

Если множество конечно, то его элементы можно пересчитать, найдя тем самым число элементов множества. Множество, состоящее из п элементов, называется «л-элементным». Множество страниц этой брошюры является, например, 48-элементным множеством, пустое множество является нульэлементным множеством.

Пример. Рассмотрим множество, состоящее из трех предметов: карандаша, пера и ластика. Найдем все его части. Имеется ровно одна нульэлементная часть — пустое множество. Имеются ровно три одноэлементные части:

Имеются ровно три двухэлементные части:

Наконец, имеется ровно одна трехэлементная часть (совпадающая со всем множеством):

Всего, таким образом, наше множество имеет восемь частей.

Пусть дано множество, состоящее из п элементов. Любая /^-элементная его часть называется сочетанием из заданных п элементов по А. Очевидно, что число сочетаний из заданных п элементов по k не зависит от того, какие именно п элементов заданы, а только от чисел п и k. Поэтому это число называют короче числом сочетаний из п элементов по k и обозначают

Иначе говоря, С* — это число Ä-элементных частей л-элементного множества. Выражение Chn обычно считают имеющим смысл при п — О, 1, 2, О ^ k ^ п. Впрочем, естественно считать, что выражение С* имеет смысл и при k > п и равно в этом случае нулю (так как в этом случае ^-элементных частей нет вовсе).

Число всех частей п-элементного множества будем обозначать через d, так что

(7.1)

Чему же равны числа сп> сп ? На некоторые из этих вопросов мы можем ответить сразу. Так, из разобранного только что примера вытекает, что С3 = 8, Сз =

Далее, имеет место следующее

Первое свойство числа сочетаний:

(7.2)

Доказательство. Действительно, т-элементное множество Е имеет ровно одну О-элементную часть (пустое множество) и ровно одну /л-элементную часть (само множество Е).

Установим теперь, не вычисляя самих чисел С„, еще три свойства этих чисел. Установление второго и четвертого свойств явится полезным упражнением на усвоение понятий, изложенных в этом параграфе; что же касается третьего свойства, то именно оно — вместе с первым — и ляжет в основу вычисления чисел С*.

Второе свойство числа сочетаний:

(7.3)

Доказательство. Возьмем какое-нибудь множество M из л элементов. Нам нужно доказать, что число его ^-элементных частей равно числу его (п — k) -элементных частей. Осуществим мысленно следующую конструкцию. Вырежем из бумаги столько квадратов, сколько имеется ^-элементных частей нашего множества (т. е. Сп), и на каждом из них изобразим одну из этих частей — так чтобы каждая /^-элементная часть была изображена на каком-то квадрате. Далее, вырежем из бумаги Сп"к кругов и каждую из (п — £)-элементных частей изобразим ровно на одном из этих кругов. Нам теперь достаточно обнаружить, что кругов и квадратов одинаковое количество. Для этого мы выложим все квадраты на стол и на каждый из них положим круг по следующему правилу: если на квадрате изображена некоторая часть множества М, составленная из k элементов, то на этот квадрат должен быть положен круг с изображением части множества М, составленной из остальных п — k элементов, т. е. из всех тех элементов множества М, которые не вошли в часть, изображенную на квадрате (на рис, 8 показано несколько квадра-

Рис. 8.

тов вместе с соответствующими им кругами для случая пятиэлементного множества М, составленного из элементов а, &, с, d, е). Очевидно, что на каждый квадрат ляжет ровно один круг и каждый круг будет положен ровно на один квадрат. А это и значит, что кругов столько же, сколько квадратов.

Прежде чем перейти к третьему свойству, докажем следующую лемму.

Лемма 1. Выделим в (n+ 1) -элементном множестве какой-то элемент. Число k-элементных частей этого множества, содержащих этот выделенный элемент, равно С^"1.

Доказательство. Снова проведем мысленный эксперимент с кругами и квадратами. Вырежем из бумаги столько квадратов, сколько есть /^-элементных частей, содержащих выделенный элемент, и на каждом из них изобразим одну такую часть, так чтобы все части были изображены. Вырежем из бумаги С*-1 кругов и на каждом круге изобразим одну из (ft—1)-элементных частей множества всех невыделенных элементов, так чтобы все такие части были изображены (невыделенных элементов n, поэтому таких частей как раз С*"1). Положим на каждый квадрат круг по следующему правилу: если на квадрате изображено некоторое множество Л, то на этот квадрат должен быть положен круг, несущий на себе изображение множества, полученного из А удалением выделенного элемента. Очевидно, что на каждый квадрат ляжет ровно один круг и каждый круг будет положен ровно на один квадрат. А это и значит, что квадратов столько же, сколько кругов, т. е. С»""1. Но ведь квадратов мы вырезали ровно столько, сколько есть ^-элементных частей (п + 1)-элементного множества, содержащих выделенный элемент. Значит, число таких частей равно С*"1, что и требовалось доказать.

Теперь перейдем к третьему свойству числа С*.

Третье свойство числа сочетаний:

(7.4)

Доказательство. Возьмем произвольное (n+ 1)-элементное множество M и составим все его £-элементные части. Выделим в M какой-нибудь элемент; обозначим этот элемент буквой а. Обозначим через X число тех

ft-элементных частей множества M, которые содержат элемент а, и через Y — число тех ^-элементных частей множества М, которые не содержат а. Тогда

(7.5)

Но по лемме X = Сп • Что же касается У, то это есть число сочетаний по k из п невыделенных элементов, т. е. Сп. Поэтому

(7.6)

что и требовалось доказать.

Четвертому свойству также предпошлем лемму.

Лемма 2. Пусть множество Е, содержащее т+п элементов, разбито на две непересекающиеся (т. е. не имеющие общих элементов) части M и N, содержащие соответственно m элементов и п элементов. Тогда число всех таких (р + q) -элементных частей множества Е, ко-* торые содержат в точности р элементов из M и в точности q элементов из N, равно Срт • Сяп.

Доказательство. Вырежем Срт кругов и на каждом изобразим одну из р-элементных частей множества М; вырежем Cqn квадратов и на каждом изобразим одно из ç-элементных частей множества N. Ясно, что соединяя круг с квадратом, мы получаем каждый раз некоторое подмножество множества Е, удовлетворяющее условиям леммы, и что каждое такое подмножество может быть «разложено на круг и квадрат» и притом единственным способом — в том смысле, что соответствующие круг и квадрат определяются выбранным подмножеством однозначно. Поэтому частей множества Е, удовлетворяющих условиям леммы, столько же, сколько можно образовать пар из кругов и квадратов — т. е. пар, у которых на первом месте стоит один из Срт кругов, а на втором — один из Cqn квадратов. Доказательство леммы 2 свелось к установлению следующего общего утверждения — одного из основных принципов комбинаторики, часто называемого правилом умножения.

Правило умножения. Пусть множество А содержит а элементов, а множество В содержит ß элементов. Тогда число всех таких пар (а,Ь), у которых на первом месте стоит какой-то элемент из А, а на втором — какой-то элемент из В, равно aß.

Доказательство правила умножения. Представим себе ß ящиков, на каждом из которых наклеен ярлык с обозначением одного из элементов множества В. Взяв какой-нибудь ящик, поместим туда все пары, у которых на втором месте стоит маркирующий этот ящик элемент множества В. В ящике окажется столько же пар, сколько может быть первых членов пары, а именно а. Итак, в каждом ящике лежит а пар, а всех ящиков ß; следовательно, число всех пар во всех ящиках равно

Замечание 1. При доказательстве правила умножения мы пользовались традиционным школьным определением умножения как суммирования одинаковых слагаемых. С тем же— и даже большим — успехом само правило умножения может служить определением операции умножения.

Четвертое свойство числа сочетаний:

(7.7)

Доказательство. Возьмем какое-нибудь (т + п)-элементное множество Е и изготовим карточки, на каждой из которых изобразим одну из /-элементных частей этого множества. Позаботимся, чтобы каждая часть была изображена, и притом ровно на одной карточке,— тогда число карточек окажется равным С1т+п. Это — левая часть соотношения (7.7). Теперь подсчитаем это же число другим способом. Разобьем Е на две непересекающиеся части M и N по m и п элементов в каждой. Возьмем /+ 1 ящиков и занумеруем их числами от 0 до /. В ящик с номером р поместим всякую такую карточку, что изображенное на ней подмножество содержит ровно р элементов из M — и, следовательно, ровно q элементов из N; в результате, в силу леммы 2, в ящике окажется Сртс1гр карточек. А число всех карточек во всех ящиках будет выражаться правой частью соотношения (7.7).

Следствие.

(7.8)

Доказательство. Достаточно положить в (7.7) / = пг = п и воспользоваться вторым свойством числа сочетаний.

Перейдем теперь к связи между числами сочетаний и треугольником Паскаля. Мы увидим сейчас, что числа Сп суть не что иное, как члены этого треугольника. В самом деле, третье свойство вместе с первым показывает, что строка

С°п+и С\+и ...» СпХ\ (7.9)

получается из строки

Cl Ci, .... CS (7.10)

по закону Паскаля. Поскольку при п = 0 строка

С°о (7.11)

совпадает, в силу (7.2), с нулевой строкой Паскаля, то и при произвольном п строка (7.10) будет совпадать с п-й строкой Паскаля, а потому

Ckn = Tkn. (7.12)

Итак, мы умеем теперь вычислять число ^-элементных частей п-элементного множества — число сочетаний из п элементов по k (формула (7.12) дает, таким образом, решение «Задачи о числе сочетаний» — при условии, что операция Паскаля считается стандартной1)).

Что же касается числа всех частей п-элементного множества, то соотношения (7.1) и (7.12) показывают, что это число равно сумме членов п-й строки Паскаля, каковая сумма, как мы знаем, равна 2п. Окончательно,

Сп = 2л. (7.13)

Замечание 2. Заменяя в (7.8) Сп на Г„, получаем новое доказательство соотношения (3.11).

§ 8. СВЯЗЬ С ФАКТОРИАЛАМИ

В § 5 были указаны два способа вычисления числа Т\ по заданным п и k: более «механический» (но зато приводящий к лишним вычислениям) способ постепенного выписывания треугольника Паскаля и более экономный по количеству действий (зато требующий из-

1) Другое решение —при других стандартных операциях — читатель найдет в § 8.

вестной организации вычислений) способ, состоящий в применении соотношений (3.12) — (3.14). Оба эти способа весьма близки друг другу и по существу непосредственно вытекают из задания чисел Г„ посредством закона Паскаля. Однако существует и совершенно другой способ для нахождения Tkn. Сейчас мы его укажем. Сначала введем одно обозначение. Положим

01 = 1,

а для всякого целого m

ml = (m — 1)! т.

Таким образом, при m > 0

ml = 1 • 2 ... m.

Выражение m! читается так: «факториал числа m» или короче: «m факториал».

Выразим теперь операцию Паскаля через операцию взятия факториала и арифметические операции. Для этого рассмотрим следующее выражение:

Обозначим такое выражение через Fqm. Очевидно, выражение Fmимеет смысл при m ^ 0, 0 ^ q ^ т. Заметим, что

Далее, Наконец,

Таким образом, строка

есть нулевая строка Паскаля, а (я+1)-я строка

получается из я-й строки

по закону Паскаля. Поэтому при любом m = О, 1, 2, ... строка

совпадает с т-и строкой Паскаля, и

Отсюда

Мы выразили, таким образом, операцию Паскаля через операции взятия факториала, вычитание, умножение и деление, в том смысле, что нашли для Тт выражение, содержащее, помимо m и q> только знаки указанных операций. Это дает возможность вычислить Тт> коль скоро мы умеем вычислять факториалы, разности, произведения и частные.

Из найденной только что формулы для Тт можно извлечь ряд следствий.

Следствие 1. Сокращая в найденном для Тт выражении числитель и знаменатель на (m — q)\, получаем

Следствие 2. Пусть m^l, l^q. Произведение q сомножителей m (m—1) ... [m — (q—1)] всегда делится на произведение q сомножителей 1-2 ... q.

Действительно, в силу следствия 1 отношение этих произведений равно Тт, а Тт — число целое.

Следствие 3. Из соотношения (5.9) получаем

Это новая форма решения задачи из § 1.

Следствие 4. Из соотношения (6.13) получаем

Это традиционное «школьное» выражение для биномиального коэффициента.

Следствие 5. Из соотношения (6.14) и следствия 1 выводим:

Это — традиционная «школьная» форма формулы бинома Ньютона.

Следствие 6. Соотношение (7.12) дает традиционную «школьную» формулу для числа сочетаний:

§ 9. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ ВНУТРЕННИХ ЧЛЕНОВ СТРОКИ ПАСКАЛЯ

Посмотрим еще раз на таблицу на с. 15 и возьмем какую-нибудь ее строку, например, предпоследнюю, 13-ю. Легко убедиться, что все ее члены, кроме крайних единиц, делятся на 13. Возникает гипотеза, что, вообще, все внутренние члены /п-й строки делятся на m (внутренними мы называем все члены строки, кроме крайних — нулевого и последнего, таким образом, в нулевой и первой строках Паскаля внутренних членов нет вовсе). Для проверки возьмем наугад еще какую-нибудь строку, например, 7-ю — и, действительно, все ее внутренние члены делятся на 7. Однако внутренние члены 6-й строки отнюдь не делятся на 6, а внутренние члены 14-й строки не делятся на 14; более того, в каждой из этих строк наибольший общий делитель всех внутренних членов равен единице. Пытаясь обнаружить разницу между числами 13 и 7, с одной стороны, и числами 6 и 14 — с другой, видим, что первые два суть числа простые, а вторые — составные. (Напомним, что целое число называется простым, если оно больше единицы и не имеет других делителей, кроме единицы и самого себя;

целое число называется составным, если оно больше единицы и не является простым.) Мы покажем, что все внутренние члены т-й строки Паскаля делятся на m тогда и только тогда, когда m — простое. Более того, мы выясним, когда, вообще, все внутренние члены п-й строки делятся на ш. Результаты наших рассуждений будут подытожены в виде теоремы, к которой мы придем, сформулировав (и впоследствии доказав) семь предложений; каждое из них может представить и самостоятельный интерес. Всюду в этих предложениях £, m, n, r, s — натуральные числа. Условимся также, для краткости, вместо того, чтобы говорить «все внутренние члены п-\\ строки Паскаля делятся на га», говорить просто «я-я строка Паскаля делится на га». Чтобы не обременять себя тривиальным случаем нулевой и первой строк (эти строки, конечно, делятся на что угодно), договоримся, что мы имеем дело лишь со строками, начиная со второй (в особенности это относится к предложениям 6 и 7).

Предложение 1. Пусть п-я строка Паскаля делится на га. Тогда п делится на га.

Предложение 2. Пусть s-я строка Паскаля делится на га. Тогда строка Паскаля с номером r s в том и только в том случае делится на га, если на га делится г-я строка.

Предложение 3. Пусть m-я строка Паскаля делится на га. Тогда п-я строка Паскаля в том и только в том случае делится на га, если п является степенью числа га, т. е. имеет вид mk.

(Предложение 3 позволяет указать номера всех строк Паскаля, делящихся, скажем, на 11. В самом деле, непосредственная проверка показывает, что 11-я строка делится на 11. А тогда заключаем, что на И делятся все строки с номерами вида 11* и только они.)

Предложение 4. Пусть р — простое число. Тогда р-я строка Паскаля делится на р.

Предложение 5. Пусть р — простое число. Тогда п-я строка Паскаля в том и только в том случае делится на р, если п является степенью числа р> т. е. имеет вид р*.

Предложение 6. Пусть га имеет хотя бы два различных простых делителя. Тогда никакая строка Паскаля не делится на га.

Предложение 7. Пусть р — простое число. Тогда никакая строка Паскаля не делится на р2.

Доказательства предложений 1—7 будут изложены несколькими строками ниже; однако мы рекомендуем читателю попытаться самостоятельно найти доказательства некоторых из этих предложений. А сейчас, опираясь на предложения 5—7, мы установим, какие именно строки Паскаля делятся на заданное число. Итак, фиксируем натуральное число m, большее единицы, и будем интересоваться тем, какие строки Паскаля делятся на это число. Среди отличных от единицы делителей числа m выберем наименьший делитель р, так что m = рт\. Если бы р делилось на некоторое число, заключенное строго между 1 и р, то, поскольку тогда m также делилось бы на это число, р не было бы наименьшим отличным от единицы делителем числа т. Поэтому р — число простое. Если Ш\ = 1, то m = р и номера всех строк, делящихся на р, исчерпываются, в силу предложения 5, степенями этого числа р. Если т\ > 1, то, действуя аналогично, находим, что т\ = qm2, где q — некоторое простое число. Если теперь р = q, то m делится на р2; и всякая делящаяся на m строка делится на р2\ поэтому, в силу предложения 7, таких строк не бывает. Если же рФ q, то m имеет два различных простых делителя, и потому, на этот раз в силу предложения 6, опять-таки не бывает строк, делящихся на т. Нами получена

Теорема. Строка Паскаля с номером п тогда и только тогда делится на ш, когда m — простое число, а п — степень этого простого числа. Другая формулировка: наибольший общий делитель всех внутренних членов п-й строки Паскаля равен р, если m есть степень простого числа р, и единице во всех остальных случаях.

Переходим к доказательству предложений 1—7.

Доказательство предложения 1 немедленно получается из того факта, что первый внутренний член п-ïi строки есть п.

Доказательству предложений 2—7 предпошлем следующую лемму.

Лемма 1. Пусть О ^ а ^ г и пусть s-я строка Паскаля делится на т. Тогда разность С™ — С{? делится на m2.

Доказательство. Множество £, состоящее из rs элементов, разложим по г ящикам, вместимостью 5 каждый. Рассмотрим произвольную as-элементную часть К множества Е. Может случиться, что элементы множества К целиком заполняют собою несколько ящиков, а в других ящиках вовсе отсутствуют; в таком случае мы назовем К сплошным; очевидно, сплошное К заполняет ровно а ящиков. Всевозможные as-элементные части множества Е (их число есть Cars^ подразделяются на сплошные, число которых обозначим X, и не-

сплошные, число которых обозначим У; таким образом, Cf/ = X+Y. Каждая сплошная часть задается указанием тех а ящиков, в которых она расположена, т. е. указанием некоторого а-элементного подмножества г-элементного множества F всех ящиков. Поэтому X = =Cj?, и нам нужно доказать, что У делится на m2. Переходя к несплошным частям, замечаем, что каждая такая часть К выделяет некоторую совокупность ящиков, в каждом из которых присутствует хотя бы один элемент из К, т. е. выделяет некоторое подмножество множества F. Приготовим 2Г комнат — столько, сколько у F подмножеств, и на дверь каждой комнаты повесим табличку с указанием одного из этих подмножеств. Далее, в каждую комнату поместим карточки с изображениями всех тех и только тех несплошных частей, для которых выделенное множество ящиков указано на табличке. Тогда Y = Y\ + ... + ^V, где Yi — число карточек в t'-й комнате. Достаточно теперь доказать, что каждое У/ делится на m2. Итак, займемся i-Pi комнатой — при произвольном, но фиксированном и Пусть на табличке, висящей на двери этой комнаты, указаны ящики Яь . •., Яь. Установим в комнате достаточное число столов. На каждый стол наклеим ярлык: на ярлыке напишем строчку чисел Si, ..., Sb, подчиненных условиям

(><*!<*,..., О < (9.1)

Позаботимся, чтобы для каждой строчки с условиями (9.1) в комнате стоял ровно один помеченный этой строчкой стол. Возьмем произвольную карточку из нашей комнаты. Элементы изображенного на ней множества К как-то распределены по ящикам Яь Яь, причем в каждом ящике присутствует хотя бы один элемент из К. Пусть в ящиках Яь Яь лежит, соответственно, sb sb элементов из К. Очевидно, для чисел Si, ..., s& выполняются неравенства (9.1); поэтому найдется стол, помеченный как раз этим набором чисел. Положим взятую нами карточку на этот стол. Таким образом, все карточки комнаты будут разложены по столам; некоторые столы, возможно, окажутся пустыми. Теперь достаточно обнаружить, что количество карточек на каждом непустом столе делится на т2. Пусть непустой стол помечен числами $и • » s&. Рассуждая, как при доказательстве леммы 2 из § 7, находим, что количество лежащих на столе карточек есть Csl • ... • Csb. Так как на карточках изображены лишь as-элементные подмножества множества Е, имеет место равенство

51+ +sb = as. (9.2)

Так как на карточках изображены лишь несплошные подмножества, то не может быть si = ... = sb = s; поэтому хотя бы для одного ящика Яа выполняется строгое неравенство sa < s. Если бы, однако, такое строгое неравенство выполнялось ровно для одного ящика, то сумма S\ +... + St не могла бы делиться на s, а она делится в силу (9.2). Следовательно, по крайней мере для двух ящиков Я a и Я$ выполнено

sa < s, sß < s. (9.3)

В силу (9.1) и (9.3) числаС*аиС^ суть внутренние члены s-й строки Паскаля. Поэтому каждое из этих чисел делится, по условию

леммы, на m, а произведение Cs'» ... • Csn, выражающее, как было указано, количество карточек на рассматриваемом столе, делится на m2.

Доказательство предложения 2. Если все числа C*s, где 0 <£ < rs, делятся на m, то, в частности, и все числа С^|, где О < а < г, делятся на m и, в силу леммы, все числа Сап где О < а < г, делятся на т. Обратно, пусть все числа Cj*. где О < а < г, делятся на т. Тогда, по той же лемме, все числа С™, где 0 < as < rs, делятся на m, и осталось доказать, что на m делятся все остальные числа C^s, где 0 < k < rs, т. е. числа C^s» у которых k не делится на s. Всякое такое C^s есть число ^-элементных частей rs-элементного множества Е. Действуем, как при доказательстве леммы 1. Сперва разложим Е по г ящикам; поскольку k не делится на s, то никакая ^-элементная часть не может быть сплошной. Далее, распределяем карточки с изображениями n-элементных частей по комнатам и столам. На столе, помеченном числами Si, Sby лежит Csl • ... • Csb карточек, причем по крайней мере в одном случае s а<. s и потому Отделится на т. Следовательно, число карточек на каждом столе, а значит, и в каждой комнате, а поэтому и число всех карточек (т. е. CJÎS) делится на т.

Доказательство предложения 3. Для всех n ^ m предложение 3 выполняется, поскольку, в силу предложения 1, п-я строка может делиться на m, лишь начиная с п = т. Пусть теперь предложение 3 выполнено для всех г < п, докажем его справедливость и для п. Если п не делится на m, то заведомо п не есть степень числа m и одновременно — в силу предложения 1 — п-я строка не делится на т; поэтому в данном случае предложение 3 выполняется. Пусть теперь п = гт. Применяя предложение 2, получаем, что п-я строка в том и только том случае делится на m, если на m делится г-я строка; последнее же обстоятельство, по индуктивному предположению, имеет место в том и только том случае, если г = mq, т. е. если п = mq+l.

Доказательство предложения 4. Соотношение

переписываем при 0 < k < р в виде равенства

1 . 2 - ... k . 1 . 2 - ... (р - k) - С\ — pl.

Поскольку правая часть делится на р, то и левая делится на р. Однако ни один из сомножителей левой части, кроме не может делиться на р. Поскольку р — число простое, то Ckp обязано делиться на р.

Замечание. Здесь мы воспользовались следующим основным свойством делимости на простое число: если а и Ь — натуральные числа и произведение ab делится на простое число р, то по крайней мере одно из чисел а и b делится на р. Наиболее короткое из

известных автору доказательств этого основного свойства делимости можно найти, например, в книге: Серпинский В. Что мы знаем и чего не знаем о простых числах, перев. с польского. — М.: Физматгиз, 1963, с. 25. Указанное основное свойство легко следует также из основной теоремы арифметики (которой посвящена, в частности, брошюра Л. А. Калужнина, «Основная теорема арифметики», составляющая 47-й выпуск данной серии «Популярные лекции по математике») и, в свою очередь, может быть положено в основу доказательства этой теоремы (как это и сделано в названной брошюре В. Серпинского).

Доказательство предложения 5. Применяем предложения 4 и 3.

Доказательство предложения 6. Пусть m делится на р и на <7, причем р ф q. Если какая-то строка Паскаля делится на т, то она делится и на /?, и на q, поэтому — в силу предложения 5 — ее номер п есть одновременно степень числа р и степень числа q. Но этого не может быть, если р и q — простые (хотя бы в силу того же основного свойства делимости).

Доказательство предложения 7. От противного. Пусть некоторая строка Паскаля делится на р2, тогда она делится на р, и ее номер, в силу предложения 5, имеет вид рк. Возьмем в этой строке член с номером р*""1, равный C^k .Достаточно обнаружить, что этот член не делится на р2. Все свелось, таким образом, к доказательству следующей леммы:

Лемма 2. Пусть р — простое число. Тогда C?k не делится на р2.

Доказательство — от противного. Предположим, что лемма неверна; тогда существует наименьшее k, при котором она неверна; возьмем это k\ очевидно, k ^ 2. Итак, C^fe делится на р2 и k ^ 2. Положим s = /?, г = pk-\ а = р*~2 и применим лемму 1; принимая во внимание предложение 4, получаем, что разность С"! — СаГ делится на р2. Поскольку, по предположению, тоже делится на р2, то и Сп равное в нашем случае С^к_{1 делится на р2, что противоречит выбору k в качестве наименьшего числа с заданным свойством.

Цена 10 к.

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

Вып. 1. А. И. Маркушевич. Возвратные последовательности.

Вып. 2. И. П. Натансон. Простейшие задачи на максимум и минимум.

Вып. 3. И. С. Соминский. Метод математической индукции.

Вып. 4. А. И. Маркушевич. Замечательные кривые.

Вып. 5. П. П. Коровкин. Неравенства.

Вып. 6. Н. Н. Воробьев. Числа Фибоначчи.

Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных степеней.

Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.

Вып. 9. А. И. Маркушевич. Площади и логарифмы.

Вып. 10. А. С. Смогоржевский. Метод координат.

Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.

Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.

Вып. 13. А. И. Маркушевич. Комплексные числа и конформные отображения.

Вып. 14. А. И. Фетисов. О доказательствах в геометрии.

Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней.

Вып. 16. В. Г. Шерватов. Гиперболические функции.

Вып. 17. В. Г. Болтянский. Что такое дифференцирование?

Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.

Вып. 19. Л. А. Люстерник. Кратчайшие линии.

Вып. 20. А. М. Лопшиц. Вычисление площадей ориентированных фигур.

Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрии.

Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры.

Вып. 23. А. С Смогоржевский. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные теоремы.

Вып. 25. А. С. Смогоржевский. Линейка в геометрических построениях.

Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач.

Вып. 27. В. А. Успенский. Некоторые приложения механики к математике.

Вып. 28. H. А. Архангельский и Б. И. Зайцев. Автоматические цифровые машины.

Вып. 29. A. H. Костовский. Геометрические построения одним циркулем.

Вып. 30. Г. Е. Шилов. Как строить графики.

Вып. 31. А. Г. Дорфман. Оптика конических сечений.

Вып. 32. Е. С. Вентцель. Элементы теории игр.

Выи. 33. А. С. Барсов. Что такое линейное программирование.

Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.

Вып. 35. H. Я. Виленкин. Метод последовательных приближений.

Вып. 36. В. Г. Болтянский. Огибающая.

Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной шкалы).

Вып. 38. Ю. А. Шрейдер. Что такое расстояние?

Вып. 39. Н. Н. Воробьев. Признаки делимости.

Вып. 40. С. В. Фомин. Системы счисления.

Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.

Вып. 42. Ю. И. Любич и Л. А. Шор. Кинематический метод в геометрических задачах.

Вып. 43. В. А. Успенский. Треугольник Паскаля.

Вып. 44. И. Я. Бакельман. Инверсия.

Вып. 45. И. М. Яглом. Необыкновенная алгебра.

Вып. 46. И. М. Соболь. Метод Монте-Карло.

Вып. 47. Л. А. Калужнин. Основная теорема арифметики.

Вып. 48. А. С. Солодовников. Системы линейных неравенств.

Вып. 49. Г. Е. Шилов. Математический анализ в области рациональных функций.

Вып. 50. В. Г. Болтянский, И. Ц. Гохберг. Разбиение фигур на меньшие части.

Вып. 51. Н. М. Бескин. Изображения пространственных фигур.

Вып. 52. Н. М. Бескин. Деление отрезка в данном отношении.

Вып. 53. Б. А. Розенфельд и Н. д. Сергеева. Стереографическая проекция.