Цикловой индекс симметрической группы

[cyb12]

Пусть $S_n$ -- симметрическая группа перестановок над $\{1,2,\ldots,n\}$. Для её циклического индекса $Z(S_n;s_1,\ldots,s_n)$ справедливо рекуррентное соотношение (если считать, что $Z(S_0)=1$:

$$Z(S_n;s_1,\ldots,s_n)=\dfrac1n\sum_{k=1}^ns_kZ(S_{n-k};s_1,\ldots,s_{n-k}).$$

Утверждается, что это следует из следующего соотношения:

$$n!Z(S_n;s_1,\ldots,s_n)=\sum_{k=1}^n(n-1)(n-2)\cdots(n-k+1)(n-k)!s_kZ(S_{n-k};s_1,\ldots,s_{n-k}).$$

Помогите понять, почему оно верно?
Вроде бы это делается по определению. Элемент $n$ может входить в цикл длины $k$ в произведении циклов подстановки, и, видимо, по этому $k$ и ведётся суммирование.