| Глава 10. Треугольник Паскаля | ||
|---|---|---|
 |  | |
| Глава 10. Треугольник Паскаля | ||
|---|---|---|
| | | |
Числовой треугольник Паскаля — неисчерпаемый источник всевозможных математических радостей.
В верхней строчке треугольника располагается одинокая единица. В остальных строках каждое число является суммой двух своих соседей этажом выше — слева и справа. Если какой-то из соседей отсутствует, он считается равным нулю. Треугольник бесконечно простирается вниз; мы приводим лишь восемь верхних строчек:
Обозначим буквой номер строки треугольника, а буквой — номер числа в строке (нумерация начинается в обоих случаях с нуля). Чаще всего число в -ой строке и на -ом месте в этой строке обозначается , реже — .
Назовём лишь некоторые факты, относящиеся к треугольнику Паскаля.
Числа в -ой строке треугольника являются биномиальными коэффициентами, то есть коэффициентами в разложении -ой степени бинома Ньютона:
Сумма всех чисел в -ой строке равна -ой степени двойки: Эта формула получается из формулы бинома, если положить .
Можно доказать явную формулу для вычисления биномиального коэффициента:
Если строки в треугольнике Паскаля выровнять по левому краю, то суммы чисел, расположенных вдоль диагоналей, идущих слева направо и снизу вверх, равны числам Фибоначчи — (каждое число в этой последовательности равно сумме двух предыдущих, а начинают последовательность две единицы):
Если раскрасить нечётные числа в треугольнике Паскаля в один цвет, а чётные — в другой, получится такая картина (на рисунке 10.1. «Треугольник Паскаля — Серпинского» указанным образом раскрашены числа в первых 128 строчках):
Похожее изображение можно построить следующим образом. В закрашенном
треугольнике перекрасим в другой цвет его серединный треугольник (образованный
серединами сторон исходного). Три маленьких треугольника, расположенные по
углам большого, останутся закрашенными в прежний цвет. Поступим с каждым из них
точно так же, как мы поступили с большим, то есть перекрасим в каждом
серединный треугольник. То же самое сделаем с оставшимися треугольниками
старого цвета. Если эту процедуру проделывать до бесконечности, на месте
исходного треугольника останется двухцветная фигура. Та её часть, которая не
перекрашена, называется треугольником
Серпинского.
Несколько первых этапов построения треугольника Серпинского показаны на рисунке
10.2. «Построение треугольника Серпинского».
Важным свойством треугольника Серпинского является его
самоподобие — ведь он состоит из
трёх своих копий, уменьшенных в два раза (это части треугольника Серпинского,
содержащиеся в маленьких треугольниках, примыкающих к углам). Самоподобие —
одно из характерных свойств фракталов, о которых мы ещё поговорим
в главе 44. «L-системы». Треугольник Серпинского также
будет упомянут в этой главе.
О таинственной связи треугольника Паскаля с простыми числами мы вычитали в книге [9] в небольшой заметке Ю. Матиясевича. Заменим в треугольнике Паскаля числа на их остатки от деления на номер строки. Расположим строки в полученном треугольнике таким образом, чтобы следующая строка начиналась на две колонки правее начала предыдущей (см. рисунок 10.3. «Связь треугольника Паскаля с простыми числами»). Тогда столбцы с простыми номерами будут состоять из одних нулей, а в столбцах, чьи номера составные, найдётся ненулевое число.
В этом руководстве мы ещё вернёмся к теме простых чисел, и не раз (в главах 14. «Поиск простых чисел», 32. «Поиск простых чисел с помощью регулярных выражений», 38. «Объектно-ориентированное программирование», 39. «Битовая реализация числового множества»).
| | | |
| Готовая программа |  | Постановка задачи |