Números de Narayana

Números de Narayana
Nombrado por	Tadepalli Venkata Narayana
No. de términos conocidos	infinito
Fórmula	$\operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}$
índice OEIS	A001263 Triángulo de Narayana

En combinatoria, los números de Narayana $\operatorname {N} (n,k),n\in \mathbb {N} ^{+},1\leq k\leq n$ forman un vector triangular de números naturales, llamado triángulo de Narayana, que se presenta en varios problemas de conteo. Llevan el nombre del matemático canadiense T. V. Narayana (1930–1987).

Fórmula

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

$\operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}$

Valores numéricos

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

Lenguaje de Dyck

Un ejemplo de un problema de conteo cuya solución se puede dar en términos de los números de Narayana. $\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, $\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 $\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 $\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:

$\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:

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

Caminos de celosía monótonos

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

$\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 $\operatorname {N} (4,k)$ es 1 + 6 + 6 + 1 = 14 (que es el 4º número de Catalan $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 $n\times n$ que no pasan por encima de la diagonal.

Árbol enraizado

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 $n$ lados y $k$ hojas es igual a $\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.

Función generadora

La función generadora de los números de Narayana es​

$\sum _{n=1}^{\infty }\sum _{k=1}^{n}\operatorname {N} (n,k)z^{n}t^{k-1}={\frac {1-z(t+1)-{\sqrt {1-2z(t+1)+z^{2}(t-1)^{2}}}}{2tz}}\;.$

Véase también

• Números de Catalan
• Números de Delannoy
• Número de Motzkin
• Número de Schröder
• Triángulo de Pascal

Bibliografía

• P. A. MacMahon (1915–1916). Combinatorial Analysis. Cambridge University Press. 
• Petersen, T. Kyle (2015). «Narayana numbers». Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher. Basel: Birkhäuser. ISBN 978-1-4939-3090-6. doi:10.1007/978-1-4939-3091-3. 

• Datos: Q6965520
• Multimedia: Narayana numbers / Q6965520