Необычные перестановки

[gogoshik]

Подскажите, плиз, как можно более строго выразить перестановки элементов, где каждый элемент встречается дважды (частный случай перестановкок на мультимножестве)? Какой то продвинутой теории я не нашел.

Например, мне нужно описать перестановки элементов на наборе $(112233)$? Допускается, чтобы элементы менялись местами, но только в порядке их парного перечисления (тут скорее всего я не точно выражаюсь). Например, разрешены такие перестановки: $(121233), (122313), (122331)$. Но не допустимы перестановки: $(211233), (132231)$. То есть 1 должна стоять на первом месте всегда, после неё может стоять либо $1$, либо $2$, но не $3$ и т.д. То есть новый элемент перестановки заданного набора может появиться не раньше, чем появился предыдущий элемент из этого набора.

[Munin]

Не очень понятно, какое условие вы накладываете. Но мне кажется, оно равносильно тому, что ваша перестановка как функция должна быть нестрого меньше, чем $f(x)=x.$

[grizzly]

Munin в сообщении #1340385 писал(а):

Не очень понятно, какое условие вы накладываете.

Если я правильно понял Вашу идею обозначения функцией, тогда так. Пусть есть набор $(a_1, a_2, ... , a_k), k\ge n, a_i\in \{1,2,...,n\}$. Перестановка $(c_1,...,c_k)$ (здесь набор $\{c_i\}$ совпадает с набором $\{a_i\}$ с учётом кратности) считается допустимой, если $c_1=1, c_i\le \max(c_1,...,c_{i-1})+1, i=2,...,k$.

Я думаю, что имеется в виду именно это, но моя запись мне самому совсем не нравится.

[Munin]

Тогда равносильно ли это $c_i\leq i$?

[grizzly]

Я же говорю, что нет. Перестановка $\{1,1,3,3,2,2\}$ недопустима, хотя удовлетворяет условию $c_i\le i$.

[Munin]

Понял.

[gogoshik]

Спасибо за некоторые идеи. Но мне все равно не понятно, как аккуратно формализовать перестановки на мультимножестве с заданными условиями.

Munin в сообщении #1340385 писал(а):

Не очень понятно, какое условие вы накладываете.

Как бы Вам объяснить понятнее. Пусть нам задан упорядоченный набор $n$ чисел. Мы строим мультимножество элементов в котором каждый элемент встречается ровно дважды. Очевидно, что мощность мультимножества будет $2n$. Нам нужно получить все возможные комбинации мультимножества, которые допускают расположение элементов по следующему правилу: на первом месте всегда стоит первый элемент упорядоченного набора, а каждый новый элемент мультимножества (взятый из упорядоченного набора) может располагаться только после того, как были уже расположены предыдущие элементы заданного упорядоченного набора.

[Someone]

gogoshik в сообщении #1340479 писал(а):

Мы строим мультимножество элементов в котором каждый элемент встречается ровно дважды.

Упорядоченное?

gogoshik в сообщении #1340479 писал(а):

на первом месте всегда стоит первый элемент упорядоченного набора, а каждый новый элемент мультимножества (взятый из упорядоченного набора) может располагаться только после того, как были уже расположены предыдущие элементы заданного упорядоченного набора.

Таких "комбинаций" — ровно одна.

Или уточняйте, что Вам нужно. Может быть, на примере, скажем, упорядоченного мультимножества $(1,1,2,2,3,3)$

[gogoshik]

Не думаю, но тут есть путаница. Я говорю про заданный упорядоченный набор. И про мультимножество. Это не одно и то же.
Допустим, нам задан упорядоченный набор трех элементов: $(1, 2, 3)$. Исходя из этого нам нужно построить мультимножество из шести элементов по определенному правилу, которые я пытался описать. По такому правилу можно получить мультимножества не только упорядоченные (не буду все выписывать): $(1, 1, 2, 2, 3, 3), (1, 2, 1, 3, 2, 3), (1, 2, 3, 1, 3, 2)$. Видите, новый элемент $2$ взятый из первоначального упорядоченного набора $(1, 2, 3)$ встречается в мультимножестве только после того, как была уже $1$, а $3$ располагается только после того, как уже были расположены (хотя бы по одному разу) элементы $1$ и $2$ из упорядоченного набора $(1, 2, 3)$.

[Someone]

Теперь понятно.

[gogoshik]

Так вот, теперь я хочу как то аккуратно формализовать перестановки на таких (полученных по таким правилам) мультимножествах. Но не знаю как, так как в классическом варианте перестановка не содержит повторений чисел, а здесь каждое число встречается дважды. Ну, например:

$\pi_{1} = \begin{pmatrix} 1 &1 &2 &2 &3 &3\\ 1 &2 &3 &1 &2 &3 \end{pmatrix}$

$\pi_{2} = \begin{pmatrix} 1 &2 &1 &2 &3 &3\\ 1 &1 &2 &3 &3 &2 \end{pmatrix}$

[Someone]

У Вас чисто комбинаторная задача. Группа перестановок к ней не имеет никакого отношения. Поэтому не выдумывайте ненужных заморочек.
Можно, конечно, попытаться привлечь теорему Пойа о перечислении (придётся рассматривать группу перестановок на $2n$ элементах), но, может быть, найдётся более простой путь. И я не гарантирую, что теорема Пойа поможет.

[gogoshik]

Someone в сообщении #1340495 писал(а):

чисто комбинаторная задача

Спасибо, но не очень понятно, что это значит в моем случае?

[Someone]

gogoshik в сообщении #1340497 писал(а):

не очень понятно, что это значит в моем случае

Ну, есть такая область математики, которая называется "комбинаторика". Одна из основных задач комбинаторики — подсчёт числа элементов всяких конечных множеств. Ваша задача именно в этом и состоит.

[gogoshik]

Someone в сообщении #1340499 писал(а):

подсчёт числа элементов всяких конечных множеств

Ну, я наверное не так выразился. Мне не нужно считать число элементов или число комбинаций элементов на конечном множестве. Я хотел бы как то формализовать, найти или придумать наиболее подходящий "язык" для описания объектов (мультимножеств с дополнительной структурой). А потом на этом "языке" получать общие результаты. Ну, например, доказать, что переставляя какие-то элементы объекта каким-то определенным образом мы всегда будем получать эквивалентные объекты или объекты одного класса. Или найти инвариантные преобразования объекта.