2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 сортировка транспозициями
Сообщение13.02.2022, 03:18 
Модератор
Аватара пользователя


11/01/06
5660
Напомню, что транспозицией называется перестановка переставляющая местами два элемента. Таким образом, на множестве $\{1,2,\dots,n\}$ существует $\frac{n(n-1)}2$ различных транспозиций.

Докажите, что для любую перестановку множества $\{1,2,\dots,n\}$ той же чётности что и $\frac{n(n-1)}2$ можно отсортировать к тождественной, применив (в некотором порядке) каждую из $\frac{n(n-1)}2$ транспозиций ровно по одному разу.

 Профиль  
                  
 
 Re: сортировка транспозициями
Сообщение13.02.2022, 03:29 
Заслуженный участник


16/02/13
4105
Владивосток
Я чего-то не понял в условии? Никак не могу доказать, что перестановку $\{1,2\}$ можно привести к тождественной, применив в любом порядке каждую из одной перестановки.

 Профиль  
                  
 
 Re: сортировка транспозициями
Сообщение13.02.2022, 04:31 
Модератор
Аватара пользователя


11/01/06
5660
iifat, конечно не любую, а любую чётную. Спасибо за бдительность. Исправлено.

 Профиль  
                  
 
 Re: сортировка транспозициями
Сообщение13.02.2022, 06:58 
Заслуженный участник


20/12/10
8858
Число $n(n-1)/2$ может быть как четным, так и нечетным. "Любую подстановку, четность которой совпадает с четностью $n(n-1)/2$, можно ..." --- видимо, такая формулировка должна быть.

 Профиль  
                  
 
 Re: сортировка транспозициями
Сообщение13.02.2022, 18:06 
Модератор
Аватара пользователя


11/01/06
5660
nnosipov, конечно! Исправил. Теперь вроде все чисто.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group