Preview

Чебышевский сборник

Расширенный поиск

ОЦЕНКА ЧИСЛА Р2–РАЗБИЕНИЙ ПЛОСКОСТИ НА ПОЛИМИНО ЗАДАННОЙ ПЛОЩАДИ

https://doi.org/10.22405/2226-8383-2016-17-3-204-214

Полный текст:

Аннотация

В работе рассматривается задача о числе \(p\)2--разбиений плоскости на полимино заданной площади. Полимино представляет собой связную фигуру на плоскости, составленную из конечного числа единичных квадратов, примыкающих друг к другу по сторонам. В настоящее время активно исследуются различные перичислительные комбинаторные задачи, связанные с полимино. Представляет интерес подсчет числа полимино определенных классов, а также подсчет числа разбиений конечных фигур или всей плоскости на полимино определенного типа. Разбиение называется \(p\)2--разбиением, если любую фигуру разбиения можно перевести в любую другую фигуру параллельным переносом или центральной симметрией, причем это преобразование переводит все разбиение в себя. \(p2\)-разбиения являются частным случаем правильных разбиений плоскости. Пусть \(t(n)\) -- число \(p2\)--разбиений плоскости на полимино площади \(n\), решетка периодов которых является подрешеткой решетки \(\mathbb{Z}^2\). Доказано, что справедливо неравенство \( C_12^n \leq t(n)\leq C_2n^4(2.68)^n\). При доказательстве нижней оценки использована явная конструкция, позволяющая построить требуемое число \(p2\)--разбиений плоскости. Доказательство верхней оценки основано на критерии Конвея существования \(p2\)--разбиений плоскости, а также на теории самонепересекающихся блужданий на квадратной решетке.
Ранее аналогичные результаты были получены авторами в задаче подсчета числа решетчатых разбений плоскости на полимино заданной площади, а также в задаче подсчета числа решетчатых разбиений плоскости на центрально-симметричные полимино.

Об авторах

А. В. Шутов
Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых
Россия

кандидат физико-математических наук, доцент, доцент кафедры управления и информатики в технических и экономических системах



Е. В. Коломейкина

Россия


Список литературы

1. Ammann R., Grunbaum B., Shephard G. Aperiodic tiles // Discrete and Computational Geometry. 1991. Vol. 6, no. 1, P. 1–25.

2. Barequet G., Rote G., Shalah M.


Для цитирования:


Шутов А.В., Коломейкина Е.В. ОЦЕНКА ЧИСЛА Р2–РАЗБИЕНИЙ ПЛОСКОСТИ НА ПОЛИМИНО ЗАДАННОЙ ПЛОЩАДИ. Чебышевский сборник. 2016;17(3):204-214. https://doi.org/10.22405/2226-8383-2016-17-3-204-214

For citation:


Shutov A.V., Kolomeykina E.V. THE ESTIMATION OF THE NUMBER OF P2–TILINGS OF A PLANE BY A GIVEN AREA POLYOMINO. Chebyshevskii Sbornik. 2016;17(3):204-214. (In Russ.) https://doi.org/10.22405/2226-8383-2016-17-3-204-214

Просмотров: 144


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)