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

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

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

• 1 Конструкции
  • 1.1 Удаление треугольников
  • 1.2 Сжатие и дублирование
  • 1.3 Игра хаоса
  • 1.4 Конструкция наконечника стрелы из прокладки Серпинского
  • 1.5 Клеточные автоматы
  • 1. 6 Треугольник Паскаля
  • 1.7 Ханойские башни
• 2 Свойства
• 3 Обобщение на другие модули
• 4 Аналоги в высших измерениях
• 5 История
• 6 Этимология
• 7 См. Также
• 8 Ссылки
• 9 Внешние ссылки

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

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

Развитие треугольника Серпинского

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

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

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

Сжатие и дублирование

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

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

Обратите внимание, что этот бесконечный процесс не зависит от начальной формы. треугольник - так просто яснее. Первые несколько шагов, начинающиеся, например, с квадрата, также имеют тенденцию к треугольнику Серпинского. Майкл Барнсли использовал изображение рыбы, чтобы проиллюстрировать это в своей статье «Фракталы с V-переменной и суперфракталы».

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

Реальный фрактал - это то, что будет получено после бесконечного количество итераций. Более формально его описывают в терминах функций на замкнутых множествах точек. Если мы позволим d A обозначить расширение в 1/2 раза вокруг точки A, тогда треугольник Серпинского с углами A, B и C будет фиксированным набором преобразования d A ∪ d B ∪ d C.

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

Игра хаос

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

Если взять точку и применить каждое из преобразований d A, d B и d C случайным образом, результирующие точки будут плотными в треугольнике Серпинского, поэтому следующий алгоритм снова будет генерировать произвольно близкие приближения к нему:

Начните с маркировки p1, p2и p3как углы треугольника Серпинского, а случайная точка v1. Установите vn + 1 = 1/2 (vn+ prn), где r n - случайное число 1, 2 или 3. Нарисуйте точки от v1до v∞. Если первая точка v1была точкой на треугольнике Серпинского, то все точки vnлежат на треугольнике Серпинского. Если первая точка v1, лежащая в пределах периметра треугольника, не является точкой на треугольнике Серпинского, ни одна из точек vnне будет лежать на треугольнике Серпинского, однако они будут сходиться на треугольнике. Если v1находится за пределами треугольника, единственный способ vnприземлиться на фактический треугольник - это если vnнаходится на том, что было бы частью треугольника, если бы треугольник был бесконечно большим.

Анимированное построение треугольника Серпинского. Треугольник Серпинского очерчен фрактальным деревом с тремя ветвями, образующими угол между собой 60 °. Если угол уменьшить, треугольник можно непрерывно преобразовать во фрактал, напоминающий дерево. Каждый подтреугольник n-й итерации детерминированного треугольника Серпинского имеет адрес на дереве с n уровнями (если n = ∞, то дерево тоже фрактал); T = сверху / по центру, L = слева, R = справа, и эти последовательности могут представлять как детерминированную форму, так и «серию ходов в игре хаоса»

Или проще:

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

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

Треугольник Серпинского с использованием повторяющейся системы функций

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

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

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

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

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

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

Треугольник Серпинского также появляется в некоторых клеточных автоматах (таких как Правило 90 ), включая те, которые относятся к Игре жизни Конвея. Например, Жизнеподобный клеточный автомат B1 / S12 при применении к отдельной ячейке сгенерирует четыре приближения треугольника Серпинского. Очень длинная линия толщиной в одну ячейку в стандартной жизни создаст два зеркальных треугольника Серпинского. Пространственно-временная диаграмма паттерна репликатора в клеточном автомате также часто напоминает треугольник Серпинского, такой как обычный репликатор в HighLife. Треугольник Серпинского также можно найти в автомате Улама-Уорбертона и в автомате Хекса-Улама-Уорбертона.

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

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

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

Башни Ханоя

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

.

