2014 dxdy logo

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

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




 
 Комбинаторика, перестановки переходящие друг в друга
Сообщение14.10.2010, 19:41 
Аватара пользователя
Добрый день!
Имеется n отличающихся друг от друга элементов, при выстраивании элементов в круг количество различных способов выстроить их в круге будет n!, но если элементы кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении элементов надо считать одинаковыми. Значит, при вращении элементов в круге получаем количество различных способов перестановки (n-1)!. Подскажите пожалуйста, почему так происходит?

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение14.10.2010, 19:49 
Аватара пользователя
А вы представьте следующее - возьмем наугад один элемент. Все, что справа от него - это другие элементы. Сколько способов расставить их? Правильно, $(n-1)!$.
Теперь вернемся в круг...

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 11:07 
Аватара пользователя
whiterussian в сообщении #362085 писал(а):
А вы представьте следующее - возьмем наугад один элемент. Все, что справа от него - это другие элементы. Сколько способов расставить их? Правильно, $(n-1)!$.
Теперь вернемся в круг...

Просто чисто визуально не могу представить, каким образом перестановки переходят друг в друга? Если при вращении их положение относительно окружающих предметов не существенно, то рассматриваем только их взаимное расположение, т.е., я думаю, рассматривается количество перестановок с учётом постоянного перемещения элементов множества на места соседних элементов. Так ли это, или я не правильно понимаю? Как это представить визуально?

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 14:41 
Все перестановки $n$ элементов образуют $S_n$.
Вам нужно не различать перестановки элементов "по кругу".
То есть две перестановки эквивалентны, если они отличаются на циклическую перестановку $(1 2 3 .. n)$ или ее степень, т.е. на элемент группы $H = \{ (1 2 3.. n)^k, k=0, ... ,n-1\}$

Ваши перестановки, следовательно, это фактор $S_n/H$, порядок равен $n!/n = (n-1)!$

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 17:28 
Аватара пользователя
Выходит в данном случае перестановки повторяются каждые n раз. Соответственно повторяющиеся перестановки эквивалентны. Теперь понятно, Спасибо!

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 20:15 
AlexandreII
Вот он, единственный алгебраист, которому я не успел надоесть своим невежеством...
Может, согласится сказать, верно ли такое предложение: нециклическая подгруппа симметрической группы подстановок всегда содержит не менее трех циклических подгрупп.

С уважением,
Лев Магазаник

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

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 21:28 
Цитата:
нециклическая подгруппа симметрической группы подстановок всегда содержит не менее трех циклических подгрупп


Пусть $H$ - нециклическая подгруппа произвольной группы $G$ (не обязательно группы подстановок).
Тогда
1. $H \ne \{e\}$, иначе она была бы циклической.
2. $\exists a \in H, a \ne e$
3. Рассмотрим набор степеней $\{ a^k, k = 0, 1,... \}$. Этот набор степеней не может перечислять все элементы H, иначе она окажется циклической.
4. Значит, $\exists b \ne a, b\ne e$.
5. Очевидно имеем циклические подгруппы H:
$H_1 = \{e\}$
$H_2$, порожденная элементом a
$H_3$, порожденная элементом b.
Как минимум 3 циклических подгруппы есть всегда.

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 21:41 
AlexandreII

Искренне Вам признателен.

Конечно, это не единственный вопрос, касающийся подгрупп симметрической группы, который меня мучит, а упомянутая Вами чуть выше подстановка с большим циклом $(1 2 3 4 ... n)$ вообще самая большая драма в моей жизни за последние восемь лет, но я уже не рискну злоупотреблять Вашей любезностью. Разве что с особого Вашего позволения, приватным образом...


С уважением,
Лев Магазаник

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 22:13 
Позвольте поинтересоваться, что же там такого произошло с длинным циклом?
Если не хотите выносить это на общее рассмотрение, Вы можете написать личное сообщение

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение15.10.2010, 23:33 
AlexandreII
Спасибо.
Сажусь и пишу. Длинно и нудно -- к сожалению, иначе не умею.

