Número de Narayana

Matriz triangular de números naturales

En combinatoria , los números de Narayana forman una matriz triangular de números naturales , llamada triángulo de Narayana, que aparecen en varios problemas de conteo . Su nombre se debe al matemático canadiense TV Narayana (1930–1987) . ${\displaystyle \operatorname {N} (n,k),n\in \mathbb {N} ^{+},1\leq k\leq n}$

Fórmula

Los números de Narayana se pueden expresar en términos de coeficientes binomiales :

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

(secuencia A001263 en la OEIS )

Interpretaciones combinatorias

Palabras de Dyck

Un ejemplo de un problema de conteo cuya solución puede darse en términos de los números de Narayana es el número de palabras que contienen pares de paréntesis que coinciden correctamente (conocidas como palabras de Dyck ) y que contienen anidaciones distintas . Por ejemplo, , ya que con cuatro pares de paréntesis, se pueden crear seis secuencias que contienen cada una dos ocurrencias del subpatrón : ${\displaystyle \operatorname {N} (n,k)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \operatorname {N} (4,2)=6}$()

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

A partir de este ejemplo debería ser obvio que , dado que la única forma de obtener un único subpatrón es tener todos los paréntesis de apertura en las primeras posiciones , seguidos de todos los paréntesis de cierre. Además , como solo se pueden lograr anidaciones distintas mediante el patrón repetitivo . ${\displaystyle \operatorname {N} (n,1)=1}$() ${\displaystyle n}$ ${\displaystyle \operatorname {N} (n,n)=1}$ ${\displaystyle n}$()()()…()

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 catalanes :

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

Caminos reticulares monótonos

Los números de Narayana también cuentan el número de caminos reticulares desde hasta , con pasos solo al noreste y sureste, sin desviarse por debajo del eje x , con picos . ${\displaystyle (0,0)}$ ${\displaystyle (2n,0)}$ ${\displaystyle k}$

Las siguientes figuras representan los números de Narayana , ilustrando las simetrías mencionadas anteriormente. ${\displaystyle \operatorname {N} (4,k)}$

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

Árboles enraizados

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

El número de árboles enraizados ordenados sin etiquetar con aristas y hojas es igual a . ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \operatorname {N} (n,k)}$

Esto es análogo a los ejemplos anteriores:

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

• En las figuras anteriores de caminos reticulares, cada arista ascendente desde la línea horizontal a la altura ⁠ ⁠ ${\displaystyle y}$ hasta ⁠ ⁠ ${\displaystyle y}$⁠ ${\displaystyle +1}$ corresponde a una arista entre el nodo ⁠ ⁠ y su ${\displaystyle y}$ hijo. Un nodo ⁠ ⁠ ${\displaystyle y}$ tiene tantos hijos como aristas ascendentes que parten de la línea horizontal a la altura ⁠ ⁠ ${\displaystyle y}$ . Por ejemplo, en la primera ruta para , los nodos 0 y 1 tendrán dos hijos cada uno; en la última (sexta) ruta, el nodo 0 tendrá tres hijos y el nodo 1 tendrá un hijo. Para construir un árbol enraizado a partir de un camino reticular y viceversa, podemos emplear un algoritmo similar al mencionado en el párrafo anterior. Al igual que con las palabras de Dyck, existe un isomorfismo entre los caminos reticulares y los árboles enraizados. ${\displaystyle \operatorname {N} (4,3)}$

Particiones

Particiones no cruzadas 1,6,6,1 con bloques 1,2,3,4 de un conjunto de 4 elementos

En el estudio de particiones, vemos que en un conjunto que contiene elementos , ${\displaystyle n}$ podemos particionar ese conjunto de diferentes maneras, donde es el ⁠ ⁠ ^ésimo número de Bell . Además, el número de formas de particionar un conjunto en exactamente ⁠ ⁠ bloques usamos los números de Stirling . Ambos conceptos están un poco fuera de tema, pero son una base necesaria para comprender el uso de los números de Narayana. En ambas nociones anteriores se explican las particiones cruzadas. ${\displaystyle B_{n}}$ ${\displaystyle B_{n}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle S(n,k)}$

Para rechazar las particiones cruzadas y contar solo las particiones no cruzadas , podemos usar los números Catalan para contar las particiones no cruzadas de todos los elementos ${\displaystyle n}$ del conjunto, . Para contar las particiones no cruzadas en las que el conjunto está dividido exactamente en bloques , usamos el número Narayana . ${\displaystyle C_{n}}$ ${\displaystyle k}$ ${\displaystyle \operatorname {N} (n,k)}$

Función generadora

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

${\displaystyle \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úmero catalán
• Número de Delannoy
• Número de Motzkin
• Polinomios de Narayana
• Número de Schröder
• Triángulo de Pascal
• Materiales de aprendizaje relacionados con Particiones relacionadas con triángulos numéricos en Wikiversidad

Citas

1. Petersen 2015, pág. 25.

Referencias

• PA MacMahon (1915–1916). Análisis combinatorio . Cambridge University Press.
• Petersen, T. Kyle (2015). "Números de Narayana" (PDF) . Números Eulerianos . Birkhäuser Textos avanzados Basler Lehrbücher. Basilea: Birkhäuser. doi :10.1007/978-1-4939-3091-3. ISBN 978-1-4939-3090-6.