Números de Narayana

Un ejemplo de un problema de conteo cuya solución se puede dar en términos de los números de Narayana. ${\displaystyle \operatorname {N} (n,k)}$, 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, ${\displaystyle \operatorname {N} (4,2)=6}$, 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 ${\displaystyle \operatorname {N} (n,1)=1}$,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 ${\displaystyle \operatorname {N} (n,n)=1}$, 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:

${\displaystyle \operatorname {N} (n,k)=\operatorname {N} (n,n-k+1)}$

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

${\displaystyle \operatorname {N} (n,1)+\operatorname {N} (n,2)+\operatorname {N} (n,3)+\cdots +\operatorname {N} (n,n)=C_{n}}$

Los números de Narayana también cuentan el número de caminos de celosía de ${\displaystyle (0,0)}$ to ${\displaystyle (2n,0)}$,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 ${\displaystyle \operatorname {N} (4,k)}$, ilustrando las simetrías mencionadas anteriormente.

${\displaystyle \operatorname {N} (4,k)}$	Caminos
N(4, 1) = 1 camino con 1 pico:
N(4, 2) = 6 caminos con 2 picos:
N(4, 3) = 6 caminos con 3 picos:
N(4, 4) = 1 camino con 4 picos:

Esta suma de ${\displaystyle \operatorname {N} (4,k)}$ es 1 + 6 + 6 + 1 = 14 (que es el 4º número de Catalan ${\displaystyle C_{4}}$), y coincide con la interpretación de los números de Catalan como el número de trayectos monótonos a lo largo de los bordes de una cuadrícula de ${\displaystyle n\times n}$ que no pasan por encima de la diagonal.

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 ${\displaystyle n}$ lados y ${\displaystyle k}$ hojas es igual a ${\displaystyle \operatorname {N} (n,k)}$.

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.