En combinatoria , los números de Narayana Forman una matriz 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).
Lleva el nombre de | Tadepalli Venkata Narayana |
---|---|
No. de términos conocidos | infinito |
Fórmula | |
Índice OEIS |
|
Fórmula
Los números de Narayana se pueden expresar en términos de coeficientes binomiales :
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
Interpretaciones combinatorias
Palabras de Dyck
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 (conocidas como palabras Dyck ) y que contienennidos distintos. Por ejemplo,, ya que con cuatro pares de paréntesis, se pueden crear seis secuencias, cada una de las cuales contiene dos apariciones del subpatrón ()
:
(() (())) ((() ())) ((()) ())() ((())) (()) (()) ((())) ()
De este ejemplo debería ser obvio que , ya que la única forma de obtener un único subpatrón ()
es tener todos los paréntesis de apertura en el primerposiciones, seguidas de todos los paréntesis de cierre. También, como los distintos anidamientos sólo pueden lograrse 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 catalanes :
Caminos de celosía monótonos
Los números de Narayana también cuentan el número de caminos de celosía desde a , con escalones solo al noreste y sureste, sin desviarse por debajo del eje x , con picos.
Las siguientes figuras representan los números de Narayana , ilustrando las simetrías mencionadas anteriormente.
Rutas | |
---|---|
N (4, 1) = 1 ruta 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: |
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 trayectos monótonos a lo largo de los bordes de un cuadrícula que no pasa por encima de la diagonal.
Árboles enraizados
El número de árboles enraizados ordenados sin etiquetar con bordes y hojas es igual a .
Esto es análogo a los ejemplos anteriores:
- Cada palabra de 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.
- En las figuras anteriores de caminos de celosía, cada borde hacia arriba desde la línea horizontal en altura a corresponde a un borde entre el nodo y su hijo. Un nodo tiene tantos hijos, ya que hay bordes ascendentes que parten de la línea horizontal en altura . 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 una ruta de celosía 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 de celosía y los árboles enraizados.
Particiones
En el estudio de las particiones, vemos que en un conjunto que contiene elementos, podemos particionar que se establece en diferentes formas, donde es el º número de Bell . Además, la cantidad de formas de dividir un conjunto en exactamentebloques 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 Narayana. En ambos de los dos conceptos anteriores se tienen en cuenta las particiones que se cruzan.
Para rechazar las particiones que cruzan y contar solo las particiones que no cruzan , podemos usar los números catalanes para contar las particiones que no cruzan de todos elementos del conjunto, . Para contar las particiones que no se cruzan en las que el conjunto está dividido exactamente bloques, usamos el número de Narayana .
Función generadora
La función generadora de los números de Narayana es [1]
Ver también
- Número catalán
- Número de Delannoy
- Número de Motzkin
- Número de Schröder
- Triángulo de Pascal
- Materiales de aprendizaje relacionados con triángulos numéricos relacionados con particiones en Wikiversity
Citas
Referencias
- PA MacMahon (1915-1916). Análisis combinatorio . Prensa de la Universidad de Cambridge.
- 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.