|
Чебышевский сборник, 2016, том 17, выпуск 3, страницы 204–214
(Mi cheb509)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Оценка числа $p2$–разбиений плоскости на полимино заданной площади
А. В. Шутовa, Е. В. Коломейкинаbc a Владимирский государственный университет имени А. Г. и Н. Г. Столетовых
b Математический институт им. В.А. Стеклова Российской академии наук
c Московский государственный технический университет имени Н. Э. Баумана
Аннотация:
В работе рассматривается задача о числе $p2$-разбиений плоскости на полимино заданной площади. Полимино представляет собой связную фигуру на плоскости, составленную из конечного числа единичных квадратов, примыкающих друг к другу по сторонам. В настоящее время активно исследуются различные перичислительные комбинаторные задачи, связанные с полимино. Представляет интерес подсчет числа полимино определенных классов, а также подсчет числа разбиений конечных фигур или всей плоскости на полимино определенного типа. Разбиение называется $p2$-разбиением, если любую фигуру разбиения можно перевести в любую другую фигуру параллельным переносом или центральной симметрией, причем это преобразование переводит все разбиение в себя. $p2$-разбиения являются частным случаем правильных разбиений плоскости. Пусть $t(n)$ — число $p2$-разбиений плоскости на полимино площади $n$, решетка периодов которых является подрешеткой решетки $\mathbb{Z}^2$. Доказано, что справедливо неравенство $ C_12^n \leq t(n)\leq C_2n^4(2.68)^n$. При доказательстве нижней оценки использована явная конструкция, позволяющая построить требуемое число $p2$-разбиений плоскости. Доказательство верхней оценки основано на критерии Конвея существования $p2$-разбиений плоскости, а также на теории самонепересекающихся блужданий на квадратной решетке. Ранее аналогичные результаты были получены авторами в задаче подсчета числа решетчатых разбений плоскости на полимино заданной площади, а также в задаче подсчета числа решетчатых разбиений плоскости на центрально-симметричные полимино.
Библиогафия: 28 названий.
Ключевые слова:
разбиения, правильные разбиения, кристаллографические группы, $p2$-разбиения, полимино, самонепересекающиеся блуждания.
Поступила в редакцию: 12.06.2016 Принята в печать: 13.09.2016
Образец цитирования:
А. В. Шутов, Е. В. Коломейкина, “Оценка числа $p2$–разбиений плоскости на полимино заданной площади”, Чебышевский сб., 17:3 (2016), 204–214
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cheb509 https://www.mathnet.ru/rus/cheb/v17/i3/p204
|
Статистика просмотров: |
Страница аннотации: | 199 | PDF полного текста: | 85 | Список литературы: | 36 |
|