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

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

Как известно, Блезу Паскалю вполне заслуженно приписывают звание одного из основателей теории вероятностей, но на этом поприще следует отдать должное и другим учёным, также внесшим значительный вклад в этот раздел математики. Одним из них был итальянский полимат Джероламо Кардано. Сегодня специализация в образовании и профессиях зачастую подавляет человеческое любопытство и потенциал, которые естественным образом выходят за рамки узких предметных областей.

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

Кардано внёс весомый вклад в самые разные сферы науки и техники. Изначально при подготовке этой статьи я хотел остановиться лишь на его работах, посвящённых теории вероятности, так как в них имеются явные отсылки к треугольнику Паскаля. Однако, чем больше я читал об этом учёном, тем больше поражался его гением. Одним из самых известных его изобретений, связанных с любимой мной темой криптографии, является криптографический трафарет, знакомый большинству пользователей Хабра под названием «решётка Кардано». Интересующиеся блокчейном и криптовалютами, наверняка знакомы с платформой смарт-контрактов Cardano, названной в его честь. Работы этого учёного в области механики также остались его наследием. Я думаю, что нет ни одного человека, который хотя бы краем уха не слышал бы про такие устройства, как карданный вал и передача. Пожалуй, его самый важный, хоть и не самый очевидный, цивилизационный вклад заключался в том, что Кардано был первым европейским учёным, систематически использовавшим отрицательные числа. Возвращаясь к работам учёного Liber de ludo aleae («Книга об азартных играх»), которая содержит одно из первых систематических описаний вероятности, и Opus novum de proportionibus («Новая работа над пропорциями»), в которой он вводит биномиальные коэффициенты и теорему, рассмотрим связь между вероятностью и числами в треугольнике Паскаля. Наглядно эту связь можно продемонстрировать, рассмотрев популярный пример, описывающий результаты независимых бросков монет, как в таблице ниже (О – орёл, Р – решка).

Дальнейшее увеличение числа бросков в таблицу я не стал заносить, чтобы её не загромождать, однако их общее количество можно вычислить простым взятием степени двойки, то есть пять бросков дадут 32 и т. д.

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

В четвёртой строке показано, что три независимых броска дают вероятность выпадения любой комбинации, равную 3\(1+3+3+1)=3\8.

Ранее мы рассматривали треугольник Паскаля только как математический артефакт, однако существует и его материальное воплощение. В 1873 году английский учёный Фрэнсис Гальтон создал устройство, которое известно как доска Гальтона. На западе не очень любят Гальтона из-за основного направления его научных изысканий, поэтому чаще всего используют термин bean machine или quincunx. Доска Гальтона представляет собой физическую модель биномиального распределения, которая прекрасно иллюстрирует центральную предельную теорему. Впрочем, именно ради этой наглядной демонстрации Гальтон и изобрёл это устройство.

Страстью Гальтона было нормальное распределение, поэтому он и разработал это «наглядное пособие». Скорее всего, первый материальный образец был произведен в 1873 году компанией Tisley & Spiller (компания занималась производством различных научных приборов) и использовался им в качестве учебного пособия на лекциях.

В книге «Естественное наследование» (Natural Inheritance, 1889), где собраны многие его научные изыскания с 1874 по 1889 год и рассматриваются вопросы совместимости наследственности, Гальтон дал подробное описание своего устройства и назвал его квинконсом (quincunx). Это выражение он заимствовал из сельского хозяйства, где оно используется для описания топологического способа посадки плодовых деревьев. Также называется любое расположение пяти объектов, похожих на пятна на игральной кости.

Устройство выглядит как вертикально расположенная прямоугольная доска с треугольным набором равномерно расположенных колышков в средней части. Ближе к верху размещается ёмкость с отверстием, способным выпускать лишь по одному шарику за раз таким образом, чтобы шарик попадал строго в середину верхнего колышка. В нижней части доски помещены контейнеры для сбора шаров. Обычно вся установка плотно закрывается прозрачным корпусом, чтобы можно было наблюдать за движением шаров и избежать их выпадения. После падения шар попадает на верхний колышек, а затем отскакивает ниже — влево или вправо — с равной вероятностью. Собираясь в контейнерах, шары образуют классическую колоколообразную кривую нормального распределения.

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

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

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

Для наглядности рассмотрим ситуацию с формированием комбинаций команд для эстафеты из трёх участников при наличии всего пятерых человек. Возьмём, к примеру, вот этих всем известных «товарищей»: Энгельбарт, Таненбаум, Ритчи, Гейтс, Джой. Составим все возможные комбинации.

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

Формула для расчета количества комбинаций:

где n представляет собой общее количество участников, из которого мы выбираем, а r — количество членов команды. В нашем примере n = 5, а r = 3. Таким образом, С = 10.

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

Вернёмся на некоторое время к самому Блезу Паскалю. Как и многие другие учёные эпохи Просвещения, он был полиматом и оставил свой след во многих сферах деятельности, в том числе и в вычислительной технике. Отец Паскаля был сборщиком налогов, и в 1642 году в возрасте 19 лет Блез изобрёл механическое счётное устройство, чтобы помочь в рутинных расчётах своему отцу. Сегодня этот прибор известен под названием «паскалина», однако сам учёный называл её суммирующей машиной. На данный момент это счётное устройство считается первым достоверно существовавшим.

Оно состояло из системы взаимосвязанных подвижных шестерён, разделённых на сектора с числами. Этот принцип ещё несколько сотен лет использовался в различных вычислительных устройствах. Изобретение не имело коммерческого успеха, было дорогим и зачастую приобреталось в качестве сувенира. Как и многие устройства после него, оно опередило своё время и не прижилось в качестве рабочего инструмента. А жаль, поскольку, если бы история пошла по другому пути, возможно, современная вычислительная техника была бы намного круче.

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

