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

Фрактал, состоящий из треугольников

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

Генерируется с использованием случайного алгоритма

Треугольник Серпинского в логике: первые 16 союзов лексикографически упорядоченных аргументов . Столбцы, интерпретируемые как двоичные числа, дают 1, 3, 5, 15, 17, 51... (последовательность A001317 в OEIS ).

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

Конструкции

Существует много различных способов построения треугольника Серпинского.

Удаление треугольников

Треугольник Серпинского можно построить из равностороннего треугольника путем многократного удаления треугольных подмножеств:

1. Начните с равностороннего треугольника.
2. Разделите его на четыре равных равносторонних треугольника меньшего размера и удалите центральный треугольник.
3. Повторяйте шаг 2 с каждым из оставшихся меньших треугольников бесконечно.

Эволюция треугольника Серпинского

Каждый удаленный треугольник ( трема ) топологически является открытым множеством . ^[1] Этот процесс рекурсивного удаления треугольников является примером правила конечного подразделения .

Сокращение и дублирование

Ту же последовательность фигур, сходящихся к треугольнику Серпинского, можно альтернативно создать с помощью следующих шагов:

1. Начните с любого треугольника на плоскости (на самом деле подойдет любая замкнутая ограниченная область на плоскости). Канонический треугольник Серпинского представляет собой равносторонний треугольник с основанием, параллельным горизонтальной оси (первое изображение).
2. Уменьшите треугольник до1/2высота и1/2ширину, сделайте три копии и расположите три сморщенных треугольника так, чтобы каждый треугольник касался двух других треугольников в углах (изображение 2). Обратите внимание на появление центрального отверстия, поскольку три сморщенных треугольника между собой могут покрывать только3/4площади оригинала. (Дырки — важная особенность треугольника Серпинского.)
3. Повторите шаг 2 с каждым из меньших треугольников (изображение 3 и так далее).

Этот бесконечный процесс не зависит от того, является ли исходная форма треугольником — просто так становится понятнее. Первые несколько шагов, начинающиеся, например, с квадрата, также имеют тенденцию к треугольнику Серпинского. Майкл Барнсли использовал изображение рыбы, чтобы проиллюстрировать это в своей статье «Фракталы и суперфракталы с V-переменной». ^{[2] [3]}

Итерация от квадрата

Настоящий фрактал — это то, что будет получено после бесконечного числа итераций. Более формально его описывают в терминах функций на замкнутых множествах точек. Если мы обозначим d _A расширение в раз1/2относительно точки A, то треугольник Серпинского с углами A, B и C является фиксированным множеством преобразования . ${\displaystyle d_{\mathrm {A} }\cup d_{\mathrm {B} }\cup d_{\mathrm {C} }}$

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

Игра Хаос

Анимированное создание треугольника Серпинского с помощью игры хаоса.

Если взять точку и применить к ней каждое из преобразований d _A , d _B и d _C случайным образом, полученные точки будут плотными в треугольнике Серпинского, поэтому следующий алгоритм снова будет генерировать к нему сколь угодно близкие приближения: ^{[4 ]}

Начните с обозначения точек p ₁ , p ₂ и p ₃ как углов треугольника Серпинского и случайной точки v ₁ . Установить v _{n +1} =1/2( v _n + p _{r n} ) , где r _n — случайное число 1, 2 или 3. Нарисуйте точки v ₁ до v _∞ . Если первая точка v ₁ была точкой треугольника Серпинского, то все точки v _n лежат на треугольнике Серпинского. Если первая точка v ₁ , лежащая внутри периметра треугольника, не является точкой треугольника Серпинского, ни одна из точек v _n не будет лежать на треугольнике Серпинского, однако они сойдутся на треугольнике. Если v ₁ находится вне треугольника, единственный способ, которым v _n приземлится на настоящий треугольник, - это если v _n находится на том, что было бы частью треугольника, если бы треугольник был бесконечно большим.

Или проще:

1. Возьмите три точки на плоскости, чтобы образовать треугольник.
2. Случайным образом выберите любую точку внутри треугольника и считайте это своей текущей позицией.
3. Случайным образом выберите любую из трех вершинных точек.
4. Переместитесь на половину расстояния от вашего текущего положения до выбранной вершины.
5. Постройте текущую позицию.
6. Повторите с шага 3.

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

Конструкция наконечника прокладки Серпинского

Конструкция наконечника прокладки Серпинского

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

