Комбинаторика, перестановки переходящие друг в друга

[Lokkie]

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

[whiterussian]

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

[Lokkie]

whiterussian в сообщении #362085 писал(а):

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

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

[AlexandreII]

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

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

[Lokkie]

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

[Magazanik]

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

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

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

[AlexandreII]

Цитата:

нециклическая подгруппа симметрической группы подстановок всегда содержит не менее трех циклических подгрупп

Пусть $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 циклических подгруппы есть всегда.

[Magazanik]

AlexandreII

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

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


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

[AlexandreII]

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

[Magazanik]

AlexandreII
Спасибо.
Сажусь и пишу. Длинно и нудно -- к сожалению, иначе не умею.

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

[Профессор Снэйп]

Lokkie в сообщении #362082 писал(а):

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

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

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

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

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

(Оффтоп)

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

-- Сб окт 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$.

[AlexandreII]

Цитата:

афтар

????? я думал, здесь сленгом не пользуются.

Если

Цитата:

три нетривиальные циклические подгруппы

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

[Lokkie]

Профессор Снэйп в сообщении #362644 писал(а):

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

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