перестановки с чётными и нечётными циклами

[maxal]

1) Докажите, что количество перестановок порядка $2n$ ($n$ - натуральное число), в которых все циклы имеют чётную длину, равно количеству перестановок того же порядка, в которых все циклы имеют нечётную длину.

2) Постройте в явном виде биекцию между множествами всех таких перестановок фиксированного порядка $2n$.

[RIP]

1) Обозначим через $e_n$ количество перестановок длины $2n$, в которых все циклы имеют чётную длину. Тогда

$$e_n=\sum_{k=1}^n\frac{(2n-1)!}{(2n-2k)!}e_{n-k},\quad e_0=1$$

($\frac{(2n-1)!}{(2n-2k)!}$ --- количество способов выбрать цикл длины $2k$, содержащий $1$). Поэтому, если обозначить $f(z)=\sum_{n=0}^\infty e_n\frac{z^n}{(2n)!}$, то

$$zf'(z)=\frac{zf(z)}{2(1-z)},\quad f(0)=1,$$

т.е. $f(z)=(1-z)^{-1/2}$.

Аналогично, если обозначить через $o_n$ количество перестановок длины $n$, в которых все циклы имеют нечётную длину, то

$$o_n=\sum_{k=0}^{\lfloor\frac{n-1}2\rfloor}\frac{(n-1)!}{(n-2k-1)!}o_{n-2k-1},\quad o_0=1,$$

т.е. $g(z)=\sum_{n=0}^\infty o_n\frac{z^n}{n!}$ удовлетворяет

$$zg'(z)=\frac{zg(z)}{1-z^2},\quad g(0)=1,$$

т.е. $g(z)=\sqrt{\frac{1+z}{1-z}}$, поэтому

$$\frac{g(z)+g(-z)}2=f(z^2).\qed$$

По пути сосчитали искомое количество перестановок .

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

RIP писал(а):

По пути сосчитали искомое количество перестановок .

\[ e_n = o_{2n} = \prod_{i=1}^n (2i-1)^2 \text{ и } o_{2n+1} = (2n+1) \cdot \prod_{i=1}^n (2i-1)^2 \]

Через степенные ряды, конечно, красиво, но можно и просто по индукции. Действительно, из формул, предложенных RIP,
легко получаем

\[ e_{n+1} = \sum_{k=0}^n \frac{(2n+1)!}{(2n-2k)!} \cdot e_{n-k} = (2n+1) e_n + (2n)(2n+1) \sum_{k=1}^n \frac{(2n-1)!}{(2n-2k)!} \cdot e_{n-k} = (2n+1)^2 e_n, \]

\[ o_{2n+1} = \sum_{k=0}^n \frac{(2n)!}{(2n-2k)!} o_{2n-2k} = \frac{1}{2n+1} \cdot \sum_{k=0}^n \frac{(2n+1)!}{(2n-2k)!} \cdot e_{n-k} = \frac{e_{n+1}}{2n+1} = (2n+1) e_{n} \text{ и} \]

\[ o_{2n+2} = \sum_{k=0}^n \frac{(2n+1)!}{(2n-2k+1)!} \cdot o_{2n-2k+1} = \sum_{k=0}^n \frac{(2n+1)!}{(2n-2k+1)!} \cdot (2n-2k+1)e_{n-k} = e_{n+1}. \]

Как строить биекцию в явном виде --- непонятно. Пытался экспериментировать с домножениями перестановок на
различные транспозиции, но вроде пока безрезультатно.

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

A000246

[Хорхе]

Еще одно доказательство для поклонников символьной комбинаторики:
класс перестановок с четными циклами (как класс с метками) - это

$$ \mathcal{E} = \rm{Set}(\rm{Cyc_{\text{чет}}(\mathcal{Z})), $$

что переводится на язык экспоненциальных генератрис как

$$ E(z) = \exp\{-(\ln(1-z)-\ln(1+z))/2\} = \frac{1}{\sqrt{1-z^2}}. $$

С другой стороны, класс перестановок, состоящих из четного количества нечетных циклов - это

$$ \mathcal{O} = \rm{Set}_{\text{чет}}(\rm{Cyc_{\text{нечет}}(\mathcal{Z})), $$

что переводится на язык экспоненциальных генератрис как

$$ O(z) = \ch\{(\ln(1+z)-\ln(1-z))/2\} = \dots = \frac{1}{\sqrt{1-z^2}}. $$