En matemáticas , el grafo de Young-Fibonacci y la red de Young-Fibonacci , llamada así por Alfred Young y Leonardo Fibonacci , son dos estructuras estrechamente relacionadas que involucran secuencias de los dígitos 1 y 2. A cualquier secuencia de dígitos de este tipo se le puede asignar un rango , la suma de sus dígitos: por ejemplo, el rango de 11212 es 1 + 1 + 2 + 1 + 2 = 7. Como ya se sabía en la antigua India, el número de secuencias con un rango dado es un número de Fibonacci . La red de Young-Fibonacci es una red modular infinita que tiene estas secuencias de dígitos como sus elementos, compatible con esta estructura de rango. El grafo de Young-Fibonacci es el grafo de esta red, y tiene un vértice para cada secuencia de dígitos. Como grafo de una red modular, es un grafo modular .
Tanto el gráfico de Young-Fibonacci como la red de Young-Fibonacci fueron estudiados inicialmente en dos artículos de Fomin (1988) y Stanley (1988). Reciben su nombre de la red de Young, estrechamente relacionada con ella , y del número de Fibonacci de sus elementos en cualquier rango dado.
Una secuencia de dígitos con rango r puede formarse ya sea añadiendo el dígito 2 a una secuencia con rango r − 2 , o añadiendo el dígito 1 a una secuencia con rango r − 1 . Si f es la función que asigna r al número de secuencias de dígitos diferentes de ese rango, entonces f satisface la relación de recurrencia f ( r ) = f ( r − 2) + f ( r − 1) que define los números de Fibonacci, pero con condiciones iniciales ligeramente diferentes: f (0) = f (1) = 1 (hay una cadena de rango 0, la cadena vacía , y una cadena de rango 1, que consiste en el único dígito 1). Estas condiciones iniciales hacen que la secuencia de valores de f se desplace una posición con respecto a los números de Fibonacci : f ( r ) = F r +1 .
En el antiguo estudio indio de la prosodia , los números de Fibonacci se utilizaban para contar la cantidad de secuencias diferentes de sílabas cortas y largas con una longitud total determinada; si el dígito 1 corresponde a una sílaba corta y el dígito 2 corresponde a una sílaba larga, el rango de una secuencia de dígitos mide la longitud total de la secuencia de sílabas correspondiente. Consulte el artículo sobre los números de Fibonacci para obtener más información.
El grafo de Young-Fibonacci es un grafo infinito , con un vértice para cada cadena de dígitos "1" y "2" (incluida la cadena vacía ). Los vecinos de una cadena s son las cadenas formadas a partir de s mediante una de las siguientes operaciones:
Es fácil comprobar que cada operación puede invertirse: las operaciones 1 y 3 son inversas entre sí, al igual que las operaciones 2 y 4. Por lo tanto, el grafo resultante puede considerarse no dirigido . Sin embargo, normalmente se considera que es un grafo acíclico dirigido en el que cada arista conecta desde un vértice de rango inferior a un vértice de rango superior.
Como observan Fomin (1988) y Stanley (1988), este gráfico tiene las siguientes propiedades:
Fomin (1988) llama a un gráfico con estas propiedades un Y -grafo; Stanley (1988) llama a un gráfico con una versión más débil de estas propiedades (en el que los números de predecesores comunes y sucesores comunes de cualquier par de nodos deben ser iguales pero pueden ser mayores que uno) el gráfico de un poset diferencial .
El cierre transitivo del grafo de Young-Fibonacci es un orden parcial . Como muestra Stanley (1988), dos vértices cualesquiera x e y tienen un único máximo común predecesor en este orden (su encuentro ) y un único mínimo común sucesor (su unión ); por lo tanto, este orden es un retículo , llamado retículo de Young-Fibonacci.
Para hallar el punto de encuentro de x e y , primero se puede comprobar si uno de x e y es predecesor del otro. Una cadena x es predecesora de otra cadena y en este orden exactamente cuando el número de dígitos "2" restantes en y , después de eliminar el sufijo común más largo de x e y , es al menos tan grande como el número de todos los dígitos restantes en x después de eliminar el sufijo común. Si x es predecesor de y según esta prueba, entonces su punto de encuentro es x , y de manera similar, si y es predecesor de x , entonces su punto de encuentro es y . En un segundo caso, si ni x ni y son predecesores del otro, pero uno o ambos comienzan con un dígito "1", el punto de encuentro no cambia si se eliminan estos dígitos iniciales. Y finalmente, si tanto x como y comienzan con el dígito "2", el punto de encuentro de x e y se puede encontrar eliminando este dígito de ambos, encontrando el punto de encuentro de los sufijos resultantes y agregando el "2" nuevamente al inicio.
Se puede encontrar un sucesor común de x e y (aunque no necesariamente el sucesor menos común) tomando una cadena de "2" dígitos con una longitud igual al mayor de x e y . El sucesor menos común es entonces el resultado de la suma de las cadenas finitas que son sucesoras comunes de x e y y predecesoras de esta cadena de "2".
Como observa además Stanley (1988), la red de Young-Fibonacci es modular . Fomin (1988) afirma incorrectamente que es distributiva ; sin embargo, la subred formada por las cuerdas {21, 22, 121, 211, 221} forma una subred de diamante, prohibida en las redes distributivas.