En matemáticas , el gráfico de Young-Fibonacci y celosía Young-Fibonacci , el nombre de Alfred joven y Leonardo Fibonacci , son dos estructuras estrechamente relacionadas que implican secuencias de los dígitos 1 y 2. Cualquier secuencia de dígitos de este tipo se 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 India antigua, el número de secuencias con un rango dado es un número de Fibonacci . La celosía de Young-Fibonacci es una celosía modular infinitateniendo estas secuencias de dígitos como sus elementos, compatibles con esta estructura de rango. La gráfica de Young-Fibonacci es la gráfica de esta red y tiene un vértice para cada secuencia de dígitos. Como gráfico de una celosía modular, es un gráfico modular .
El gráfico de Young-Fibonacci y el enrejado de Young-Fibonacci fueron inicialmente estudiados en dos artículos por Fomin (1988) y Stanley (1988) . Reciben el nombre de la celosía de Young estrechamente relacionada y del número de Fibonacci de sus elementos en cualquier rango dado.
Secuencias de dígitos con un rango determinado
Una secuencia de dígitos con rango r puede formarse sumando el dígito 2 a una secuencia con rango r - 2 , o agregando el dígito 1 a una secuencia con rango r - 1 . Si f ( r ) es la función que asigna r al número de secuencias de dígitos diferentes de ese rango, por lo tanto, f satisface la relación de recurrencia f ( r ) = f ( r - 2) + f ( r - 1) que define el Fibonacci números, 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 consta de un solo dígito 1). Estas condiciones iniciales hacen que la secuencia de valores de f se desplace una posición de los números de Fibonacci: f ( r ) = F r + 1 donde F i denota el i- ésimo número de Fibonacci.
En el antiguo estudio indio de la prosodia , los números de Fibonacci se utilizaron para contar el número 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 el número de Fibonacci para obtener más detalles.
Gráficos de secuencias de dígitos
El gráfico de Young-Fibonacci es un gráfico 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:
- Inserte un "1" en s , antes del "1" situado más a la izquierda (o en cualquier lugar de s si aún no contiene un "1").
- Cambie el "1" de s más a la izquierda en un "2".
- Quite el "1" más a la izquierda de la s .
- Cambie un "2" que no tenga un "1" a la izquierda por un "1".
Es sencillo verificar que cada operación se puede invertir: las operaciones 1 y 3 son inversas entre sí, al igual que las operaciones 2 y 4. Por lo tanto, el gráfico resultante puede considerarse no dirigido . Sin embargo, generalmente se considera que es un gráfico acíclico dirigido en el que cada borde se conecta desde un vértice de rango inferior a un vértice de rango superior.
Como observan tanto Fomin (1988) como Stanley (1988) , este gráfico tiene las siguientes propiedades:
- Está conectado: cualquier cadena no vacía puede tener su rango reducido por alguna operación, por lo que hay una secuencia de operaciones que van de ella a la cadena vacía, lo que da una dirección inversa en el gráfico desde la cadena vacía a cada otro vértice.
- Es compatible con la estructura de rango: cada ruta dirigida tiene una longitud igual a la diferencia en los rangos de sus puntos finales.
- Para cada dos nodos distintos u y v , el número de predecesores inmediatos comunes de u y v es igual al número de sucesores inmediatos comunes de u y v ; este número es cero o uno.
- El grado de salida de cada vértice es igual a uno más su grado de entrada.
Fomin (1988) llama a un gráfico con estas propiedades un gráfico en Y ; Stanley (1988) llama a un gráfico con una versión más débil de estas propiedades (en el que el número de predecesores comunes y sucesores comunes de cualquier par de nodos debe ser igual pero puede ser mayor que uno) el gráfico de un poset diferencial .
Orden parcial y estructura de celosía
El cierre transitivo del gráfico de Young-Fibonacci es un orden parcial . Como Stanley (1988) muestra, dos vértices x y y tener un único predecesor común mayor en este orden (su meet ) y un sucesor menos común único (su unirse a ); por lo tanto, este orden es una celosía , llamada celosía de Young-Fibonacci.
Para encontrar la reunión de X e Y , se puede en primer lugar si uno de X e Y es un precursor de la otra. Una cadena x es un precursor de otra cadena y en este orden exactamente cuando el número de dígitos "2" que quedan en y , después de retirar el sufijo común más larga de x e y , es por lo 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 un predecesor de y de acuerdo con esta prueba, entonces su encuentro es x , y de manera similar, si y es un predecesor de x, entonces su 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 encuentro no cambia si se eliminan estos dígitos iniciales. Y finalmente, si tanto x e y comienzan con el dígito “2”, el encuentro de x e y se pueden encontrar mediante la eliminación de este dígito de ambos, la búsqueda de la reunión de los sufijos resultantes, y añadiendo el “2” de nuevo a el comienzo.
Un sucesor común de x y y (aunque no necesariamente el sucesor menos común) se puede encontrar mediante la adopción de una serie de “2” dígitos con longitud igual a la más larga de x y y . El sucesor menos común es la continuación del encuentro de las finito de cadenas que son sucesores comunes de X y Y y predecesores de esta cadena de “2” s.
Como observa además Stanley (1988) , la red de Young-Fibonacci es modular . Fomin (1988) afirma incorrectamente que es distributivo ; sin embargo, la subred formada por las cadenas {21,22,121,211,221} forma una subred de diamante, prohibida en las redes distributivas.
Referencias
- Fomin, SV (1988), "Correspondencia generalizada de Robinson-Schensted-Knuth", Journal of Mathematical Sciences , 41 (2): 979-991, doi : 10.1007 / BF01247093. Traducido de Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. VA Steklova AN SSSR 155 : 156-175, 1986.
- Stanley, Richard P. (1988), "Posets diferenciales", Journal of the American Mathematical Society , 1 (4): 919–961, doi : 10.2307 / 1990995 , JSTOR 1990995.