[juanma]

La estructura del diagrama (imagen) puede ser codificada por la siguiente definición:
\( D(n)=n-D(D(n-1)) \) (para n>0)
\( D(0)=0 \)


¿Alguien me explica cómo funciona?

[pierrot]

¿Y qué representa esa sucesión? Por favor, no dupliques hilos.

[juanma]

¿Y qué representa esa sucesión? Por favor, no dupliques hilos.

Cito el libro donde encontré el diagrama...

Para definir el Diagrama D (que es infinito) nos limitaremos a escribir en dos nódulos la letra "D" (la cual estará representando una reproducción completa del diagrama). En el diagrama superior [en la imagen] la estructura es representada implícitamente; si queremos observarlo mas explícitamente expandimos cada una de las "D", como se ve en el diagrama inferior.
Ahora bien, ¿cómo hace la función D(n) para codificar la estructura de árbol del Diagrama? Muy sencillamente: si uno construye un árbol, colocando D(n) debajo de n, para todos los valores de n, recreará el Diagrama D.

Espero que esto te ayude a entenderlo.

[pierrot]

Pero concretamente, ¿\( D(n) \) qué es? ¿Un grafo? Pero \( D(0)=0 \) es un número natural. También en la fórmula recursiva aparece un \( n-D(D(n-1)) \). ¿Cómo se define restarle un grafo a un número natural?

Lo que sea que haya querido transmitir el autor está terriblemente mal expresado.

[juanma]

Pero concretamente, ¿\( D(n) \) qué es? ¿Un grafo? Pero \( D(0)=0 \) es un número natural. También en la fórmula recursiva aparece un \( n-D(D(n-1)) \). ¿Cómo se define restarle un grafo a un número natural?

Lo que sea que haya querido transmitir el autor está terriblemente mal expresado.

No creo que el autor lo haya expresado mal [es un libro muy elogiado], creo que yo no se dar los recursos necesarios o el contexto adecuado para que entiendas el problema.
Si todavía te da curiosidad, podes afrontar el problema directamente. El libro se llama Gödel, Escher, Bach de Douglas R. Hofstadter.
Te dejo adjunto un pdf únicamente con las páginas en cuestión. Tambien adjunto imágenes de estas mismas páginas. Y dejo acá el link de un pdf del libro completo. http://avata.utadeo.edu.co/Lecturas/Hofstadter_Douglas_Un_Eterno_y_Gracil_Bucle.pdf . La página en la que se empieza a desarrollar el problema es la 159, aunque para mas contexto podrías leer desde párrafos anteriores.
Desde ya te agradezco el interés.

[pierrot]

Pero concretamente, ¿\( D(n) \) qué es? ¿Un grafo? Pero \( D(0)=0 \) es un número natural. También en la fórmula recursiva aparece un \( n-D(D(n-1)) \). ¿Cómo se define restarle un grafo a un número natural?

Lo que sea que haya querido transmitir el autor está terriblemente mal expresado.

No creo que el autor lo haya expresado mal [es un libro muy elogiado], creo que yo no se dar los recursos necesarios o el contexto adecuado para que entiendas el problema.

Si dispones los valores de \( n \) y \( D(n) \) en una tabla, obtienes lo siguiente:

\( \begin{array}{lllllllllll}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
D(n) & 1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 6 & 6
\end{array} \)

Para construir el grafo usando esta tabla, pones el nodo 1 en la raíz del árbol y luego cada nodo \( n \) lo colocas encima del nodo con etiqueta \( D(n) \). Por ejemplo, el nodo 2 va encima del 1, y el nodo 3 encima del 2. El nodo 4 y el nodo 5 van ambos encima del nodo 3, y así sucesivamente. Así te queda el grafo que está en las páginas que adjuntaste.


Sigo pensando que está muy mal explicado.