1. Начните с одного сегмента линии на плоскости.
2. Несколько раз замените каждый сегмент кривой тремя более короткими сегментами, образуя углы 120 ° на каждом стыке между двумя последовательными сегментами, при этом первый и последний сегменты кривой либо параллельны исходному сегменту линии, либо образуют с ним угол 60 °.

На каждой итерации эта конструкция дает непрерывную кривую. В пределе они приближаются к кривой, которая очерчивает треугольник Серпинского одним непрерывным направленным (бесконечно извилистым) путем, который называется наконечником стрелки Серпинского . ^[5] Фактически, цель оригинальной статьи Серпинского 1915 года заключалась в том, чтобы показать пример кривой (кривой Кантора), как об этом свидетельствует само название статьи. ^{[6] [7]}

Клеточные автоматы

Треугольник Серпинского также появляется в некоторых клеточных автоматах (таких как Правило 90 ), в том числе в тех, которые относятся к «Игре жизни» Конвея . Например, Life-like клеточный автомат B1/S12 при применении к одной ячейке будет генерировать четыре аппроксимации треугольника Серпинского. ^[8] Очень длинная линия толщиной в одну клетку в обычной жизни создаст два зеркальных треугольника Серпинского. Временно-пространственная диаграмма шаблона репликатора в клеточном автомате также часто напоминает треугольник Серпинского, например, у обычного репликатора в HighLife. ^[9] Треугольник Серпинского также можно найти в автомате Улама-Уорбертона и автомате Хекс-Улама-Уорбертона. ^[10]

Треугольник Паскаля

Аппроксимация уровня 5 треугольника Серпинского, полученная путем закрашивания первых 2 ⁵ (32) уровней треугольника Паскаля белым, если биномиальный коэффициент четный, и черным в противном случае.

Если взять треугольник Паскаля со строками и раскрасить четные числа в белый цвет, а нечетные числа в черный, то результатом будет приближение к треугольнику Серпинского. Точнее, пределом n , стремящимся к бесконечности, этого треугольника Паскаля цвета четности является треугольник Серпинского. ^[11] ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$

Поскольку доля черных чисел стремится к нулю с увеличением n , следствием этого является то, что доля нечетных биномиальных коэффициентов стремится к нулю, когда n стремится к бесконечности. ^[12]

Башни Ханоя

Головоломка Ханойские башни включает в себя перемещение дисков разного размера между тремя колышками, сохраняя при этом свойство, согласно которому ни один диск никогда не помещается поверх диска меньшего размера. Состояния головоломки из n -дисков и допустимые переходы из одного состояния в другое образуют неориентированный граф , ханойский граф , который геометрически можно представить как граф пересечений множества треугольников, оставшихся после n- го шага в головоломке. построение треугольника Серпинского. Таким образом, в пределе стремления n к бесконечности эту последовательность графиков можно интерпретировать как дискретный аналог треугольника Серпинского. ^[13]

Характеристики

Для целого числа измерений при удвоении стороны объекта создаются его копии, т.е. 2 копии для 1-мерного объекта, 4 копии для 2-мерного объекта и 8 копий для 3-мерного объекта. Для треугольника Серпинского удвоение его стороны создает три его копии. Таким образом, треугольник Серпинского имеет размерность Хаусдорфа , ​​что следует из решения для . ^[14] ${\displaystyle d}$ ${\displaystyle 2^{d}}$ ${\displaystyle {\tfrac {\log 3}{\log 2}}\approx 1.585}$ ${\displaystyle 2^{d}=3}$ ${\displaystyle d}$

Площадь треугольника Серпинского равна нулю (по мере Лебега ). Площадь, оставшаяся после каждой итерации, равна площади предыдущей итерации, а бесконечное количество итераций приводит к тому, что площадь приближается к нулю. ^[15] ${\displaystyle {\tfrac {3}{4}}}$

Точки треугольника Серпинского имеют простую характеристику в барицентрических координатах . ^[16] Если точка имеет барицентрические координаты , выраженные в виде двоичных чисел , то точка находится в треугольнике Серпинского тогда и только тогда, когда для всех . ${\displaystyle (0.u_{1}u_{2}u_{3}\dots ,0.v_{1}v_{2}v_{3}\dots ,0.w_{1}w_{2}w_{3}\dots )}$ ${\displaystyle u_{i}+v_{i}+w_{i}=1}$ ${\displaystyle i}$

Обобщение на другие модули

Обобщение треугольника Серпинского также можно создать с использованием треугольника Паскаля, если используется другой модуль . Итерацию можно создать, взяв треугольник Паскаля со строками и раскрасив числа по их значению по модулю . При приближении к бесконечности образуется фрактал. ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle P^{n}}$ ${\displaystyle P}$ ${\displaystyle n}$

Тот же фрактал можно получить, разделив треугольник на мозаику из подобных треугольников и удалив перевернутые треугольники из оригинала, а затем повторяя этот шаг с каждым меньшим треугольником. ${\displaystyle P^{2}}$

И наоборот, фрактал также можно создать, начав с треугольника, продублировав его и расположив новые фигуры в той же ориентации в более крупный аналогичный треугольник с соприкасающимися вершинами предыдущих фигур, а затем повторяя этот шаг. ^[17] ${\displaystyle {\tfrac {n(n+1)}{2}}}$

Аналоги в высших измерениях

Рекурсия пирамиды Серпинского (8 шагов)

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

Тетрикс, построенный из исходного тетраэдра с длиной стороны, обладает тем свойством, что общая площадь поверхности остается постоянной на каждой итерации. Начальная площадь поверхности тетраэдра (итерация-0) с длиной стороны равна . Следующая итерация состоит из четырех копий с длиной стороны , поэтому общая площадь снова равна. Последующие итерации снова увеличивают количество копий в четыре раза и уменьшают длину стороны вдвое, сохраняя общую площадь. При этом объем строительства на каждом этапе уменьшается вдвое и поэтому приближается к нулю. Предел этого процесса не имеет ни объема, ни поверхности, а, подобно прокладке Серпинского, представляет собой сложносвязанную кривую. Его размерность Хаусдорфа равна ; здесь «логарифм» обозначает натуральный логарифм , числитель — логарифм количества копий фигуры, сформированной из каждой копии предыдущей итерации, а знаменатель — логарифм коэффициента, на который эти копии уменьшаются по сравнению с предыдущей итерация. Если все точки проецируются на плоскость, параллельную двум внешним ребрам, они точно заполняют квадрат с длиной стороны без перекрытия. ^[18] ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L^{2}{\sqrt {3}}}$ ${\displaystyle {\tfrac {L}{2}}}$ ${\textstyle 4{\bigl (}{\tfrac {L}{2}}{\bigr )}^{2}{\sqrt {3}}=L^{2}{\sqrt {3}}}$ ${\textstyle {\tfrac {\log 4}{\log 2}}=2}$ ${\displaystyle {\tfrac {L}{\sqrt {2}}}}$

Анимация вращающегося тетрикса 4-го уровня, показывающая, как некоторые ортогональные проекции тетрикса могут заполнять плоскость — в этом интерактивном SVG перемещайтесь влево и вправо по тетриксу, чтобы повернуть 3D-модель.

История

Вацлав Серпинский описал треугольник Серпинского в 1915 году. Однако подобные узоры уже появляются как распространенный мотив инкрустированной каменной кладки в косматском стиле XIII века . ^[19]

Аполлоническая прокладка была впервые описана Аполлонием Пергским (3 век до н.э.) и далее проанализирована Готфридом Лейбницем (17 век) и является изогнутым предшественником треугольника Серпинского 20-го века. ^[20]

Этимология

Использование слова «прокладка» для обозначения треугольника Серпинского относится к прокладкам , которые встречаются в двигателях и которые иногда имеют ряд отверстий уменьшающегося размера, похожих на фрактал; это использование было придумано Бенуа Мандельбротом , который считал, что фрактал похож на «часть, которая предотвращает утечки в двигателях». ^[21]

Смотрите также

• Аполлоническая прокладка , набор взаимно касающихся кругов с той же комбинаторной структурой, что и треугольник Серпинского.
• Список фракталов по размерности Хаусдорфа
• Ковер Серпинского , еще один фрактал, названный в честь Серпинского и образованный путем многократного удаления квадратов из большего квадрата.
• Triforce — реликвия из серии Legend of Zelda.

Рекомендации