Для целого числа измерений d при удвоении стороны объекта, создаются 2 копии, т.е. 2 копии для 1-мерного объекта, 4 копии для 2-х мерного объекта и 8 копий для 3-х мерного объекта. Для треугольника Серпинского удвоение его стороны создает 3 копии самого себя. Таким образом, треугольник Серпинского имеет размерность Хаусдорфа log (3) / log (2) = log 2 3 ≈ 1,585, что следует из решения 2 = 3 для d.

Площадь треугольника Серпинского равна нулю (в мере Лебега ). Площадь, остающаяся после каждой итерации, составляет 3/4 площади предыдущей итерации, и бесконечное количество итераций приводит к площади, приближающейся к нулю.

Точки треугольника Серпинского имеют простую характеристику в барицентрические координаты. Если точка имеет координаты (0.u 1u2u3…, 0.v 1v2v3…, 0.w 1w2w3…), выраженные как двоичные числа, то точка находится в треугольнике Серпинского, если и только если u i + v i + w i = 1 для всех i.

Обобщение треугольника Серпинского также можно сгенерировать с помощью треугольника Паскаля, если используется другой модуль Modulo. Итерацию n можно создать, взяв треугольник Паскаля с P строками и раскрасив числа по их значению для x mod P. Когда n приближается к бесконечности, создается фрактал.

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

И наоборот, фрактал также можно сгенерировать, начав с треугольника, продублируя его и расположив n (n + 1) / 2 новых фигур в той же ориентации в более крупный аналогичный треугольник с вершинами предыдущие рисунки касаются, затем повторяют этот шаг.

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

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

Тетрикс, построенный из исходного тетраэдра с длиной стороны L, обладает тем свойством, что общая площадь поверхности остается постоянной при каждой итерации. Начальная площадь поверхности тетраэдра (итерация-0) с длиной стороны L равна L√3. Следующая итерация состоит из четырех копий с длиной стороны L / 2, поэтому общая площадь снова равна 4 (L / 2) √3 = 4L · √3 / 4 = L√3. При этом объем конструкции на каждом этапе уменьшается вдвое и поэтому приближается к нулю. Предел этого процесса не имеет ни объема, ни поверхности, но, как и прокладка Серпинского, представляет собой сложную связанную кривую. Его размерность Хаусдорфа равна log (4) / log (2) = 2. Если все точки проецируются на плоскость, параллельную двум внешним краям, они точно заполняют квадрат со стороной L / √2 без перекрытия.

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

Вацлав Серпинский описал треугольник Серпинского в 1915 году. Однако подобные узоры появляются уже в 13 веке Космати мозаики в соборе Ананьи, Италия и других местах центральной Италии, для ковров во многих местах, таких как неф римской базилики Санта-Мария-ин-Космедин, а также для отдельных треугольников, расположенных по кругу в нескольких церквях и базиликах. В случае изолированного треугольника итерация не менее трех уровней.

Средневековый треугольник с исторически достоверной датировкой был недавно изучен. Он сделан из порфира и золотого листа, изолирован, итерация 4 уровня

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

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

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

