Делимость на факториал

[Sonic86]

Задача, возможно, подойдет для студентов.
Доказать, что:

$$n! | \sum\limits_{\pi \in S_n}2^{s(\pi)}$$

$\pi$ - перестановка из $S_n$, $s(\pi)$ - число циклов, в которые разлагается $\pi$.

[maxal]

Для решения достаточно вспомнить определение чисел Стирлинга 1-го рода и их производящую функцию.

[Sonic86]

maxal писал(а):

Для решения достаточно вспомнить определение чисел Стирлинга 1-го рода и их производящую функцию.

Ага ! А вот я совсем не так решал...

[Padawan]

у меня получилось, что эта сумма равна $(n+1)!$
Если её обозначить через $F_n$, то получается рекуррентное уравнение

$$F_n=2(F_{n-1}+(n-1)F_{n-2}+(n-1)(n-2)F_{n-3}+\ldots+(n-1)(n-2)\cdot\ldots \cdot 2\cdot F_1+(n-1)(n-2)\cdot\ldots \cdot2\cdot 1)$$

Откуда по индукции $F_n=(n+1)!$

[maxal]

Padawan в сообщении #373016 писал(а):

у меня получилось, что эта сумма равна $(n+1)!$

Так и есть:

$$\sum\limits_{\pi \in S_n}2^{s(\pi)} = \sum_{k=1}^n \left[n\atop k\right]\cdot 2^k = 2(2+1)(2+2)\cdots(2+n-1) = (n+1)!,$$

где $\left[n\atop k\right]$ - числа Стирлинга 1-го рода без знака.