Если в треугольнике Паскаля мы выделим цветом числа, кратные любому из натуральных чисел ≥ 2, то они создадут узор из перевёрнутых треугольников, который напоминает фрактал, описанный в 1915 году польским математиком Вацлавом Серпинским. На Хабре есть хорошая статья о треугольнике Серпинского.

Фракталы — вообще отдельно взятая тема, которая находит своё применение во множестве различных отраслей. Что касается технологий, то первым делом вспоминаются фрактальные антенные системы (частным случаем является, например, технология RFID), фрактальные алгоритмы сжатия, децентрализованные сети и проектирование микроэлектроники.

Если рассмотрим первые 32 строки треугольника Паскаля по модулю 2 как двоичные числа и преобразуем их в десятичные числа, мы получим последовательность OEIS (онлайн-энциклопедия целочисленных последовательностей) A001317:

1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295, …

Интересно, что все члены этой последовательности до 31 включительно являются целочисленными делителями последнего числа 4294967295. Если представить его как (2³² – 1), то понятно, что это число является числом Мерсенна. Сложно сказать, почему только первые 31 являются делителями 32-го члена, а дальше эта закономерность ломается. На некоторых профильных ресурсах ведутся дискуссии по этому поводу, в которых также обсуждается, что происходит с этим паттерном после 32-го члена.

Ещё интересный факт: это число имеет простую факторизацию 3 × 5 × 17 × 257 × 65537 = 4294967295. И здесь снова мистика. Эти простые множители на сегодняшний день являются единственно известными простыми числами Ферма. То есть числа вида:

в этом случае с n = 0, 1, 2, 3 и 4. Поиск других таких чисел, как и их существование, являются открытой научной проблемой. Эти закономерности в рядах треугольника интригуют, и попытки понять их привели к ещё одному интересному открытию. В частности, хотя 33-й член не делится на 32-й, 34-й — ровно в три раза больше 33-го. Далее числа чередуются между дробным отношением и отношением, равным трём, что, как я предполагаю, является закономерностью, которая будет продолжаться и далее, но это не точно (¯\_(ツ)_/¯).

Следующей пасхалкой, которую хранит в себе треугольник, является его связь с самыми известными трансцендентными числами — числом Эйлера и π. Эти числа и сами по себе являются математическими пасхалками, хранящими в себе множество интересных свойств. Подавляющее большинство математиков и учёных вообще считают самой элегантной формулой в математике тождество Эйлера. Общепризнанная математическая красота этой формулы не может оставить равнодушным даже человека, не сильно связанного с математикой.

В чём красота? При всём своём минимализме тождество Эйлера показывает глубокую взаимосвязь между классическими разделами математики. Оно соединяет в себе основные математические операции и пять фундаментальных констант, принадлежащих к четырём классическим областям математики. Нуль и единица относятся к арифметике, мнимая единица — к алгебре, число π — к геометрии, а основание натурального логарифма — к матанализу.

Существует множество приближений и формул, связывающих число Эйлера, π и другие иррациональные числа. В 2012 году американский математик-любитель Харлан Бразерс (Harlan J. Brothers) сумел связать число Эйлера и треугольник Паскаля. Он вывел и доказал формулу:

где S_n — произведение чисел в n строке треугольника.

Ранее, в 2007 году другой математик, энтузиаст Джонас Толоза (Jonas Castillo Toloza) обнаружил связь между π и обратными треугольными числами (которые содержатся на одной из диагоналей треугольника Паскаля). Немного позже было найдено более элегантное доказательство. Английский профессор Рон Нотт (Ron Knott) свёл его к одной из качественных аппроксимацией числа π, ряду Нилаканта, тогда как Толоза доказывал свойство с помощью ряда Грегори-Лейбница, который в сравнительном анализе различных простых методов вычисления числа π дал наихудшие результаты.

Треугольник Паскаля обладает взаимосвязью с ещё одним широко известным рядом — гармоническим. Этот ряд состоит из бесконечного количества гармоник чисел натурального ряда.

Гармонический ряд является медленно расходящимся. Для того, чтобы сумма членов ряда превысила сотню необходимо сложить 15092688622113788323693563264538101449859497 значений. Этот ряд можно использовать для создания другого интересного треугольника, который называется гармоническим треугольником Лейбница.

В этом варианте гармонический ряд размещается вдоль двух ведущих диагоналей. Слева его элементы связываются тем, что каждый из них представляет собой разность дроби слева от него и дроби, расположенной сверху и слева по диагонали. Справа они связываются ровно таким же образом, только зеркально. Например, 1\30=1\5 — 1\6.

Вторую диагональ в треугольнике Лейбница называют телескопическим рядом: 1/2, 1/6, 1/12, 1/20, ... Треугольник Лейбница в некотором роде является противоположностью треугольника Паскаля. Так, чтобы получить число, нужно сложить два числа ниже него, например: 1\2 = 1\3 + 1\6.

Чтобы из треугольника Лейбница получить паскалевский, нужно разделить первый член в n-й строке на каждый другой в этой же строке. Например, в пятом ряду мы получим следующее:

Что интересно, треугольник Лейбница был известен и до него. Итальянский математик Пьетро Менголи, пытаясь найти решение проблемы квадратуры круга, вывел этот треугольник и использовал его для работы с бесконечными рядами и нахождения площадей. Конечно, проблема квадратуры осталась нерешённой, однако Менголи смог вычислить число π до 11 знака.

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

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS