Герсонид: комбинаторика с доказательствами

Автор

Леви бен Гершом (1288–1344), в латинской традиции Герсонид, жил в Провансе — в Баньоль-сюр-Сез и Оранже. Раввин, философ, комментатор Библии, астроном и математик; фигура крупная и в еврейской, и в европейской интеллектуальной истории.

Из его нематематических занятий стоит отметить одно, потому что оно вошло в европейскую науку: он изобрёл посох Иакова (baculus Jacobi) — простой угломерный прибор из рейки с подвижной поперечиной, позволявший измерять угловое расстояние между светилами. Прибор использовался мореплавателями до XVIII века; им пользовались и Колумб, и Васко да Гама.

«Маасе хошев»

Трактат «Маасе хошев» («Дело счётчика», 1321) содержит 68 предложений и устроен по-евклидовски: утверждение, доказательство, следствие.

Что в нём доказано:

• число перестановок $n$ предметов равно $n!$;
• число размещений — упорядоченных выборок $k$ из $n$ — равно $\dfrac{n!}{(n-k)!}$;
• число сочетаний равно $\dbinom{n}{k}=\dfrac{n!}{k!\,(n-k)!}$;
• формулы для сумм: $\sum k$, $\sum k^{2}$, $\sum k^{3}$, причём последняя — знаменитое $\left(\sum k\right)^{2}$.

Ни одна из этих формул не была новостью: их знали и в Индии, и в исламском мире, и в еврейской традиции до него. Новостью были доказательства.

Индукция

Главное в трактате — метод. Герсонид рассуждает так:

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

Это математическая индукция — в явном, осознанном и систематически применяемом виде. Историки математики расходятся в том, кому отдать первенство: рассуждения индуктивного типа встречаются у аль-Караджи (ок. 1000) и раньше, а явную формулировку принципа обычно приписывают Мауролико (1575) и Паскалю (1654). Но у Герсонида метод применяется подряд, в десятках предложений, с осознанием того, что это общий приём, — и по этому признаку он, пожалуй, первый.

Как выглядит его доказательство $n!$. Для одного предмета перестановка одна. Пусть для $n-1$ предметов их $(n-1)!$. Возьмём $n$ предметов; первое место можно занять $n$ способами, а остальные $n-1$ предметов переставляются $(n-1)!$ способами. Значит, всего $n\cdot(n-1)!=n!$. $\blacksquare$

Рассуждение выглядит очевидным сегодня — и в этом всё дело. До Герсонида комбинаторные формулы были рецептами: их знали и применяли, но не обосновывали. Он превратил их в теоремы.

Почему его не читали

Судьба трактата — характерный сюжет о том, как работает передача знания.

Написан он на иврите, в Провансе, вне университетской латинской традиции. Латинского перевода не было; европейские математики XV–XVII веков его не читали. ПаскальБлез Паскальфранцузский математик, физик и религиозный философ · 1623–1662Собрал в шестнадцать лет теорему о шестиугольнике, в девятнадцать — счётную машину, в тридцать один — теорию вероятностей, а потом бросил математику ради Бога., доказывая те же вещи в 1654 году, о предшественнике не знал.

Первое научное издание с немецким переводом появилось только в 1909 году (Густав Лянге); всерьёз содержание оценили в середине XX века. Сегодня Герсонида считают одним из крупнейших комбинаторщиков Средневековья — но на европейскую математику он не повлиял никак.

Это стоит держать в уме, читая любую историю науки: последовательность идей и последовательность влияний — разные последовательности. Тот же сюжет на карте — Дезарг, забытый на двести лет, Шлефли, напечатанный посмертно, и Ферма, не публиковавший почти ничего.

Астрономия

Ради полноты: Герсонид составил астрономические таблицы, критиковал птолемеевские модели за несоответствие наблюдениям (в частности, заметил, что видимый размер планет не меняется так, как требуют эпициклы) и первым дал оценку расстояний до звёзд, получив величины на порядки большие принятых. Его именем назван кратер на Луне.

Задача. Докажите по индукции формулу для числа сочетаний, повторив ход Герсонида: покажите, что $C_{n}^{k}=C_{n-1}^{k-1}+C_{n-1}^{k}$, и выведите отсюда явную формулу.
(Указание: базой служат $C_{n}^{0}=C_{n}^{n}=1$; шаг — то самое тождество из треугольника Цзя Сяня. Явная формула проверяется подстановкой: $\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-1-k)!}=\frac{(n-1)!\,[\,k+(n-k)\,]}{k!(n-k)!}=\frac{n!}{k!(n-k)!}$.)

Следующая точка: Париж — где комбинаторику применят к деньгам и попутно родят теорию вероятностей.