Contar las permutaciones en $S_n$ con $k_i$ ciclos de longitud $i$ utilizando el teorema de Polya

Question

Tuve esta tarea de contar el número de permutaciones en $S_n$ con $k_i$ ciclos de longitud $i$ . Es bastante fácil encontrar que la respuesta es $\frac{n!}{1^{k_1}2^{k_2}\cdot\cdot\cdot k_1!k_2!\cdot\cdot\cdot k_n!}$ sólo por el hecho de contarlos.

También he intentado hacerlo con el teorema de Polya, pero hasta ahora sin éxito. La idea es reformular el problema como un problema de coloración (y luego utilizar el teorema de Polya con pesos) de la siguiente manera: Dado un conjunto $X=\{1,\dots,n\}$ de $n$ vértices (piense en ello como un collar) y $C$ un conjunto de $n$ colores con pesos asignados a cada color, es decir, w(c_i)=x_i. Contar el número de formas de hacer una n-coloración de X si dos coloraciones son indistinguibles si podemos obtener una simplemente intercambiando los colores en la otra. Como la acción del grupo actuará sobre el conjunto de colores (en lugar de $X$ ) No sé cómo seguir...

¡Cualquier ayuda será apreciada! Gracias de antemano.

Answer 1

No estoy seguro de por qué querrías usar especies no etiquetadas aquí. Parece que el procedimiento estándar es observar que el OGF del índice de ciclo del grupo simétrico es $$G(z) = \sum_{q\ge 0} Z(S_q) z^q = \exp\left(a_1 z + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} + \cdots\right).$$ Nos interesa el coeficiente $$n! [z^n a_1^{k_1} a_2^{k_2} a_3^{k_3}\cdots] G(z)$$ donde $$\sum_{q=1}^n k_q q = n.$$

En realidad al hacer la extracción utilizamos $$G(z) = \exp\left( \sum_{q\ge 1} a_q \frac{z^q}{q}\right) = \prod_{q\ge 1}\exp\left(a_q \frac{z^q}{q}\right)$$ para obtener $$n! [z^n] \prod_{q\ge 1} \frac{z^{q k_q}}{q^{k_q} k_q!} = n! \prod_{q\ge 1} \frac{1}{q^{k_q} k_q!}.$$