Podemos resolver esto, mientras que la de establecer la maquinaria para considerar otras funcional sub-repite. Podemos considerar que una función se describe por su funcional gráfico , es decir, un grafo dirigido, donde cada vértice $v$ tiene un borde que va a $f(v)$. Por ejemplo, podríamos dibujar $f(x)=x+1$
$$0\longrightarrow 1\longrightarrow 2\longrightarrow 3\longrightarrow 4\longrightarrow \cdots. $$
Más generalmente, $f(x)=x+b$ tiene este aspecto:
$$0\longrightarrow b+0\longrightarrow 2b+0\longrightarrow 3b+0\longrightarrow \cdots$$
$$1\longrightarrow b+1\longrightarrow 2b+1\longrightarrow 3b+1\longrightarrow \cdots$$
$$\vdots$$
$$b-1\longrightarrow 2b-1\longrightarrow 3b-1\longrightarrow 4b-1\longrightarrow \cdots$$
Es decir, si se describe la gráfica de $x\mapsto x+1$ como una cadena, entonces la gráfica de $x\mapsto x+b$ $b$ discontinuo cadenas. Si queremos ser muy formal, podemos definir una cadena de $C$ a un conjunto tal que la imagen de $f(C)$ y preimagen $f^{-1}(C)$ igualdad $C$.
A partir de aquí, vamos a $f(x)=x+b$. Ahora, supongamos que una función $g$ que $g^a=f$. Varias cosas deben ser claras: en primer lugar, $f$ $g$ conmutar en virtud de la composición:
$$g\circ f = g\circ g^{a}=g^{a+1}=g^{a}\circ g = f\circ g.$$
Una consecuencia importante de esto es que si sabemos, por ejemplo, $g(k)$, entonces sabemos que $g(f(k))=f(g(k))$ significado $g(x+b)=g(x)+b$. En la funcional gráfico da el siguiente sencillo corolario:
Si $C$ está conectado a la parte funcional de la gráfica (es decir, una cadena), entonces la imagen de a $g(C)$ es un subconjunto de un conectada parte de la cadena. Así pues, hay algunos bien definido mapa de $G$ mapeo de cadenas a otras cadenas que si $x\in C$$g(x)\in G(C)$.
Un ejemplo de lo anterior sería que si $b=2$$g(x)=x+1$, $G$ mapa del conjunto de los números pares para el conjunto de los números impares y viceversa -, puede ser interpretado como un mapa de clases de equivalencia de mod $b$, pero sólo necesitamos el hecho de que actúa sobre cadenas. Es notable el hecho de que claramente $G^a$ es la función identidad, porque si $x\in C$ $f(x)\in C$ significado $g^a(x)\in C$. Una rama de este es que $G$ es un bijection, ya que si una iteración de que es un bijection (es decir, la identidad aquí), debe ser un bijection demasiado. Con más fuerza, tenemos el siguiente lema:
No puede ser de $0<a'<a$ $C$ tal que $G^{a'}(C)=C$. Es decir, $G^a$ es el menos iterar con puntos fijos.
Para demostrarlo, supongamos $a'$ es el menos $a'$. Si $a'$ no divide $a$,$a=k+na'$$0<k<a'$,$G^{a}(C)=G^{k+na'}(C)=G^{k}(C)$. Esto no puede ser, ya que $G^k$ no tiene puntos fijos, sino $G^{a}$ debe ser la identidad. Si $a'$ sí divide $a$$a=na'$$n>1$. Sin embargo, en este caso, la restricción de $g^{a'}$ $C$es un mapa de $C\rightarrow C$. Sin embargo, esto significaría que el $n^{th}$ itera $g^{a'}$ $f$ - pero $f$ restringido a $C$ es isomorfo a $x\mapsto x+1$ (debido a $C$ es una cadena) que no tiene sub-itera (como se ha demostrado). Por lo tanto $g^{a'}$ no puede tener su $n^{th}$ iterar igual a$f$$C$, la creación de una contradicción.
Esto significa que $G$ es una permutación en el $b$ cadenas, donde cada ciclo tiene una longitud de $a$. De inmediato, esto da que no existen funciones si $a$ no divide $b$. Para concluir, consideramos que el mapa de $g$ restringido a una sola cadena $C_1$ la asignación a $C_2=G(C_1)$. Desde $f$ viajes con $g$, es fácil ver que esto es determinado. Por otra parte, desde la $C_1$ es la única cadena con $G(C_1)=C_2$, debido a $G$ ser un bijection, se deduce que la imagen de $g(\mathbb N)\cap C_2=g(C_1)$. Ya que la imagen de $g$ debe contener la imagen de $f$, la siguiente de la siguiente manera:
Si $C_1$ es la naturals igual a $k_1$ mod $b$ $C_2$ es de esas igual a $k_2$ mod $b$ donde $0\leq k_1,k_2 < b$, uno de los siguientes para todos $x\in C_1$: $$g(x)=x-k_1+k_2$$ $$g(x)=x-k_1+k_2+b$$
Esto es debido a que $g$ está determinado por $g(k_1)$, el cual puede ser $k_2$ o $k_2+b$, ya que el $k_2+b$ es en la imagen de $f$ y no sería incluido en la imagen de $g$ si establecemos $g(k_1)=k_2+2b$, por ejemplo.
Vamos a llamar a una cadena de $C_1$ donde $g$ satisface la identidad anterior a ser "estática" y en el que la $g$ satisface el último a ser "avanzar".
Debe quedar claro a partir de computación que si una órbita $C,G(C),G^{2}(C),\ldots,G^{a-1}(C)$ contiene $\ell$ avance de ciclos, entonces para $x\in C$ tenemos $g^{a}(C) = a + \ell b$, con lo que todas esas órbitas tienen exactamente un avance de ciclo. Esto es intuitivamente darse cuenta de que una "estática" de la cadena de mapas de elementos correspondientes a los elementos correspondientes, es decir, se asigna el primer elemento de una cadena a un el primer elemento de otro y así sucesivamente. El avance de un mapa es $f$ compuesto con un mapa estático. Los mapas de $g$ todos conmuta con $f$ y la composición de un ciclo de mapas estáticos debe ser la identidad (ya que se asigna el primer elemento de $C$ para el primer elemento de $C$, por ejemplo), por lo que claramente tenemos el correcto igualdad si y sólo si exactamente uno está avanzando - y, para las definiciones adecuadas de "estático" y "avanzar" sobre arbitraria funcional gráficos, esto es en general.
Sin embargo, esto hace que la combinatoria fácil. En particular, todos los $g$ está determinada únicamente por $G$, una permutación que es el producto de $(b/a)$ ciclos disjuntos de longitud $a$, y una selección de $1$ avance de la cadena en cada ciclo. Esto funciona como:
Hay $\frac{b!}{(a!)^{b/a} (b/a)!}$ formas para dividir los elementos en conjuntos disjuntos de tamaño $a$. Si, en cada conjunto, se escribe el avance de ciclo $C$, seguido por $G(C), G^{2}(C),\ldots G^{a-1}(C)$, podemos crear un bijection entre las funciones potenciales $G$ e identificaciones de un avance de la cadena con el conjunto de las permutaciones de $a$ elementos. Hay, pues, $a!$ fue para elegir a $g$ en cada uno de los conjuntos de $a$ cadenas. Hay $b/a$ estos conjuntos, por lo tanto la respuesta es
$$\frac{b!}{(a!)^{b/a}(b/a)!}\cdot (a!)^{b/a}=\frac{b!}{(b/a)!}.$$
Podemos mostrar que $x\mapsto x+b$ adueñado de todos los números enteros tiene una infinidad de sub-cuando se itera $a$ divide $b$, ya que cada mapa correspondiente $x+k$ a partir de una cadena a otra, puede ser considerado para ser estática o avanzar, ya que no hay "punto de partida" en los enteros, a contar desde - por lo que en la elección de los "mapas de transición", se obtiene infinitamente mucho la elección. Curiosamente, se puede utilizar el mismo método para mostrar que, por ejemplo, $x\mapsto 2x$ sobre los enteros positivos es infinitamente muchas cadenas, así que podemos hacer una infinidad de sub-repite de la misma por cualquier $a$ (y la de la obra anterior es suficiente para caracterizar a todos ellos). Si tenemos en cuenta $x\mapsto 2x$ $0$ en el dominio, podemos demostrar que, desde que terminamos con un componente conectado funcional de la gráfica que es simplemente un ciclo de$0$$0$, y puesto que no se puede asignar este componente a cualquier otro (ya que mucho no se ve como una cadena), que consiste en un sub-iterar de $x\mapsto 2x$ sobre los enteros positivos junto con la definición que el %de$0\mapsto 0$. También podemos probar que el mapa de $x\mapsto |x+b|$ tomadas a través de los números enteros no divisible por $b$ tiene sub-repite siempre $a$ divide $b$, ya que su gráfica es como una cadena, donde cada elemento se le da un extra de borde entrante desde un vértice sin bordes que van a él (existen infinidad de sub-recorre de este, cuando existen, a pesar de que, como los nuevos nodos sin preimages agregar algún grado de libertad). Los casos más complicados de hacer de esta una buena manera de visualizar el problema, pero las cosas pueden ponerse bastante peludo cuando se mira en el caso general.
