Частичная перестановка

Выбор в определенном порядке

В комбинаторной математике частичная перестановка или последовательность без повторения на конечном множестве S является взаимно однозначной связью между двумя заданными подмножествами S. То есть оно определяется двумя подмножествами U и V одинакового размера и взаимно однозначным отображением U в V . Эквивалентно, это частичная функция на S , которую можно расширить до перестановки . ^{[1] [2]}

Представление

Обычно рассматривается случай, когда набор S представляет собой просто набор {1, 2, ..., n } первых n целых чисел. В этом случае частичная перестановка может быть представлена ​​строкой из n символов , некоторые из которых представляют собой различные числа в диапазоне от 1 до, а остальные представляют собой специальный «дырочный» символ ◊. В этой формулировке область U частичной перестановки состоит из позиций в строке, не содержащих дырок, и каждая такая позиция отображается в число в этой позиции. Например, строка «1 ◊ 2» будет представлять собой частичную перестановку, которая отображает 1 в себя и отображает 3 в 2. ^[3] Семь частичных перестановок двух элементов: ${\displaystyle n}$

◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.

Комбинаторное перечисление

Количество частичных перестановок n элементов для n = 0, 1, 2,... задается целочисленной последовательностью

1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ... (последовательность A002720 в OEIS )

где n- й элемент последовательности определяется формулой суммирования

${\displaystyle \sum _{i=0}^{n}i!{\binom {n}{i}}^{2}}$

в котором i-й член подсчитывает количество частичных перестановок с поддержкой размера i , то есть количество частичных перестановок с i недырочными записями. Альтернативно, его можно вычислить с помощью рекуррентного соотношения

${\displaystyle P(n)=2nP(n-1)-(n-1)^{2}P(n-2).}$

Это определяется следующим образом:

1. ${\displaystyle P(n-1)}$частичные перестановки, в которых последние элементы каждого набора опущены:
2. ${\displaystyle P(n-1)}$частичные перестановки, при которых конечные элементы каждого набора сопоставляются друг с другом.
3. ${\displaystyle (n-1)P(n-1)}$частичные перестановки, при которых последний элемент первого набора включен, но не сопоставляется с последним элементом второго набора
4. ${\displaystyle (n-1)P(n-1)}$частичные перестановки, при которых последний элемент второго набора включен, но не сопоставляется с последним элементом первого набора
5. ${\displaystyle -(n-1)^{2}P(n-2)}$, частичные перестановки, включенные в оба подсчета 3 и 4, те перестановки, в которые включены конечные элементы обоих наборов, но не сопоставляются друг с другом.

Ограниченные частичные перестановки

Некоторые авторы ограничивают частичные перестановки так, что либо область ^[4] , либо диапазон ^[3] биекции вынужден состоять из первых k элементов в наборе из n переставляемых элементов для некоторого k . В первом случае частичная перестановка длины k из n- множества представляет собой просто последовательность k термов из n -множества без повторений. (В элементарной комбинаторике эти объекты иногда ошибочно называют « k -перестановками » n -множества.)

Рекомендации

1. Штраубинг, Ховард (1983), «Комбинаторное доказательство теоремы Кэли-Гамильтона», Discrete Mathematics , 43 (2–3): 273–279, doi : 10.1016/0012-365X(83)90164-4 , MR  0685635.
2. Ку, CY; Лидер, И. (2006), «Теорема Эрдеша-Ко-Радо для частичных перестановок», Discrete Mathematics , 306 (1): 74–86, doi : 10.1016/j.disc.2005.11.007 , MR  2202076.
3. Классон, Андерс; Елинек, Вит; Елинкова, Ева; Китаев, Сергей (2011), «Избегание шаблонов в частичных перестановках», Электронный журнал комбинаторики , 18 (1): Статьи 25, 41, MR  2770130.
4. Бурштейн, Александр; Ланкхэм, Исайя (2010), «Ограниченная сортировка по терпению и избегание запрещенных шаблонов», Шаблоны перестановок , London Math. Соц. Лекционная конспект. Сер., т. 1, с. 376, Кембридж: Кембриджский университет. Press, стр. 233–257, arXiv : math/0512122 , doi : 10.1017/CBO9780511902499.013, MR  2732833..