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

Аннотация

В работе рассматривается задача о числе \(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\)--разбиений плоскости, а также на теории самонепересекающихся блужданий на квадратной решетке.
Ранее аналогичные результаты были получены авторами в задаче подсчета числа решетчатых разбений плоскости на полимино заданной площади, а также в задаче подсчета числа решетчатых разбиений плоскости на центрально-симметричные полимино.