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

редактировать

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

СОДЕРЖАНИЕ

1 Представление
2 Комбинаторное перечисление
3 Ограниченные частичные перестановки
4 ссылки

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

Обычно рассматривается случай, когда множество S - это просто набор {1, 2,..., n } первых n целых чисел. В этом случае частичная перестановка может быть представлена строкой из n символов, некоторые из которых являются различными числами в диапазоне от 1 до, а остальные - специальным символом «дырка» ◊. В этой формулировке область U частичной перестановки состоит из позиций в строке, которые не содержат дыр, и каждая такая позиция отображается на номер в этой позиции. Например, строка «1 ◊ 2» будет представлять частичную перестановку, которая отображает 1 на себя и отображает 3 на 2. Семь частичных перестановок двух элементов: ${\ 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 _ {я = 0} ^ {n} я! {\ binom {n} {i}} ^ {2}}

\ sum_ {i = 0} ^ ni! \ binom {n} {i} ^ 2

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

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

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

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

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

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

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

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