С уважением,
Лев Магазаник

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение16.10.2010, 06:20 
Аватара пользователя
Lokkie в сообщении #362082 писал(а):
Добрый день!
Имеется n отличающихся друг от друга элементов, при выстраивании элементов в круг количество различных способов выстроить их в круге будет n!, но если элементы кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении элементов надо считать одинаковыми. Значит, при вращении элементов в круге получаем количество различных способов перестановки (n-1)!. Подскажите пожалуйста, почему так происходит?

А вот когда мы подносим эти самые выстроенные в круг элементы к зеркалу и смотрим на них через него, мы видим другое взаимное расположение элементов или то же самое?

Вроде логично считать, что то же самое. Ведь само расположение не меняется, меняется лишь точка зрения на него! Допустим, наше "взаимное расположение" --- это $n$ (различных :-) ) человеков (каждый человек уникален!), которые встали вдоль экватора Земли и взялись за руки, замкнув круг. Можно улететь на орбиту и смотреть на них то со стороны Африки, то со стороны Папуа-Новой Гвинеи... Каждый раз мы будем видеть прямо под собой разных людей, хотя на самом деле кольцо этого гигантского хоровода остаётся неизменным, меняется лишь наша точка зрения на него. Но тогда почему мы должны считать, что посмотрев на всё это дело со стороны Южного полюса, а потом со стороны Северного, мы увидим разные кольца людей?!

Конечно, можно возразить, что если мы, зависнув над Северным полюсом, видим лицо человека, то со стороны Южного полюса мы увидим затылок. Но давайте считать, что все наши люди симметричны относительно оси, проходящей через их вытянутые руки. В конце-концов, существуют же сферические кони, а человек, как существо более совершенное, обязан быть симметричным не в меньшей степени!

Ну а коли так, то $(n-1)!$ --- неправильный ответ :D

(Оффтоп)

Если всей Земли народ
За руки возьмётся,
Кто-то в море упадёт ---
Жалко, но придётся!


-- Сб окт 16, 2010 10:32:41 --

AlexandreII в сообщении #362542 писал(а):
Цитата:
нециклическая подгруппа симметрической группы подстановок всегда содержит не менее трех циклических подгрупп


Пусть $H$ - нециклическая подгруппа произвольной группы $G$ (не обязательно группы подстановок).
Тогда
1. $H \ne \{e\}$, иначе она была бы циклической.
2. $\exists a \in H, a \ne e$
3. Рассмотрим набор степеней $\{ a^k, k = 0, 1,... \}$. Этот набор степеней не может перечислять все элементы H, иначе она окажется циклической.
4. Значит, $\exists b \ne a, b\ne e$.
5. Очевидно имеем циклические подгруппы H:
$H_1 = \{e\}$
$H_2$, порожденная элементом a
$H_3$, порожденная элементом b.
Как минимум 3 циклических подгруппы есть всегда.

Я думаю, афтар имел в виду три нетривиальные циклические подгруппы. Так что $H_1 = \{ e \}$ не годится...

На самом деле есть ещё $c \not\in H_3$, так как $H \neq H_3$. Если $c \not\in H_1$, то можно взять $H_4 = \langle c \rangle$, а если $c \in H_1$, то $H_4 = \langle ab \rangle$.

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение16.10.2010, 09:39 
Цитата:
афтар
????? я думал, здесь сленгом не пользуются.

Если
Цитата:
три нетривиальные циклические подгруппы
, то вроде и правда получается. В прежних обозначениях:
$H_1 = \{a^k\}$
$H_2 = \{b^l\}$
$H_3 = \{(ab)^m\}$

 
 
 
 Re: Комбинаторика, перестановки переходящие друг в друга
Сообщение16.10.2010, 09:56 
Аватара пользователя
Профессор Снэйп в сообщении #362644 писал(а):
А вот когда мы подносим эти самые выстроенные в круг элементы к зеркалу и смотрим на них через него, мы видим другое взаимное расположение элементов или то же самое?

Если рассматривать людей, расположенных в круг на плоскости, и считать, что каждый из них уникален, то число перестановок вычисляется как (n-1)!, как-то не приходит в голову этот хоровод перевернуть. А если расположить хоровод по экватору, то получится уже по крайней мере 2 точки наблюдения хоровода - со стороны Северного полушария и со стороны Южного полушария, и поэтому число перестановок будем вычислять так: (n-1)!/2.

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


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