Производящие функиции

[Lapka]

$P_{(n,k)}=\frac{S_{(n,k)}}{n!}$ - вероятность наличия k циклов в подстановке степени n, S(n,k) - числа Стирлинга первого рода.
$\sum\limits_{n}P_{(n,k)}*z^n$ - помогите составить производящую функцию

[Sonic86]

Ну, во-первых, вот тут в Вики есть рекуррентная формула:

Вот вторых она Вам не поможет. Вам что надо найти? У Вас члены суммы зависят от $k,n$, а суммирование ведется только по $k$. Сформулируйте вопрос точнее.

[Vince Diesel]

Можно посчитать сначала для $k=1$. А затем, используя подходящую формулу, выражающую $S(n,k+1)$ через $S(n,k)$, показать, что для произвольного $k$ п.ф. равна $k$-й степени п.ф. для $k=1$ с некоторым множителем.

Другой способ - умножить формулу $x^{\bar n}=\sum_{k}S(n,k)x^k$ на $z^n/n!$, просуммироать по $n$ и получить п.ф. $f(x,z)=\sum_{k,n=0}^\infty \frac{S(n,k)x^kz^n}{n!}$ двух переменных. Тогда требуемая функция будет равна $\partial_x^kf(0,z)/k!$.

[--mS--]

Кстати, ответ есть у Грэхема, Кнута, Паташника в "Конкретной математике", таблица 386, формула (7.50):

$$\dfrac{1}{k!}\ln\left(\dfrac{1}{1-z}\right)^k.$$