1. "" Прокладка Серпинского от Trema Removal"".
2. Майкл Барнсли ; и другие. (2003), «Фракталы и суперфракталы с V-переменной», arXiv : math/0312314
3. НОВА (программа общественного телевидения). Странная новая наука о хаосе (эпизод). Общественная телекомпания WGBH Boston. Вышел в эфир 31 января 1989 года.
4. Фельдман, Дэвид П. (2012), «17.4 Игра в хаос», Хаос и фракталы: элементарное введение , Oxford University Press, стр. 178–180, ISBN 9780199566440.
5. Прусинкевич, П. (1986), «Графические приложения L-систем» (PDF) , Proceedings of Graphics Interface '86 / Vision Interface '86 , стр. 247–253.
6. Серпинский, Вацлав (1915). «Sur une courbe не рекламирует точку est un point de разветвления». Компет. Ренд. акад. наук. Париж . 160 : 302–305.
7. Брунори, Паола; Магроне, Паола; Лалли, Лаура Тедескини (07 июля 2018 г.), Императорский порфир и золотой лист: треугольник Серпинского в средневековом римском монастыре, Достижения в области интеллектуальных систем и вычислений, том. 809, Springer International Publishing, стр. 595–609, номер номера : 10.1007/978-3-319-95588-9_49, ISBN. 9783319955872, S2CID  125313277
8. Румпф, Томас (2010), «Игра жизни Конвея, ускоренная с помощью OpenCL» (PDF) , Материалы одиннадцатой Международной конференции по мембранным вычислениям (CMC 11) , стр. 459–462.
9. Билотта, Элеонора ; Пантано, Пьетро (лето 2005 г.), «Явления возникновения паттернов в 2D клеточных автоматах», Artificial Life , 11 (3): 339–362, doi : 10.1162/1064546054407167, PMID  16053574, S2CID  7842605.
10. Хованова, Таня; Не, Эрик; Пураник, Алок (2014), «Треугольник Серпинского и автомат Улама-Уорбертона», Math Horizons , 23 (1): 5–9, arXiv : 1408.5937 , doi : 10.4169/mathhorizons.23.1.5, S2CID  125503155
11. Стюарт, Ян (2006), Как разрезать торт: и другие математические загадки, Oxford University Press, стр. 145, ISBN 9780191500718.
12. Ян Стюарт, «Как разрезать торт», Oxford University Press, стр. 180.
13. Ромик, Дэн (2006), «Кратчайшие пути в графе Ханойской башни и конечных автоматах», SIAM Journal on Discrete Mathematics , 20 (3): 610–62, arXiv : math.CO/0310109 , doi : 10.1137/050628660 , МР  2272218, S2CID  8342396.
14. Фальконер, Кеннет (1990). Фрактальная геометрия: математические основы и приложения . Чичестер: Джон Уайли. п. 120. ИСБН 978-0-471-92287-2. Збл  0689.28003.
15. Хельмберг, Гилберт (2007), Знакомство с фракталами, Уолтер де Грюйтер, стр. 41, ISBN 9783110190922.
16. «Множество способов формирования прокладки Серпинского» .
17. Шеннон, Кэтлин М.; Бардзелл, Майкл Дж. (ноябрь 2003 г.). «Узоры в треугольнике Паскаля - с изюминкой». Конвергенция . Математическая ассоциация Америки . Проверено 29 марта 2015 г.
18. Джонс, Хью; Кампа, Аурелио (1993), «Абстрактные и естественные формы из систем итерированных функций», Тельманн, Нью-Мексико; Тельманн, Д. (ред.), Общение с виртуальными мирами , Международная серия CGS CG, Токио: Springer, стр. 332–344, doi : 10.1007/978-4-431-68456-5_27
19. Уильямс, Ким (декабрь 1997 г.). Стюарт, Ян (ред.). «Тротуары Космати». Математический турист. Математический интеллект . 19 (1): 41–45. дои : 10.1007/bf03024339. S2CID  189885713.
20. Мандельброт Б (1983). Фрактальная геометрия природы . Нью-Йорк: WH Freeman. п. 170. ИСБН 978-0-7167-1186-5.
    Асте Т., Вейр Д. (2008). В поисках идеальной упаковки (2-е изд.). Нью-Йорк: Тейлор и Фрэнсис. стр. 131–138. ISBN 978-1-4200-6817-7.
21. Бенедетто, Джон; Войцех, Чая. Интеграция и современный анализ . п. 408.

Внешние ссылки

• «Прокладка Серпинского», Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Решето Серпинского». Математический мир .
• Ротемунд, Пол В.К.; Пападакис, Ник; Уинфри, Эрик (2004). «Алгоритмическая самосборка треугольников Серпинского ДНК». ПЛОС Биология . 2 (12): е424. doi : 10.1371/journal.pbio.0020424 . ПМК  534809 . ПМИД  15583715.
• Прокладка Серпинского от Trema Removal в кратчайшие сроки
• Прокладка Серпинского и Ханойская башня в разрубке
• Графический процессор в реальном времени сгенерировал треугольник Серпинского в 3D
• Треугольники Пифагора, Вацлав Серпинский, Courier Corporation, 2003 г.
• A067771 Число вершин в треугольнике Серпинского порядка n. в OEIS
• Интерактивная версия игры хаоса