Треугольник Серпинского (иногда пишется как Серпинский ), также называемый прокладкой Серпинского или решетом Серпинского , представляет собой фрактальный притягивающий фиксированный набор с общей формой равностороннего треугольника , рекурсивно разделенный на меньшие равносторонние треугольники. Первоначально построенная в виде кривой, это один из основных примеров самоподобных множеств, то есть математически сгенерированная модель, воспроизводимая при любом увеличении или уменьшении. Он назван в честь польского математика Вацлава Серпинского , но появился как декоративный узор за много столетий до работ Серпинского.
Существует много различных способов построения треугольника Серпинского.
Треугольник Серпинского можно построить из равностороннего треугольника путем многократного удаления треугольных подмножеств:
Каждый удаленный треугольник ( трема ) топологически является открытым множеством . [1] Этот процесс рекурсивного удаления треугольников является примером правила конечного подразделения .
Ту же последовательность фигур, сходящихся к треугольнику Серпинского, можно альтернативно создать с помощью следующих шагов:
Этот бесконечный процесс не зависит от того, является ли исходная форма треугольником — просто так становится понятнее. Первые несколько шагов, начинающиеся, например, с квадрата, также имеют тенденцию к треугольнику Серпинского. Майкл Барнсли использовал изображение рыбы, чтобы проиллюстрировать это в своей статье «Фракталы и суперфракталы с V-переменной». [2] [3]
Настоящий фрактал — это то, что будет получено после бесконечного числа итераций. Более формально его описывают в терминах функций на замкнутых множествах точек. Если мы обозначим d A расширение в раз1/2относительно точки A, то треугольник Серпинского с углами A, B и C является фиксированным множеством преобразования .
Это привлекательное фиксированное множество , так что, когда операция многократно применяется к любому другому множеству, изображения сходятся в треугольнике Серпинского. Это то, что происходит с треугольником выше, но подойдет и любой другой набор.
Если взять точку и применить к ней каждое из преобразований d A , d B и d C случайным образом, полученные точки будут плотными в треугольнике Серпинского, поэтому следующий алгоритм снова будет генерировать к нему сколь угодно близкие приближения: [4 ]
Начните с обозначения точек p 1 , p 2 и p 3 как углов треугольника Серпинского и случайной точки v 1 . Установить v n +1 =1/2( v n + p r n ) , где r n — случайное число 1, 2 или 3. Нарисуйте точки v 1 до v ∞ . Если первая точка v 1 была точкой треугольника Серпинского, то все точки v n лежат на треугольнике Серпинского. Если первая точка v 1 , лежащая внутри периметра треугольника, не является точкой треугольника Серпинского, ни одна из точек v n не будет лежать на треугольнике Серпинского, однако они сойдутся на треугольнике. Если v 1 находится вне треугольника, единственный способ, которым v n приземлится на настоящий треугольник, - это если v n находится на том, что было бы частью треугольника, если бы треугольник был бесконечно большим.
Или проще:
Этот метод также называется игрой хаоса и является примером повторяющейся системы функций . Вы можете начать с любой точки снаружи или внутри треугольника, и в конечном итоге получится прокладка Серпинского с несколькими остатками точек (если начальная точка лежит на контуре треугольника, оставшихся точек нет). С помощью карандаша и бумаги краткий контур формируется после расстановки примерно ста точек, а детали начинают проявляться после нескольких сотен.
Другая конструкция прокладки Серпинского показывает, что ее можно построить в виде кривой на плоскости. Он формируется в результате многократного изменения более простых кривых, аналогично построению снежинки Коха :
На каждой итерации эта конструкция дает непрерывную кривую. В пределе они приближаются к кривой, которая очерчивает треугольник Серпинского одним непрерывным направленным (бесконечно извилистым) путем, который называется наконечником стрелки Серпинского . [5] Фактически, цель оригинальной статьи Серпинского 1915 года заключалась в том, чтобы показать пример кривой (кривой Кантора), как об этом свидетельствует само название статьи. [6] [7]
Треугольник Серпинского также появляется в некоторых клеточных автоматах (таких как Правило 90 ), в том числе в тех, которые относятся к «Игре жизни» Конвея . Например, Life-like клеточный автомат B1/S12 при применении к одной ячейке будет генерировать четыре аппроксимации треугольника Серпинского. [8] Очень длинная линия толщиной в одну клетку в обычной жизни создаст два зеркальных треугольника Серпинского. Временно-пространственная диаграмма шаблона репликатора в клеточном автомате также часто напоминает треугольник Серпинского, например, у обычного репликатора в HighLife. [9] Треугольник Серпинского также можно найти в автомате Улама-Уорбертона и автомате Хекс-Улама-Уорбертона. [10]
Если взять треугольник Паскаля со строками и раскрасить четные числа в белый цвет, а нечетные числа в черный, то результатом будет приближение к треугольнику Серпинского. Точнее, пределом n , стремящимся к бесконечности, этого треугольника Паскаля цвета четности является треугольник Серпинского. [11]
Поскольку доля черных чисел стремится к нулю с увеличением n , следствием является то, что доля нечетных биномиальных коэффициентов стремится к нулю, когда n стремится к бесконечности. [12]
Головоломка Ханойские башни включает в себя перемещение дисков разного размера между тремя колышками, сохраняя при этом свойство, согласно которому ни один диск никогда не помещается поверх диска меньшего размера. Состояния головоломки из n -дисков и допустимые переходы из одного состояния в другое образуют неориентированный граф , ханойский граф , который геометрически можно представить как граф пересечений множества треугольников, оставшихся после n- го шага в головоломке. построение треугольника Серпинского. Таким образом, в пределе стремления n к бесконечности эту последовательность графиков можно интерпретировать как дискретный аналог треугольника Серпинского. [13]
Для целого числа измерений при удвоении стороны объекта создаются его копии, т.е. 2 копии для 1-мерного объекта, 4 копии для 2-мерного объекта и 8 копий для 3-мерного объекта. Для треугольника Серпинского удвоение его стороны создает три его копии. Таким образом, треугольник Серпинского имеет размерность Хаусдорфа , что следует из решения для . [14]
Площадь треугольника Серпинского равна нулю (по мере Лебега ). Площадь, оставшаяся после каждой итерации, равна площади предыдущей итерации, а бесконечное количество итераций приводит к тому, что площадь приближается к нулю. [15]
Точки треугольника Серпинского имеют простую характеристику в барицентрических координатах . [16] Если точка имеет барицентрические координаты , выраженные в виде двоичных чисел , то точка находится в треугольнике Серпинского тогда и только тогда, когда для всех .
Обобщение треугольника Серпинского также можно создать с использованием треугольника Паскаля, если используется другой модуль . Итерацию можно создать, взяв треугольник Паскаля со строками и раскрасив числа по их значению по модулю . При приближении к бесконечности образуется фрактал.
Тот же фрактал можно получить, разделив треугольник на мозаику из подобных треугольников и удалив перевернутые треугольники из оригинала, а затем повторяя этот шаг с каждым меньшим треугольником.
И наоборот, фрактал также можно создать, начав с треугольника, продублировав его и расположив новые фигуры в той же ориентации в более крупный аналогичный треугольник с соприкасающимися вершинами предыдущих фигур, а затем повторяя этот шаг. [17]
Тетраэдр Серпинского или тетрикс — это трехмерный аналог треугольника Серпинского, образованный путем многократного сжатия правильного тетраэдра до половины его первоначальной высоты, соединения четырех копий этого тетраэдра с соприкасающимися углами и последующего повторения процесса.
Тетрикс, построенный из исходного тетраэдра с длиной стороны, обладает тем свойством, что общая площадь поверхности остается постоянной на каждой итерации. Начальная площадь поверхности тетраэдра (итерация-0) с длиной стороны равна . Следующая итерация состоит из четырех копий с длиной стороны , поэтому общая площадь снова равна. Последующие итерации снова увеличивают количество копий в четыре раза и уменьшают длину стороны вдвое, сохраняя общую площадь. При этом объем строительства на каждом этапе уменьшается вдвое и поэтому приближается к нулю. Предел этого процесса не имеет ни объема, ни поверхности, а, подобно прокладке Серпинского, представляет собой сложносвязанную кривую. Его размерность Хаусдорфа равна ; здесь «логарифм» обозначает натуральный логарифм , числитель — логарифм количества копий фигуры, сформированной из каждой копии предыдущей итерации, а знаменатель — логарифм коэффициента, на который эти копии уменьшаются по сравнению с предыдущей итерация. Если все точки проецируются на плоскость, параллельную двум внешним ребрам, они точно заполняют квадрат с длиной стороны без перекрытия. [18]
Вацлав Серпинский описал треугольник Серпинского в 1915 году. Однако подобные узоры уже появляются как распространенный мотив инкрустированной каменной кладки в косматском стиле XIII века . [19]
Аполлоническая прокладка была впервые описана Аполлонием Пергским (3 век до н.э.) и далее проанализирована Готфридом Лейбницем (17 век) и является изогнутым предшественником треугольника Серпинского 20-го века. [20]
Использование слова «прокладка» для обозначения треугольника Серпинского относится к прокладкам , которые встречаются в двигателях и которые иногда имеют ряд отверстий уменьшающегося размера, похожих на фрактал; это использование было придумано Бенуа Мандельбротом , который считал, что фрактал похож на «часть, которая предотвращает утечки в двигателях». [21]