Формула числа перестановок в классе сопряженных элементов

[genk]

Здравствуйте. В монографиях по теории групп и комбинаторному анализу часто приводится формула для числа перестановок симметрической группы S_n в данном классе сопряженных элементов
s_{(\nu)}=\dfrac{n!}{2^{\nu_2}3^{\nu_3}\dots n^{\nu_n}\nu_1!\nu_2!\dots \nu_n!} (обобщение формулы см.,например,здесь).
В формуле (\nu)=(\nu_1,\nu_2,\dots,\nu_n)-циклическая структура(цикленный тип)перестановки,т.е.при разложении перестановки в произведение независимых циклов встречается \nu_1 циклов длины 1,\nu_2 циклов длины 2 и т.д.,\nu_n циклов длины n.Например,для перестановки (123)(45)(67)(8)(9) \in S_9 имеем \nu=(2,2,1,0,0,0,0,0,0),и формула дает s_{(\nu)}=\dfrac{9!}{2^2 3^1 2! 2!}=7560.
Формула громоздка для вычислений,и алгоритм требует предварительной записи цикленного типа.
Порывшись в своих студенческих записях,я обнаружил более простую формулу,которую и предлагаю для пользования заинтересованным читателям.Надо просто записать перестановку в циклическом разложении(неважно,в каком порядке) и в знаменателе дроби перемножить д л и н ы всех циклов(игнорируя,понятно,циклы единичной длины) и соответствующие факториалы(уже не игнорируя единичные циклы).
Вот эта формула: s_{(\nu)}=\dfrac{n!}{n_1 n_2\dots n_k \nu_1! \nu_2!\dots \nu_k!} (здесь n_i-длина цикла,встречающегося \nu_i раз).
Так,для вышеприведенного примера s_{(\nu)}=\dfrac{9!}{3\cdot 2\cdot 2\cdot 2!\cdot 2!}=7560,а для перестановки (1234)(567)(89)(10) \in S_{10} получим s_{(\nu)}=\dfrac{10!}{4\cdot 3\cdot 2}=151200.

[DeBill]

genk
Сравнивая две Ваши формулы, видим: в них написано в точности одно и то же....

[genk]

DeBill в сообщении #1493754 писал(а):

Сравнивая две Ваши формулы, видим: в них написано в точности одно и то же....

Конечно же одно и тоже! Речь идет совсем о другом:если записать разложение перестановки на циклы,то вторая формула гораздо проще для вычислений(начинающим изучать теорию групп).

[tolstopuz]

genk в сообщении #1493219 писал(а):

Вот эта формула: s_{(\nu)}=\dfrac{n!}{n_1 n_2\dots n_k \nu_1! \nu_2!\dots \nu_k!} (здесь n_i-длина цикла,встречающегося \nu_i раз).
Так,для вышеприведенного примера s_{(\nu)}=\dfrac{9!}{3\cdot 2\cdot 2\cdot 2!\cdot 2!}=7560

Что-то не сходится. Чему в этом примере равны $n_1$, $n_2$, $n_3$, $\nu_1$, $\nu_2$, $\nu_3$?

[genk]

tolstopuz в сообщении #1493850 писал(а):

Что-то не сходится. Чему в этом примере равны $n_1$, $n_2$, $n_3$, $\nu_1$, $\nu_2$, $\nu_3$?

Все прекрасно сходится.В формуле надо перемножить д л и н ы всех циклов(это будет 3*2*2*1*1) и 2!2!-поскольку в перестановке цикл длины 3 встречается 1 раз,цикл длины 2-дважды,а цикл длины 1-ТОЖЕ два раза.

[tolstopuz]

genk в сообщении #1493977 писал(а):

tolstopuz в сообщении #1493850 писал(а):

Что-то не сходится. Чему в этом примере равны $n_1$, $n_2$, $n_3$, $\nu_1$, $\nu_2$, $\nu_3$?

Все прекрасно сходится.В формуле надо перемножить д л и н ы всех циклов(это будет 3*2*2*1*1) и 2!2!-поскольку в перестановке цикл длины 3 встречается 1 раз,цикл длины 2-дважды,а цикл длины 1-ТОЖЕ два раза.

В знаменателе вашей формулы есть $k$ множителей вида $n_i$ и $k$ (столько же) множителей вида $\nu_i!$, где, как вы сами написали, $n_i$ - длина цикла, встречающегося $\nu_i$ раз.

Следуя вашей инструкции, имеем $n_1=3$, $\nu_1=1$, $n_2=2$, $\nu_2=2$, $n_3=1$, $\nu_3=2$.

Подставьте эти числа в вашу формулу и посмотрите, что получится, если следовать вашей инструкции.

[genk]

tolstopuz
Формально Вы правы,но ведь формула должна быть привязана к вычислительному алгоритму,который достаточно понятен.В примере n_1=3,n_2=2,n_3=2(а не 1),n_4=1,n_5=1.Тогда \nu_1=1,\nu_2=2,\nu_3=2 и все получается.
В формуле индекс \nu_k можно заменить на любой другой \nu_m и считать,что,начиная с первого цикла,\nu_i это число циклов следующей длины в разложении перестановки.
Тем не менее,спасибо за любые замечания.

[tolstopuz]

genk в сообщении #1494171 писал(а):

Формально Вы правы,но ведь формула должна быть привязана к вычислительному алгоритму,который достаточно понятен.

В этом и дело. У вас есть верное словесное описание того, что вы делаете, а для солидности вы пририсовали к нему неверную формулу, которой не пользуетесь.

[genk]

tolstopuz в сообщении #1494174 писал(а):

В этом и дело. У вас есть верное словесное описание того, что вы делаете, а для солидности вы пририсовали к нему неверную формулу, которой не пользуетесь.

В том то и дело,что формулой(в новой редакции) можно пользоваться-она должна быть перед глазами,иначе возможны ошибки при вычислении(как у вас для значения n_3).

[tolstopuz]

genk в сообщении #1493219 писал(а):

(здесь n_i-длина цикла,встречающегося \nu_i раз).

genk в сообщении #1494171 писал(а):

В примере n_1=3,n_2=2,n_3=2(а не 1),n_4=1,n_5=1.Тогда \nu_1=1,\nu_2=2,\nu_3=2 и все получается.

Подставляем $i=1$: 3 - длина цикла, встречающегося 1 раз.
Подставляем $i=2$: 2 - длина цикла, встречающегося 2 раза.
Подставляем $i=3$: 2 - длина цикла, встречающегося 2 раза.
Подставляем $i=4$: 1 - длина цикла, встречающегося [неверный индекс] раз.
Подставляем $i=5$: 1 - длина цикла, встречающегося [неверный индекс] раз.

Надеюсь, я правильно подставил ваши числа в ваше объяснение?