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

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

Представительство

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

◊◊, ◊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- й элемент последовательности определяется формулой суммирования

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

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

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

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

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

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

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

Ссылки

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

[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 .

[cjjk-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 .

[1]

[2]

[3]

[4]