Треугольник Серпинского

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

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

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

Способ первый: через чётность

Оказывается, узор Серпинского спрятан в треугольнике Паскаля: если закрасить нечётные биномиальные коэффициенты, получится именно он. Есть простое битовое правило: клетка $(row, col)$ закрашена тогда и только тогда, когда

$$(\,row\ \&\ col\,) = col,$$

где $\&$ — побитовое И. Это значит, что в двоичной записи $col$ нет ни одной единицы там, где у $row$ стоит ноль. Нарисуем:

n = 16
for row in range(n):
    line = ""
    for col in range(n):
        line += "*" if (row & col) == col else " "
    print(line)

Вывод:

*
**
* *
****
*   *
**  **
* * * *
********
*       *
**      **
* *     * *
****    ****
*   *   *   *
**  **  **  **
* * * * * * * *
****************

Способ второй: игра в хаос

Ещё поразительнее: возьмём три вершины треугольника и случайную точку. Бросаем кубик и шагаем на половину расстояния к случайно выбранной вершине; ставим точку; повторяем. Хаотичный, казалось бы, процесс рисует... всё тот же Серпинского. Это «игра в хаос» — пример того, как из случайности рождается строгая структура. Каждая итерация — это сжимающее преобразование, и притягивающее множество всех трёх преобразований и есть наш фрактал.

Как работает под капотом

Связь с чётностью объясняет теорема Куммера и Люка: биномиальный коэффициент $\binom{row}{col}$ нечётен ровно тогда, когда в двоичной записи $col$ «вкладывается» в $row$ — то есть когда $(row\ \&\ col) = col$. Самоподобие видно прямо в выводе: верхняя половина — копия всего узора, а нижняя — две его копии рядом. Поэтому при удвоении $n$ картинка повторяет себя в трёх углах, оставляя пустой центр — ровно правило построения фрактала.

Частые ошибки

Не путайте побитовое И & с логическим and: в правиле нужна именно битовая операция. Не ждите, что узор появится при произвольном $n$ — он самоподобен на степенях двойки. И в «игре в хаос» важно шагать ровно на половину пути: другой коэффициент даст другой (или размытый) аттрактор.

Итог

• Серпинского строится выбрасыванием центральных треугольников.
• Он же — узор нечётных биномиальных коэффициентов: $(row\ \&\ col) = col$.
• Он же — аттрактор «игры в хаос» со случайными шагами.
• Самоподобие: три копии в углах, пустой центр.