Números de Narayana

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda

En combinatoria, los números de Narayana forman una vector triangular de números naturales, llamada triángulo de Narayana, que ocurren en varios problemas de conteo. Llevan el nombre del matemático canadiense T. V. Narayana (1930–1987).

Fórmula[editar]

Los números de Narayana se pueden expresar en términos de coeficiente binomial:

Valores numéricos[editar]

Las primeras ocho filas del triángulo de Narayana dicen:

k =       1   2   3   4   5   6   7   8
n = 1  |  1
    2  |  1   1
    3  |  1   3   1
    4  |  1   6   6   1
    5  |  1  10  20  10   1
    6  |  1  15  50  50  15   1
    7  |  1  21 105 175 105  21   1
    8  |  1  28 196 490 490 196  28   1

(sucesión A001263 en OEIS)

Interpretaciones combinatorias[editar]

Lenguaje de Dyck[editar]

Un ejemplo de un problema de conteo cuya solución se puede dar en términos de los números de Narayana. , es el número de palabras que contienen pares de paréntesis, que coinciden correctamente (conocido como Lenguaje de Dyck) y contiene distinto anidamientos. Por ejemplo, , ya que con cuatro pares de paréntesis, se pueden crear seis secuencias, cada una de las cuales contiene dos ocurrencias el subpatrón ():

(()(()))  ((()()))  ((())())
()((()))  (())(())  ((()))()

De este ejemplo debería ser obvio que ,ya que la única forma de obtener un solo subpatrón () es tener todos los paréntesis de apertura en la primera posición, seguido de todos los paréntesis de cierre. También , como los distintos anidamientos solo se pueden lograr mediante el patrón repetitivo. ()()()…().

De manera más general, se puede demostrar que el triángulo de Narayana es simétrico:

La suma de las filas de este triángulo es igual a los números de Catalan:

Caminos de celosía monótonos[editar]

Los números de Narayana también cuentan el número de [[Caminos de celosía|caminos de celosía] de to ,con escalones solo al noreste y sureste, sin desviarse por debajo del x-axis, con picos.

Las siguientes figuras representan los números de Narayana , ilustrando las simetrías mencionadas anteriormente.

Paths
N(4, 1) = 1 camino con 1 pico: Narayana N(4, 1).svg
N(4, 2) = 6 camino con 2 picos: Narayana N(4, 2).svg
N(4, 3) = 6 camino con 3 picos: Narayana N(4, 3).svg
N(4, 4) = 1 camino con 4 picos: Narayana N(4, 4).svg

Esta sume de es 1 + 6 + 6 + 1 = 14, que es el 4º número catalán, . Esta suma coincide con la interpretación de los números catalanes como el número de trayectos monótonos a lo largo de los bordes de un cuadrícula que no pasa por encima de la diagonal.

Árbol enraizado[editar]

Los 6 árboles enraizados ordenados de 4 aristas y 2 hojas, correspondientes al número de Narayana N (4, 2)

El número de árboles enraizados ordenados con lados y hojas es igual a .

Ello es análogo a los ejemplos previos:

  • Cada palabra Dyck se puede representar como un árbol enraizado. Comenzamos con un solo nodo: el nodo raíz. Este es inicialmente el "nodo activo". Al leer la palabra de izquierda a derecha, cuando el símbolo es un paréntesis de apertura, agregue un hijo al nodo activo a y establezca este hijo como nodo activo. Cuando el símbolo es un paréntesis de cierre, establezca el padre del nodo activo como nodo activo. De esta forma obtenemos un árbol, en el que cada nodo no raíz corresponde a un par de paréntesis coincidente, y sus hijos son los nodos correspondientes a las sucesivas palabras de Dyck dentro de estos paréntesis. Los nodos hoja corresponden a paréntesis vacíos: (). De manera análoga, podemos construir una palabra Dyck a partir de un árbol enraizado mediante una búsqueda en profundidad. Por tanto, existe un isomorfismo entre las palabras de Dyck y los árboles enraizados.

Función generadora[editar]

La función generadora de los números de Narayana es [1]

Véase también[editar]

Referencias[editar]

  1. Petersen, 2015, p. 25.

Bibliografía[editar]