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

[Chernoknizhnik]

Захотелось мне найти их число в $S_n$ для произвольного $n$. Ответ я получил, но далеко не удовлетворительный. Может быть, есть более простые подходы и более изящные формулы для вычисления этого числа? Возможно, в мои рассуждения закралась ошибка. Рассуждал я следующим образом:

Широко известно, что подстановки сопряжены тогда и только тогда, когда совпадают их цикловые типы, т.е. совпадают соответствующие им диаграммы Юнга. Поэтому нам достаточно посчитать количество диаграмм Юнга веса $n$ (в диаграмме Юнга в каждой нижеследующей строке количество клеток не менее, чем в предыдущей).
Найдем количество $u_0$ диаграмм Юнга, в которых нет одноклеточных строчек, $u_1$ - одна одноклеточная строка, $u_2$ - две и т.д.

Ответом будет число $u_0+u_1+u_2+...+u_n$ ($u_n$, кстати, равно $1$ и соответствует здесь лишь тождественная подстановка). Понятно, что $u_k$ есть число подстановок, фиксирующих $k$ точек. Итак, вычисляем $u_k$.

Вычислим число $\delta_n$ подстановок без неподвижных точек (т.н. беспорядков), оно равно, как известно $n!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+...+\frac{(-1)^n}{n!})$. Становится понятно, что число $u_k$ подстановок, фиксирующих ровно $k$ точек, равно $\binom nk \delta_{n-k}$.
Число беспорядков, кстати, это ближайшее целое к $\frac{n!}{e}$, где $e$ - замечательный предел (или как там его?), так что число $\delta_n$ и $\binom nk \delta_n$ считаются несложно.
Есть ли более короткие пути? Формула Бернсайда для перечисления орбит тоже ничего хорошего, на мой взгляд, не дает.

[mihiv]

Число диаграмм Юнга равно количеству различных представлений числа $n$ в виде суммы нескольких слагаемых, а Вы находите по -моему число различных подстановок.

[Chernoknizhnik]

Но представления числа $n$ в виде суммы нескольких слагаемых взаимно однозначно соответствуют классам сопряженности, т.к. $g(x_1,x_2,...x_k)g^{-1}=(gx_1,gx_2...gx_k)$ и обратно, если цикловые типы подстановок, т.е. наборы $(m_1,...m_n)$, где $m_i$ - число $i$-циклов, одинаковы, то подстановки сопряжены.

[ИСН]

Ну дак это и есть A000041.

Цитата:

a(n) is also the number of conjugacy classes in the symmetric group S_n

[Chernoknizhnik]

Вот спасибо!