Кайфын: треугольник до Паскаля

Таблица

Цзя Сянь работал в Кайфыне — столице империи Сун, крупнейшем городе мира XI века — около 1050 года. Его сочинения утрачены; содержание известно через трактат Ян Хуэя (1261), который честно ссылается на предшественника. Поэтому в Китае треугольник называют треугольником Ян Хуэя.

Таблица устроена так:

$$ \begin{array}{ccccccccc} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1 \end{array} $$

Каждое число — сумма двух стоящих над ним. В современной записи это тождество

$$C_{n}^{k}=C_{n-1}^{k-1}+C_{n-1}^{k}.$$

Почему оно верно — рассуждение, которое стоит проделать, потому что оно образцово комбинаторное. Выбираем $k$ предметов из $n$. Отметим один предмет — скажем, последний. Все выборы делятся на два непересекающихся класса: те, где отмеченный предмет взят (тогда остальные $k-1$ выбираются из $n-1$), и те, где не взят (тогда все $k$ выбираются из $n-1$). Сложив, получаем тождество. $\blacksquare$

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

Зачем это было нужно

Цзя Сянь строил таблицу не ради красоты, а как вычислительное средство: с её помощью извлекаются корни любой степени.

Метод такой: чтобы найти корень степени $n$ из числа, подбирают цифры ответа по одной, и на каждом шаге нужно знать, насколько изменится $n$-я степень при добавлении очередной цифры. Ответ даёт разложение

$$(a+b)^{n}=\sum_{k}C_{n}^{k}a^{n-k}b^{k},$$

а коэффициенты берутся из таблицы. Способ развил Цинь Цзюшао (1247) до того, что в Европе называют схемой Горнера, — за пять с половиной веков до Горнера.

Заметьте, что это алгоритм: конечная последовательность действий, гарантированно приводящая к ответу с нужной точностью. Дискретная математика начинается не с теорем, а с рецептов такого рода.

Пять открытий одного треугольника

Треугольник — рекордсмен карты по числу независимых переоткрытий.

Индийский случай особенно интересен и стоит отдельного слова. Пингала, разбирая стихотворные размеры из долгих и кратких слогов, перечислял все возможные сочетания — и получил и биномиальные коэффициенты (таблица меру-прастара, описанная комментатором Халаюдхой в X веке), и последовательность, которую мы называем числами ФибоначчиЛеонардо Пизанскийитальянский математик · около 1170 — около 1250Привёз в Европу индийские цифры, нуль и счёт пером вместо жетонов на доске; кролики из двенадцатой главы — побочная задача, прославившая его через шестьсот пятьдесят лет.. Задача была лингвистической; математика получилась как побочный продукт.

Вклад Паскаля — не открытие таблицы, а два других шага: он поставил её на службу подсчёту шансов и доказал её свойства методом полной индукции, дав одну из первых явных формулировок этого метода.

Что ещё было в этой традиции

Китайская дискретная математика недобрана на нашей карте, и стоит перечислить хотя бы главное.

«Математика в девяти книгах» (оформлена к I в. н. э.) — систематический свод из 246 задач с методами решения, в том числе метод Гаусса для линейных систем (за восемнадцать веков до ГауссаКарл Фридрих Гаусснемецкий математик и астроном · 1777–1855«Король математиков», у которого напечатанное было заметно меньше сделанного: половина результатов пролежала в дневнике до самой смерти — включая неевклидову геометрию.) и правило работы с отрицательными числами.

Задача Сунь Цзы (III–V вв.): найти число, дающее заданные остатки при делении на 3, 5, 7. Общий метод дал Цинь Цзюшао (1247) — это китайская теорема об остатках, и она работает в каждом современном криптографическом пакете.

«Яшмовое зеркало четырёх элементов» Чжу Шицзе (1303) содержит треугольник до восьмой строки и решение систем уравнений с четырьмя неизвестными.

Следующая точка: Новгород — где счётом займутся ради календаря и упрутся в вопрос о делимости времени.