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

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

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

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

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

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

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

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

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

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

в которой я-й член подсчитывает количество частичных перестановок с поддержкой размера я, то есть количество частичных перестановок с я не дырочные записи. В качестве альтернативы, это может быть вычислено отношение повторения

{ Displaystyle P (n) = 2nP (n-1) - (n-1) ^ {2} P (n-2).}

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

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

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

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

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

^ Штраубинг, Говард (1983), "Комбинаторное доказательство теоремы Кэли-Гамильтона", Дискретная математика, 43 (2–3): 273–279, Дои:10.1016 / 0012-365X (83) 90164-4, МИСТЕР 0685635.
^ Ku, C. Y .; Лидер, I. (2006), "Теорема Эрдеша-Ко-Радо для частичных перестановок", Дискретная математика, 306 (1): 74–86, Дои:10.1016 / j.disc.2005.11.007, МИСТЕР 2202076.
^ ^а ^б Клаэссон, Андерс; Jelínek, Vít; Елинкова, Ева; Китаев, Сергей (2011), «Избегание паттернов при частичных перестановках», Электронный журнал комбинаторики, 18 (1): Документы 25, 41, МИСТЕР 2770130.
^ Бурштейн, Александр; Ланкхэм, Исайя (2010), «Сортировка с ограниченным терпением и предотвращение шаблонов с ограничениями», Шаблоны перестановок, Лондонская математика. Soc. Lecture Note Ser., 376, Кембридж: Cambridge Univ. Press, стр. 233–257, arXiv:математика / 0512122, Дои:10.1017 / CBO9780511902499.013, МИСТЕР 2732833.

[1] Штраубинг, Говард (1983), "Комбинаторное доказательство теоремы Кэли-Гамильтона", Дискретная математика, 43 (2–3): 273–279, Дои:10.1016 / 0012-365X (83) 90164-4, МИСТЕР 0685635.

[2] Ku, C. Y .; Лидер, I. (2006), "Теорема Эрдеша-Ко-Радо для частичных перестановок", Дискретная математика, 306 (1): 74–86, Дои:10.1016 / j.disc.2005.11.007, МИСТЕР 2202076.

[cjjk-3] а ^б Клаэссон, Андерс; Jelínek, Vít; Елинкова, Ева; Китаев, Сергей (2011), «Избегание паттернов при частичных перестановках», Электронный журнал комбинаторики, 18 (1): Документы 25, 41, МИСТЕР 2770130.

[4] Бурштейн, Александр; Ланкхэм, Исайя (2010), «Сортировка с ограниченным терпением и предотвращение шаблонов с ограничениями», Шаблоны перестановок, Лондонская математика. Soc. Lecture Note Ser., 376, Кембридж: Cambridge Univ. Press, стр. 233–257, arXiv:математика / 0512122, Дои:10.1017 / CBO9780511902499.013, МИСТЕР 2732833.

[1]

[2]

[3]

[4]