Coloreando$n$ cadena con$k$ colores

Question

Las cadenas están hechas de perlas, en cada uno de $k$ colores. En cada cadena hay $n$ perlas. Pretendemos que las dos cadenas son iguales si uno se puede hacer a partir de la segunda por la rotación cíclica (espejo de la reflexión no está permitido). Cuántas cadenas diferentes podemos obtener?

Quiero usar Polyi teorema. Así que vamos a deifine $$G = \left\{0,1,2,...,n-1 \right\} = \mathbb Z_n $$ where element $e \in G$ is treated as cyclic rotation with $e$ puestos. Ahora debo escribir los elementos y ciclos que se produce por ellos cíclico índice. \begin{array}{|c|c|c|c|} \hline elements& cycles\\ \hline 0 & x_1^n \\ \hline 1 & x_n^1 \\ \hline 2 & ? \\ \hline 3 & ? \\ \hline ... & ... \\ \hline n-3 & ? \\ \hline n-2 & ? \\ \hline n-1 & x_n^1 \\ \hline \end{array} Sé lo que pasó por elementos de la $0,1,n-1$ pero me completety no saben cómo tratar a los demás elementos debido al hecho de que hay enfoque diferente en diferentes combinaciones de $k$, $n$...

Answer 1

Sé Polyi Teorema en una forma ligeramente diferente, así que mis disculpas por el poco notación diferente.

Deje $G=\{0,1,2,...,n-1\}$ cíclica de grupo y deje $X$ ser el conjunto de todos los colores arreglos de $n$ cuentas $k$ colores. Nota $\# X=k^{n}$. Ahora tenemos que calcular la cardinalidad de los puntos fijos de los elementos de $G$: $\chi(g)=\#\{x\in X:gx=x\}$.

Deje $d$ ser un divisor de $n$, recordemos que el número de elemento de orden $d$ en $G$ es $\varphi(d)$ donde $\varphi$ es el de Euler-$\varphi$ fórmula. Tenga en cuenta que si $g$ es un elemento de orden $d$ entonces $\chi(g)=k^{n/d}$.

El uso de Polyi del teorema nos encontramos con que el número de colores diferentes cadenas de seguridad de rotación cíclica está dada por: $$\#(G\verb?\?X)=\sum_{d,d|n}\varphi(d)k^{n/d}.$$