close

Вход

Забыли?

вход по аккаунту

?

Ладейные полиномы в многомерных пространствах.

код для вставкиСкачать
Ладейные полиномы в многомерных пространствах
# 10, октябрь 2012
DOI: 10.7463/1012.0463238
Белоусов А. И., Исаев Д. С., Ремень И. В., Донцов В. В.
УДК 519.115.1
Россия, МГТУ им. Н.Э. Баумана
al_belous@bk.ru
idenx@ya.ru
bhyk@yandex.ru
dont.val@yandex.ru
Введение.
Как известно (см. [1]), для произвольной прямоугольной шахматной доски
ладейным числом называют число способов поставить на эту доску n не бьющих друг
друга ладей (при произвольном фиксированном n). Впервые эти числа ввел советский
математик С.Е. Аршон в середине 30-х годов. Вычисление ладейных чисел для двумерных
и трехмерных досок рассмотрено в работах [1-5]. Для досок более высокой размерности
проблема вычисления таких чисел, как и проблема создания эффективного алгоритма их
вычисления, пока остается открытой.
В настоящей статье рассматривается обобщение данной теории на многомерный
случай (для произвольной размерности), а также приведен алгоритм для вычисления
ладейных чисел.
В комбинаторике известна задача подсчета количества подстановок с
запрещенными позициями. Если провести аналогию с шахматами, это количество
способов постановки на доску n не бьющих друг друга ладей, но с дополнительным
запретом ставить ладьи на некоторые клетки доски. В работе исследована задача подсчета
количества подстановок с запрещенными позициями в случае произвольной размерности,
получена формула для подсчета этого количества подстановок и приведены примеры ее
практического применения.
1. Вывод основных формул.
Рассмотрим следующую задачу. Дано множество векторов с d компонентами F.
Требуется вычислить
– количество k-элементных подмножеств множества F, таких,
что все -ые компоненты векторов этого подмножества попарно различны для всех
.
Известное из [1] определение ладейного полинома без труда переносится на
многомерный случай.
http://technomag.edu.ru/doc/463238.html
139
Определение 1. Пусть F – множество векторов с d компонентами. Ладейным
полиномом назовем производящую функцию
при определенных выше числах
(F).
С точки зрения «шахматной интерпретации» такое число (для заданного k) равно числу
способов поставить k ладей в небоевые позиции на данной многомерной доске, т.е. таким
образом, чтобы никакие две ладьи не имели на доске общих координат (в обычном
двумерном случае не находились бы на одной горизонтали или на одной вертикали).
Теорема 1. Пусть F – множество векторов с d компонентами, S – вектор из
множества F. Пусть
– множество векторов F, из которого удалены все вектора, в
которых хотя бы одна координата совпадает с той же координатой S. Пусть
–
множество F, из которого удален вектор S.
Тогда ладейный полином F определяется формулой
=
+
.
Доказательство. Если из F выбрать k векторов, то вектор S либо выбран, либо не
выбран. Если он выбран, то остальные k – 1 векторов должны быть выбраны из
, что
осуществимо
выбраны из
способами. Если S не выбрано, то все k векторов должны быть
, что осуществимо
способами. Таким образом,
.
Так как
, то
,
но
Таким образом,
=
+
, что и требовалось доказать.
Приведем алгоритм в псевдокоде, вычисляющий ладейный полином.
Алгоритм 1.
function R(F)
10.7463/1012.0463238
140
begin
if Length(F) = 1
return (x+1);
if Length(F) = 0
return 1;
return x*R
+R( );
end
В полученном многочлене коэффициенты при
будут равны
Рассмотрим следующую задачу. Дано
| =
конечных множеств
.
). Сколько существует матриц с
, m = min(
неупорядоченными столбцами размера d × m, таких, что каждая -ая строка представляет
собой перестановку m-элементного подмножества множества
для любого
?
Теорема 2. Пусть U – множество определенных выше матриц. Тогда их число
составит
Доказательство. Пусть в матрице каким-то образом выбрана 1-ая строка. Это
можно сделать
способами. Зафиксируем ее. Известно, что количество перестановок
множества из k элементов равно k!. Рассмотрим
-ую строку матрицы
состоит из
m! =
). Она
способами. Тогда,
пользуясь комбинаторным правилом умножения, получаем:
.
Но
=
, поэтому в итоге
.
Теорема доказана.
Заметим, что при d = 2,
А именно, пусть d = 2,
={a, b, c, d, e, f, g ,h},
http://technomag.edu.ru/doc/463238.html
={1,2,3,4,5,6,7,8}.
141
Тогда общая задача сводится к следующей: сколько существует матриц вида
, где вторая строка – перестановка множества
? Или, что
эквивалентно, сколькими способами можно расставить 8 ладей на доске 8×8 так, чтобы
они не били друг друга? Очевидно, что их можно расставить 8! способами.
В качестве примера рассмотрим такую задачу.
Дано
конечных множеств
. Мощность -го множества
=
,
). Дано конечное множество F, называемое множеством “запрещенных
m = min(
позиций”, состоящее из векторов
, таких, что для любого
.
Сколько существует матриц с неупорядоченными столбцами размера d × m, таких
что каждая -я строка является перестановкой m – элементного подмножества множества
для любого
и ни один столбец матрицы не принадлежит множеству F
(множество всех таких матриц может быть обозначено как U\F)?
Теорема 3. Число
.
Доказательство.
Рассмотрим любую матрицу из множества
Число таких матриц
, определенного в условии теоремы 2.
(в силу теоремы 2).
Рассмотрим подмножества векторов
из множества F, таких что
. Обозначим через
содержащих столбец
множество матриц
. Найдем количество таких матриц | |. Так как один столбец в
матрице уже определен ( ), нужно найти, сколь много матриц размера d × (m–1) в
множестве . Применяя формулу (1), получаем:
,
где
количество векторов в множестве
.
Далее:
.
Обозначим
– количество векторов в множестве F. Тогда
.
Рассмотрим
матриц из множества
фиксированы.
и содержащих столбцы
матриц размера d ×(m–2) в множестве
, причем
. Тогда |
| - количество
. Так как два столбца
=
уже определены, то
,
10.7463/1012.0463238
142
.
Здесь
или количество двухэлементных подмножеств
множества F, таких, что все компоненты обоих векторов попарно различны.
Аналогично,
для
=
где
или
количество
,
подмножеств
k-элементных
множества F, таких, что все компоненты обоих векторов попарно различны.
По формуле включения-исключения:
=
=
= |U| -
,
,
, а так как
, получаем
+
=
.
(2)
Теорема доказана.
Из формулы (2) при d = 2 и
имеем
=
,
что является известной формулой для числа подстановок с запрещенными позициями (см.
[1]).
2. Примеры приложений.
1) Рассмотрим “трехмерные шахматы”. Сколькими способами можно расставить n
ладей в трехмерном шахматном кубе n × n × n так, чтобы они не били друг друга и не
располагались на главной диагонали куба?
В данном примере множество «запрещенных векторов» F – всевозможные dкомпонентные векторы вида
для всех
; d = 3,
,
.
Так
как
,
=
;
.
Таким образом, n ладей можно расставить
пособами.
В частности, при d = 2 получаем так называемое «число беспорядков» ([1]):
=
http://technomag.edu.ru/doc/463238.html
.
143
2) Даны вещества, разбитые на d непересекающихся классов, в каждом классе по
веществ,
. Определённые вещества нельзя смешивать. Сколькими способами
можно получить смеси из n веществ, используя все вещества?
Пусть F – множество всевозможных кортежей длины d, i-ый элемент кортежа это
вещество i-го класса и во всех кортежах на соответствующих местах расположены
вещества, запрещенные к смешиванию. И пусть m = min(
).
Ответ можно получить, посчитав
,
вычисляются по приведенному выше алгоритму.
где числа
3) Компания по отправке подарков закупила
упаковок для них. Подарки необходимо отправить
подарков и
подарочных
адресатам. Известно, что некоторые
адресаты не любят определенные цвета упаковок, а некоторые подарки не сочетаются с
определёнными цветами упаковок. Сколькими способами можно разослать подарки
адресатам?
Данная задача аналогична предыдущей, здесь d = 3,
.
Множество запрещенных кортежей формируется так же.
4) В бар пришли n математиков, каждый снимает свою шляпу, пальто и шарф и
вешает на стойку. По выходу из бара, каждый из математиков случайным образом берет
одно пальто, шляпу и шарф. Найти вероятность события, при котором ни один из
математиков не наденет правильно свою одежду.
В данной задаче имеем размерность пространства d = 3 (три множества:
. Сформируем кортежи выбранной по
математиков, пальто, шляп),
выходу из бара одежды вида (
),
, где каждый
элементы кортежа – это предметы одежды, который взял математик при выходе из бара и
сам математик. Множество из n таких кортежей однозначно задает событие,
происходящее при выходе математиков из бара. Для того чтобы, ни один из математиков
не надел правильно свою одежду, необходимо, чтобы в этом множестве не содержалось
кортежей вида:
(
), ,
.
Пусть F - множество таких запрещенных кортежей.
По формуле (2), так как
, получаем
.
Далее:
=
10.7463/1012.0463238
.
144
Итак, число возможных способов взять одежду так, чтобы ни один из математиков
не надел свою одежду правильно:
.
Теперь подсчитаем общее число способов взять одежду. По формуле (1)
|U|=
.
Используя классическое определение вероятности, получаем вероятность искомого
события P =
.
Заключение
В работе дано обобщение конструкции ладейных полиномов на многомерный (для
произвольной размерности) случай. Выведены основные формулы, доказана теорема о
декомпозиции многомерной доски и на этой основе разработан алгоритм вычисления
ладейных полиномов.
Кроме этого, получены результаты, обобщающие (на многомерный случай) метод
подсчета числа подстановок с запрещенными позициями.
Все указанные результаты получены впервые. Они представляют собой полезный
аппарат для решения ряда прикладных задач. Некоторые примеры таких задач приведены
в последнем разделе статьи.
Список литературы
1. Андерсон Дж. Комбинаторика и дискретная математика.- М.: Издательский дом
«Вильямс», 2003.- 960 с.
2. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и
симметрические функции.- М.: Мир, 2005.- 767 с.
3. Кохась К.П. Ладейные числа и многочлены.- М.: Изд-во МЦНМО, 2003.- 20 с.
4. Krzywonos N., Alayont F. Rook Polynomials in Higher Dimensions. Режим доступа:
http://scholarworks.gvsu.edu/sss/29 (дата обращения 29.06.2012).
5. Benjamin Z. Rook polynomials for chessboard for two and three dimensions. Режим доступа:
http://people.rit.edu/~hxssma/Ben-thesis.pdf (дата обращения 29.06.2012)
http://technomag.edu.ru/doc/463238.html
145
Rook polynomials in multydimensional spaces
# 10, October 2012
DOI: 10.7463/1012.0463238
Belousov A.I., Isaev D.S., Remen' I.V., Doncov V.V.
Russia, Bauman Moscow State Technical University
al_belous@bk.ru
idenx@ya.ru
bhyk@yandex.ru
dont.val@yandex.ru
The authors consider a generalization of the well-known combinatorial structure of rook
polynomials for boards of arbitrary dimension. The authors obtained basic formulas and
examples of their application in practice. An algorithm of computing rook polynomials was
developed.
Publications with keywords:chess board, permutation, rook polynomial, permutation with
forbidden positions
Publications with words:chess board, permutation, rook polynomial, permutation with
forbidden positions
References
1. Anderson A. J. Discrete mathematics with combinatorics, Prentice. Hall, Upper Saddle River,
New Jersey, 2001. (Russ. ed.: Anderson Dzh. Kombinatorika i diskretnaia matematika. Moscow,
Izdatel'skii dom «Vil'iams», 2003. 960 p.).
2. Stanley R.P. Enumerative Combinatorics. Vol. 2. New York/Cambridge, Cambridge
University Press, 1999. (Russ. ed.: Stenli R. Perechislitel'naia kombinatorika. Derev'ia,
proizvodiashchie funktsii i simmetricheskie funktsii. Moscow, Mir, 2005. 767 p.).
3. Kokhas' K.P. Ladeinye chisla i mnogochleny [Rook numbers and polynomials]. Moscow,
MTsNMO Publ., 2003. 20 p.
4. Krzywonos N., Alayont F. Rook Polynomials in Higher Dimensions. Available at:
http://scholarworks.gvsu.edu/sss/29 , accessed 29.06.2012.
5. Benjamin Z. Rook polynomials for chessboard for two and three dimensions. Available at:
http://people.rit.edu/~hxssma/Ben-thesis.pdf , accessed 29.06.2012.
10.7463/1012.0463238
146
Документ
Категория
Без категории
Просмотров
9
Размер файла
334 Кб
Теги
полином, пространство, многомерная, ладейные
1/--страниц
Пожаловаться на содержимое документа