3.6. Ладейные многочлены и многочлены попаданий

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

3.6.1. Ладейные многочлены

• Определение. Доской запрещенных позиций называется произвольный набор выделенных клеток шахматной доски, сохраняющих свое расположение относительно других клеток доски. Пример доски запрещенных позиций показан на рис. 3.1.

• Определение. Пусть С — доска запрещенных позиций. Введем обозначения: количество способов расставить к ладей на доске запрещенных позиций так, чтобы они не били друг друга; количество способов расстановки О ладей на доске запрещенных позиций, т.е. способов не ставить ладьи на доску. Ладьи считаются неразличимыми. Производящую функцию последовательности будем называть ладейным многочленом доски С и обозначать

Задача. Найти ладейный многочлен для доски на рис. 3.2.

Решение. Непосредственным подсчетом можно установить, что Тогда

Задача. Найти ладейный многочлен доски на рис. 3.3.

Решение. Непосредственным подсчетом можно установить, что Тогда

Задача. Найти ладейный многочлен доски на рис. 3.4.

Решение. Непосредственным подсчетом можно установить, что Тогда

Определение. Доски называются независимыми, если их клетки располагаются на различных горизонталях и вертикалях. Пример независимых досок показан на рис. 3.5.

Рис. 3.1

Рис. 3.2

Рис. 3.3

Рис. 3.4

Рис. 3.5

Свойства ладейных многочленов

• Свойство 1. Правило произведения. Пусть ладейные многочлены независимых досок Если доска то Доказательство. Пусть расстановка ладей на доске

— расстановка ладей на доске Тогда перестановка ладей на доске Верно и обратное. Пусть и множество расстановок ладей на доске, соответственно Тогда прямое произведение множество расстановок ладей на доске С.

Обозначим веса расстановок: где число ладей в перестановке где число ладей в перестановке Тогда вес перестановки равен

В соответствии с тем, как введены веса перестановок, ладейные многочлены можно записать как сумму весов элементов множеств:

Многочлены удовлетворяют всем условиям правила обобщенного произведения (см. п.3.4), в соответствии с которым

Задача. Найти ладейный многочлен доски С на рис. 3.6. Пусть доска из одной клетки, Ясно, что доска С состоит из независимых досок Отсюда следует, что

Рис. 3.6

• Свойство 2. Правило суммы. Пусть С — доска запрещенных позиций. Введем обозначения: — доска с ладьей в клетке а доска с удаленной клеткой а Тогда

Для доказательства данного свойства вновь рассмотрим ладейный многочлен как сумму весов перестановок. Все расстановки множества разобьем на два подмножества перестановки с ладьей на клетке перестановки, которые не занимают клетку а.

Тогда

Множитель х перед скобкой — это вес ладьи в перестановке которая поставлена на выделенную клетку а. Задача. Найти для доски на рис. 3.7. Решение. Воспользуемся правилом суммы, по которому

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

Рис. 3.7

Рис. 3.8

• Свойство 3 для прямоугольных досок. Пусть С — прямоугольная доска запрещенных позиций размером число горизонталей; число вертикалей (рис. 3.8). На квадратной доске размером к можно способами расставить владей. Различных досок к х к на доске можно выбрать способами Отсюда число способов расставить к ладей на исходной прямоугольной доске. Тогда

Задача. Найти для прямоугольной доски С размером

Решение.

Коэффициент при показывает, что число способов поставить две ладьи на такую доску равно 6.

3.6.2. Многочлены попаданий

• Определение. Пусть дана квадратная доска размером с запрещенными позициями (рис. 3.9). Обозначим через количество перестановок на квадратной доске ладей, к из которых занимают запрещенные позиции. Многочленом попадания называется производящая функция последовательности

Рис. 3.9

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

сочетаниям длины свойств, число сочетаний С.

Принцип включения и исключения позволяет определить

Так как нас интересует лишь количество перестановок, то будем полагать Нетрудно установить, что где количество способов расставить владей на запрещенных позициях доски Тогда

Заметим, что для всех С другой стороны, если то для всех Поэтому последнее выражение примет вид или Найденное выражение позволяет записать многочлен попаданий в виде

Суммирование выполняется по координатам узлов сетки на рис. 3.10. Замена переменных суммирования в последнем выражении позволяет упростить многочлен попаданий и приводит его к виду где суммирование уже выполняется по узлам сетки на рис. 3.11.

Рис. 3.10

Рис. 3.11

Таким образом,

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

Заметим, что Тогда многочлен попаданий перепишем в виде

где Таким образом,

Задача. Найти многочлен попаданий для доски с запрещенными позициями на рис. 3.12. Запрещенные позиции отмечены темным цветом.

Рис. 3.12

Решение. Найдем ладейный многочлен доски запрещенных позиций, которая состоит из двух независимых досок. Тогда

Значит

Итак,

Анализ коэффициентов при показывает, что число перестановок, в которых ладьи не занимают запрещенных клеток, равно 1 (коэффициент при перестановок с одной ладьей на запрещенных позициях — 3 (коэффициент при перестановок с двумя ладьями на запрещенных позициях — 1 (коэффициент при перестановок с тремя ладьями на запрещенных позициях —1 (коэффициент при ).