Максимальный порядок элемента группы подстановок

[JMH]

Задача следующая:
Доказать, что порядок любого элемента группы S_n не превосходит e^{n/e}\approx 1.44^n

Двигаюсь в следующем направлении: если подстановка \sigma разлагается в произведение независимых циклов длин p_1,p_2,...,p_n, то ord(\sigma)=LCM\{p_1,p_2,...,p_n\} (LCM - наименьшее общее кратное). Стало быть, нужно найти такое разбиение множества n, что мощности элементов разбиения взаимно просты, т.к. в этом случае НОК равно произведению мощностей, след. максимально. Далее, как известно, число таких целых чисел k, что 0<k\le n, (k,n)=1 - это функция Эйлера \varphi(n) и она вычисляется так: \varphi(n)=n\displaystyle\prod_{p}(1-\frac{1}{p}), где p - все простые делители n. В таком случае \displaystyle\prod_{p}(1-\frac{1}{p})<\displaystyle\lim_{n\to \infty}(1-\frac{1}{n})^n=\frac{1}{e}. Т.о. наибольшее возможное число циклов, на которые разлагается подстановка, равно n/e; Если мы перемножим наибольшую возможную длину цикла n/e число раз (возведем в степень n/e), то мы получим наибольший возможный порядок подстановки \sigma.

Вот тут я застрял - судя по условию задачи, наибольшая возможная длина цикла равна e (а такого не может быть), не могу дотумкать, что здесь не так?
Заранее благодарен за любые идеи!

[ИСН]

А, функция Ландау, да-да. Короче так. Ваши рассуждения о взаимно простых циклах остроумны и красивы (и даже дают это чёртово n/e), но не имеют отношения к делу. Проще надо, гораздо проще. Наибольшая длина цикла, очевидно, равна n; но такой цикл получится всего один. А если попробовать два, три...

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

JMH в сообщении #342727 писал(а):

Стало быть, нужно найти такое разбиение множества n, что мощности элементов разбиения взаимно просты, т.к. в этом случае НОК равно произведению мощностей, след. максимально.

Это ещё почему?

Возьмём, например, $n=33$. Имеем $33 = 2 + 31$, $\text{НОК}(2,31) = 62$. С другой стороны, $33 = 9 + 24$ и $\text{НОК}(9,24) = 72 > 62$. Однако в первом случае берётся разложение $n$ на взаимно-простые слагаемые, а во втором --- нет.

[JMH]

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

Возьмём, например, $n=33$. Имеем $33 = 2 + 31$, $\text{НОК}(2,31) = 62$. С другой стороны, $33 = 9 + 24$ и $\text{НОК}(9,24) = 72 > 62$. Однако в первом случае берётся разложение $n$ на взаимно-простые слагаемые, а во втором --- нет.

Вы правы и это еще один гвоздь в крышку гроба моей попытки решения Я все пытаюсь сообразить в чем состоит суть подсказки ИСН: ясно что нужно искать максимальное НОК разбиения множества n, но в голову приходит только самая грубая оценка $n!\approx n*ln (n)$; как получить $e^{n/e}$ догадаться не получается

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

JMH в сообщении #342993 писал(а):

все пытаюсь сообразить в чем состоит суть подсказки ИСН...

Да он очень простую вещь предлагает:

$$ \begin{array}{c} \text{Максимальный порядок} = \\ \max\limits_{k \in \mathbb{N}} \max \{ \text{НОК}(x_1,\ldots, x_k) : x_1, \ldots, x_k \in \mathbb{N},\, x_1 + \ldots + x_k = n \} \leqslant \\ \max\limits_{k \in \mathbb{N}} \max \{ x_1 \cdot \ldots \cdot x_k : x_1, \ldots, x_k \in \mathbb{N},\, x_1 + \ldots + x_k = n \} \leqslant \\ \max\limits_{k \in \mathbb{N}} \max \{ x_1 \cdot \ldots \cdot x_k : x_1, \ldots, x_k \in \mathbb{R},\, x_1, \ldots, x_k > 0,\, x_1 + \ldots + x_k = n \} = \\ \max\limits_{k \in \mathbb{N}} \left( \frac{n}{k} \right)^k \leqslant \max\limits_{k \in \mathbb{R},\, k > 0} \left( \frac{n}{k} \right)^k = e^{\frac{n}{e}} \end{array} $$

Спрашивайте, если что-то вдруг непонятно

-- Сб авг 07, 2010 00:39:49 --

Кстати, понятно, что

$$ \lim\limits_{n \to \infty} \frac{\text{Максимальный порядок}}{e^{n/e}} = 1 $$

Так что оценка в пределе точна.

[mihailm]

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

Кстати, понятно, что

$$ \lim\limits_{n \to \infty} \frac{\text{Максимальный порядок}}{e^{n/e}} = 1 $$

Так что оценка в пределе точна.

А это почему можно спросить?

[JMH]

Будьте добры, вот этот момент поясните пожалуйста: $\max\limits_{k \in \mathbb{R},\, k > 0} \left( \frac{n}{k} \right)^k = e^{\frac{n}{e}$

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

JMH в сообщении #343013 писал(а):

Будьте добры, вот этот момент поясните пожалуйста

Дифференцируете по $k$, приравниваете производную к нулю, находите максимум...

mihailm в сообщении #343011 писал(а):

А это почему можно спросить?

Возможно, я поспешил с этим пределом

[JMH]

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

JMH в сообщении #343013 писал(а):

Будьте добры, вот этот момент поясните пожалуйста: $\max\limits_{k \in \mathbb{R},\, k > 0} \left( \frac{n}{k} \right)^k = e^{\frac{n}{e}$

Дифференцируете по $k$, приравниваете производную к нулю, находите максимум...

Не получается: $\left[\left(\frac{n}{x}\right)^x\right]'=-\frac{n}{x^2}\left(\frac{n}{x}\right)^x ln \frac{n}{x}$
Приравниваем к нулю и потенциируем: $x=ne^{-\frac{n}{x^2}\left(\frac{n}{x}\right)^x}$
и что дальше? $e^{\frac{n}{e}$ не видать, может вечер пятницы виноват?

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

JMH в сообщении #343058 писал(а):

Не получается: $\left[\left(\frac{n}{x}\right)^x\right]'=-\frac{n}{x^2}\left(\frac{n}{x}\right)^x ln \frac{n}{x}$
Приравниваем к нулю и потенциируем: $x=ne^{-\frac{n}{x^2}\left(\frac{n}{x}\right)^x}$
и что дальше? $e^{\frac{n}{e}$ не видать, может вечер пятницы виноват?

???

$$ \frac{d}{dx} \left( \frac{n}{x} \right)^x = \frac{d}{dx} e^{x \ln \frac{n}{x}} = e^{x \ln \frac{n}{x}} \left(\ln \frac{n}{x} + x \cdot \frac{x}{n} \cdot \frac{-n}{x^2} \right) $$

Приравниваем к нулю содержимое скобки, получаем $\ln (n/x) = 1$, $n/x = e$ и $x = n/e$.

А у Вас производная неправильно вычислена

[JMH]

М-да. Спасибо Вам большое! А у меня, видать, совсем мозги заржавели...