флеров

Перестановки с ограничениями на местоположение

В задаче о числе беспорядков ищут число перестановок _n , в которых для каждого i некоторые значения (i) запрещены (именно, (i) i). Рассмотрим более общую теорию таких перестановок. Традиционно ее описывают, используя шахматную терминологию. Пусть . Множество B называют доской. Для _n определим график G() перестановки  условием

G() ={(i, (i), i[n]}.

Определим теперь

N_j = {_n : j = B  G()},
r _k = число k - подмножеств множества B, таких, что никакие два элемента не имеют общей координаты,
r _k = число способов разместить k не атакующих друг друга ладей на B.

Мы можем отождествить перестановку _n с размещением n не атакующих друг друга ладей в квадратах (i, (i)) доски . Тогда N_j есть число способов размещения n не атакующих друг друга ладей на доске , при которых в точности j из этих ладей находятся в B. Например, если B = {(1, 1), (2, 2), (3, 3), (3, 4), (4, 4)}, то N₀ = 6, N₁ = 9, N₂ = 7, N₃ = 1, N₄ = 1, r₀ = 1, r₁ = 5, r₂ = 8, r₃ = 5, r₄ = 1. Наша цель - описать числа N_j и, в особенности N₀ , в терминах чисел r _k. Определим многочлен N_n формулой

Теорема 1.15. Имеем

. (1.29)

В частности,

. (1.30)

Первое доказательство.

Пусть C_k есть число пар (, C), где _n и C - k-подмножество множества B  G(). Для каждого j выберем N_j способами перестановку  так, чтобы j = B  G(), а затем C выберем способами. Следовательно, . С другой стороны, можно было бы сначала выбрать r_k способами множество C, а затем расширить его (n - k)! способами до перестановки . Следовательно, C_k = r_k (n - k)!. Поэтому

или, эквивалентно,

Полагая y = x - 1, получаем желаемую формулу ( 1 .29). 

Второе доказательство. Достаточно доказать формулу ( 1 .29) в предположении, что x - положительное целое число. Левая часть формулы ( 1 .29) подсчитывает число способов, которыми можно разместить не атакующие ладьи на доске и пометить каждую ладью на B элементами множества [x]. С другой стороны, такую конфигурацию можно получить, поместив k не атакующих ладей на участок B, пометив каждую из них элементом множества {2, 3, ... , x}, поместив n - k добавочных ладей на доску (n - k)! способами и пометив новые ладьи на B единицами. Это устанавливает желаемое взаимно однозначное соответствие. 

Два доказательства теоремы 1 .15 дают еще одну иллюстрацию двух комбинаторных способов доказательства равенства двух многочленов. Конечно, можно доказать формулу ( 1 .30) прямым применением метода включений-исключений. Такое доказательство нельзя было бы рассматривать как комбинаторное, так как мы не построили явно взаимно однозначное соответствие между двумя множествами. Два доказательства, которые приведены выше, можно рассматривать как “полукомбинаторные”, так как они получаются из прямых формул взаимно однозначного соответствия, включающих параметры x и y соответственно, и затем мы получаем формулу ( 1 .30), полагая y = -1 и x = 0.

1.16. Пример. (Снова задача о беспорядках). Возьмем B={(1, 1), (2, 2), ... , (n, n)}. Мы хотим вычислить N₀ = D(n). Ясно, что , так что

1.17. Пример. (Задача о супружеских парах (о гостях).) Эта известная задача формулируется следующим образом: сколькими способами можно рассадить за круглым столом n супружеских пар так, чтобы никакая пара не сидела рядом и женщины чередовались с мужчинами. Задача эквивалентна поиску числа перестановок _n , для которых (i)i, i+1(mod n) для всех i[n]. Другими словами, мы ищем число N₀ для доски B = {(1, 1), (2, 2), ... , (n, n), (1, 2), (2, 3), ... , (n - 1, n), (n, 1)}. Взглянув на рисунок доски B, мы видим, что r_k равно числу способов, которыми можно выбрать k из 2n расположенных на окружности точек так, чтобы среди них не было двух последовательных (соседних).

Лемма 1.18. Число способов, которыми можно выбрать k точек из m точек на окружности так, чтобы среди них не было двух последовательных (соседних) точек, равно

Первое доказательство. Пусть f(m, k) - искомое число, и пусть g(m, k) - число способов выбрать k не последовательных точек из m точек, расположенных по окружности, а затем покрасить k выбранных точек в красный цвет и одну из неокрашенных точек покрасить в синий цвет. Ясно, что

g(m, k) = (m - k)f(m, k).

Но можно вычислить g(m, k) также следующим образом. Сначала покрасим одну точку в синий цвет m способами. Теперь нам нужно покрасить в красный цвет k точек, выбранных из линейного массива m -1 точек так, чтобы среди них не было двух последовательных. Одним из способов дальнейших рассуждений может быть следующий. Расположим m - 1 - k неокрашенных точек в линию и вставим k красных точек в m - k промежутков между неокрашенными точками (считая начало и конец) . Это можно сделать способами. Следовательно, . Откуда

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

Второе доказательство. Пометим точки числами 1, 2, ... , m в возрастающем по часовой стрелке порядке. Мы хотим покрасить k из них в красный цвет, так чтобы не было двух последовательных красных точек. Сначала подсчитаем число возможностей, при которых точка 1 не окрашена в красный цвет. Расположим m- k неокрашенных точек по кругу, пометив одну из них единицей и вставим k красных точек в m - k промежутков между неокрашенными точками способами. С другой стороны, если точка 1 будет покрашена в красный цвет, то расположим m - k + 1 точек по кругу, покрасим одну из этих точек в красный цвет и пометим ее 1, а затем вставим способами k - 1 красную точку на m - k - 1 разрешенных мест.

Следовательно,

. 

На основании доказанной леммы имеем

Утверждение 1.19. Многочлен N_n(x) для доски

B={(i, i), (i, i+1(mod n)): 1  i  n}

дается формулой

В частности, число N₀ перестановок _n, для которых

(i)i, i+1(mod n) при 1  i  n, дается формулой

. 

Содержание