2014 dxdy logo

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

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




 
 Порождающее множество перестановок
Сообщение22.10.2016, 23:45 
Очевидно, что многократной перестановкой соседних элементов можно осуществить любую перестановку. То есть множество перестановок вида $1, 2, \dots, i-2, i-1, i+1, i, i+2, i+3, \dots, n$ является порождающим в том смысле, что любую перестановку можно представить комбинацией этих. Таких перестановок всего $n-1$ для данного $n$.
А существуют ли порождающие множества размера $n-2$, или даже ещё меньше?

 
 
 
 Re: Порождающее множество перестановок
Сообщение23.10.2016, 00:04 
Аватара пользователя
Существует. Если хотите основательно, то почитайте про симметрические группы. Если позабавиться, то рассмотрите перестановку первых двух элементов и ещё одну, многократным повторением которых можно переставить любые два соседних элемента.
Привиделась картина Ван-Гога "Прогулка в тюрьме(?)". Понурые заключённые ходят по кругу, а надзиратель может тычком палки поменять местами двух проходящих мимо него бедолаг. Впрочем, может быть они заслужили такую долю.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group