1. ^ Конверсано, Элиза; Тедескини-Лалли, Лаура (2011), «Треугольники Серпинского в камне на средневековых полах в Риме» (PDF), APLIMAT Journal of Applied Mathematics, 4 : 114, 122
2. ^ Брунори, Паола; Магроне, Паола; Лалли, Лаура Тедескини (2018-07-07), «Имперский Порфирий и Золотой Лист: Треугольник Серпинского в средневековом римском монастыре», Достижения в области интеллектуальных систем и вычислений, Springer International Publishing, стр. 595–609, doi : 10.1007 / 978-3-319-95588-9_49, ISBN 9783319955872
3. ^«Прокладка Серпинского от Trema Removal»
4. ^Майкл Барнсли ; и другие. (2003), "V-переменные фракталы и суперфракталы", arXiv : math / 0312314
5. ^NOVA (программа общественного телевидения). Странная новая наука хаоса (эпизод). Станция общественного телевидения WGBH Бостон. Вышла в эфир 31 января 1989 г.
6. ^Фельдман, Дэвид П. (2012), «17.4 Игра хаоса», Хаос и фракталы: элементарное введение, Oxford University Press, стр. 178–180, ISBN 9780199566440.
7. ^Peitgen, Heinz-Otto; Юргенс, Хартмут; Саупе, Дитмар; Малецкий, Эван; Perciante, Терри; и Юнкер, Ли (1991). Фракталы для класса: стратегические действия Том первый, с.39. Спрингер-Верлаг, Нью-Йорк. ISBN 0-387-97346-X и ISBN 3-540-97346-X.
8. ^Прусинкевич, П.. (1986), «Графические приложения L-систем» (PDF), Proceedings of Graphics Interface '86 / Vision Interface '86, стр. 247–253.
9. ^Серпинский, Вацлав (1915). "Sur une courbe dont tout point est un point de ramification". Компт. Ренд. Акад. Sci. Париж. 160 : 302–305 - через https://gallica.bnf.fr/ark:/12148/bpt6k31131.
10. ^Румпф, Томас (2010), «Игра жизни Конвея» ускорено с помощью OpenCL " (PDF), Труды одиннадцатой международной конференции по мембранным вычислениям (CMC 11), стр. 459–462.
11. ^Билотта, Элеонора; Пантано, Пьетро (лето 2005 г.), «Эмерджентные явления формирования паттернов в двумерных клеточных автоматах», «Искусственная жизнь», 11 (3): 339–362, doi : 10.1162 / 1064546054407167, ПМИД 16053574.
12. ^Хованова Таня; Не, Эрик; Пураник, Алок (2014), «Треугольник Серпинского и автомат Улама-Уорбертона», Math Horizons, 23 (1): 5–9, arXiv : 1408.5937
13. ^Стюарт, Ян (2006), Как разрезать торт: и другие математические головоломки, Oxford University Press, стр. 145, ISBN 9780191500718.
14. ^Ромик, Дэн (2006), «Кратчайшие пути в графе Ханойской башни и конечные автоматы», журнал SIAM по дискретной математике, 20 (3): 610–62, arXiv : math.CO/0310109, doi : 10.1137 / 050628660, MR 2272218.
15. ^Falconer, Кеннет (1990). Фрактальная геометрия: математические основы и приложения. Чичестер: Джон Вили. п. 120. ISBN 978-0-471-92287-2. Zbl 0689.28003.
16. ^Хельмберг, Гилберт (2007), Знакомство с фракталами, Вальтер де Грюйтер, стр. 41, ISBN 9783110190922.
17. ^«Множество способов формирования прокладки Серпинского».
18. ^Шеннон и Бардзелл, Кэтлин и Майкл, «Узоры в треугольнике Паскаля - с поворотом - сначала Твист: Что это такое? », maa.org, Математическая ассоциация Америки, получено 29 марта 2015 г.
19. ^Джонс, Хью; Кампа, Аурелио (1993), «Абстрактные и естественные формы из повторяющихся функциональных систем», в Thalmann, N.M.; Thalmann, D. (eds.), Communicating with Virtual Worlds, CGS CG International Series, Tokyo: Springer, pp. 332–344, doi : 10.1007 / 978-4-431-68456- 5_27
20. ^Вольфрам, Стивен (2002), Новый вид науки, Wolfram Media, стр. 43, 873
21. ^«Геометрическая мозаика пола (треугольники Серпинского), неф Санта-Мария in Cosmedin, Forum Boarium, Rome ", 5 сентября 2011 г., Flickr
22. ^Mandelbrot B (1983). Фрактальная геометрия природы. Нью-Йорк: У. Х. Фриман. п. 170. ISBN 978-0-7167-1186-5.. Aste T, Weaire D (2008). В поисках идеальной упаковки (2-е изд.). Нью-Йорк: Тейлор и Фрэнсис. С. 131–138. ISBN 978-1-4200-6817-7.
23. ^Бенедетто, Джон; Войцех, Чая. Интеграция и современный анализ. п. 408.

На Викискладе есть материалы, связанные с треугольниками Серпинского.

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