Знак перестановки. Число транспозиций. Число инверсий

[khasanov.sm]

Добрый день!


Помогите пожалуйста разобраться со следующим упражнением:

Пусть $\delta\left\lbrace\sigma\right\rbrace - общее число инверсий относительно перестановки $\sigma$. Показать, что найдутся $\delta\left\lbrace\sigma\right\rbrace$ транспозиций $\tau_1\tau_2...\tau_{\delta\left\lbrace\sigma\right\rbrace}$:

$\tau_1\tau_2...\tau_{\delta\left\lbrace\sigma\right\rbrace}\circ \sigma=e$,

где $e$ единичная перестановка.

Что имею:
Рассмотрим произведение одной из транспозиций с инверсией $\tau = (\sigma(i),\sigma(j))$ на перестановку $\sigma$:

$(\sigma(i),\sigma(j)) \circ \sigma$

В полученной перестановке пара номеров $(i,j)$ не будет составлять инверсию относительно $\sigma$. Продолжая умножение на остальные $k-1$ возможных транспозиций, получим перестановку с числом инверсий равным 0. А это свойство единичной перестановки.

Верно?

[svv]

Нет, это было бы слишком просто. Вот где подводный камень:

khasanov.sm в сообщении #1439036 писал(а):

В полученной перестановке пара номеров $(i,j)$ не будет составлять инверсию относительно $\sigma$.

Да, этой инверсии больше не будет, но Ваша "исправляющая" транспозиция может создать новые инверсии.

Например, пусть элементы $2,3,7$ в перестановке шли в таком порядке: $7,2,3$. Вы меняете местами $7$ и $3$, чтобы устранить их инверсию, но тем самым создаёте новую инверсию — элементов $2$ и $3$, которой до транспозиции не было.

khasanov.sm в сообщении #1439036 писал(а):

Продолжая умножение на остальные $k-1$ возможных транспозиций, получим перестановку с числом инверсий равным 0. А это свойство единичной перестановки.

Может быть, но это пока не доказано.

[khasanov.sm]

svv в сообщении #1439037 писал(а):

Да, этой инверсии больше не будет, но Ваша "исправляющая" транспозиция может создать новые инверсии.

Например, пусть элементы $2,3,7$ в перестановке шли в таком порядке: $7,2,3$. Вы меняете местами $7$ и $3$, чтобы устранить их инверсию, но тем самым создаёте новую инверсию — элементов $2$ и $3$, которой до транспозиции не было.

Тогда необходимо по порядку применять такие транспозиции, которые на всех $k$ шагах будут «устранять» только одну инверсию.

[svv]

Пример, который я привёл, показывает, что не стоит выбирать необходимые транспозиции заранее, исходя из $\sigma$.
Другой пример: допустим, в $\sigma$ элементы $1,2,3$ стоят в порядке $3,2,1$. Вы видите здесь инверсии пар $(1,3), (1,2), (2,3)$. Но это не значит, что надо запланировать три транспозиции: после перестановки местами элементов $1$ и $3$ цель уже достигнута. Если же мы попытаемся применить ещё какие-то транспозиции, будет хуже.

Но планировать все транспозиции заранее и не нужно. Достаточно показать, что, действуя по самому простому и естественному алгоритму, Вы будете на каждом шаге уменьшать число инверсий. И тогда не более чем через $k$ шагов их не останется совсем.

[khasanov.sm]

svv в сообщении #1439315 писал(а):

Вы будете на каждом шаге уменьшать число инверсий. И тогда не более чем через $k$ шагов их не останется совсем.

Я ошибочно воспринял слова «показать, что найдутся k (общее число инверсий) таких транспозиций $\tau_1,\tau_2,...,\tau_k$, приводящих $\sigma$ к $e$», переформулировав в «...РОВНО k таких транспозиций ...». Ваша поправка «не более чем..» внесла ясность.

Таким образом, сам «простой и естественный» алгоритм есть суть последовательное применение транспозиций, понижающих общее число инверсий $\delta(\sigma)$ ровно на 1:

$\delta(\tau_i \circ \sigma)=\delta(\tau_{i-1} \circ \sigma)-1$

[svv]

Или больше чем на $1$ (несложно увидеть, что это ничему не помешает, хотя в задаче требуется ровно $k$ транспозиций).
Тогда необходимо показать, что такая транспозиция всегда существует.
Она действительно существует. Более того, устраняя инверсию транспозицией, Вы всегда уменьшаете общее число инверсий (хотя некоторые новые инверсии могут возникать). Сможете доказать это?

-- Вт фев 11, 2020 12:54:51 --

khasanov.sm в сообщении #1439332 писал(а):

Ваша поправка «не более чем..» внесла ясность.

Ну, вот пример с $3,2,1$ как раз иллюстрирует это. Инверсий три, транспозиция необходима одна.

[Someone]

svv в сообщении #1439333 писал(а):

Инверсий три, транспозиция необходима одна.

Но условие задачи требует именно трёх.

[svv]

Как я заметил,

svv в сообщении #1439333 писал(а):

несложно увидеть, что это ничему не помешает, хотя в задаче требуется ровно $k$ транспозиций

Раскрываю секрет (автору темы не читать!).

(Оффтоп)

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

[khasanov.sm]

svv в сообщении #1439333 писал(а):

Более того, устраняя инверсию транспозицией, Вы всегда уменьшаете общее число инверсий (хотя некоторые новые инверсии могут возникать). Сможете доказать это?

Пожалуй да:

Рассмотрим любую транспозицию $\tau_{ij} = (\sigma(i) \sigma(j)) : i < j, \sigma(i)>\sigma(j)$, при умножении на $\sigma $ которой образуются новые инверсии вида $ (\sigma(j),\sigma(p)) : i< j < p ,\sigma(i) >\sigma(j) > \sigma(p)$. Тогда справедливо, что количество образованных инверсий равно количеству "побочно устраненных" инверсий при композиции $\tau_{ij} \circ \sigma$ :

$ (\sigma(i),\sigma(p)) : i< p ,\sigma(i) > \sigma(p)$

Таким образом, любая транспозиция $\tau_{ij} $ уменьшает число инверсий на 1.

Спасибо!

[svv]

khasanov.sm в сообщении #1439412 писал(а):

Таким образом, любая транспозиция $\tau_{ij} $ уменьшает число инверсий на 1.

Хм, а как же мой пример «3-2-1», где перестановка местами $3$ и $1$ убивает сразу три инверсии?

[khasanov.sm]

svv в сообщении #1439472 писал(а):

Хм, а как же мой пример «3-2-1», где перестановка местами $3$ и $1$ убивает сразу три инверсии?

Данная оговорка справедлива для любой транспозиции с побочно возникающими инверсиями относительно перестановки $\sigma$.

Таким образом я утверждаю, что любая транспозиция $\tau_{ij} = (\sigma(i) \sigma(j)): i < j, \sigma(i) > \sigma(j) $ уменьшает общее число инверсий.