Circulares permutaciones con objetos indistinguibles

Question

Dados n objetos distintos, hay $n!$ permutaciones de los objetos y $n!/n$ «permutaciones circulares"de los objetos (materias de la orientación del círculo, pero hay no hay punto de partida, así $1234$ $2341$ son los mismos, y $4321$ es diferente).

Dado objetos de $n$ $k$ tipos (donde los objetos dentro de cada tipo son indistinguibles), $r_i$ del tipo $i^{th}$, hay

\begin{equation*} \frac{n!}{r_1!r_2!\cdots r_k!} \end{ecuación *}

permutaciones. ¿Cuántas permutaciones circulares existen de tal sistema?

Answer 1

Escribí una serie de entradas en el blog que explica como resolver preguntas como esta; es relevante aquí. La función generadora que usted desea es

$$\frac{1}{n} \sum_{d | n} (x_1^{n/d} + ... + x_k^{n/d})^d \varphi \left( \frac{n}{d} \right)$$

donde el coeficiente de $x_1^{r_1} ... x_k^{r_k}$ es el número que desee.

Answer 2

Este problema se resuelve mejor con Teorema de enumeración de Pólya, que sigue del lema de Burnside. Consulte la sección primera de este artículo de Wikipedia.