Camino de celosía

Secuencia de vectores de extremo a extremo a través de puntos de una red

Trayectoria reticular de longitud 5 en ℤ ² con S = { (2,0), (1,1), (0,-1) }.

En combinatoria , un camino reticular L en el entramado entero d -dimensional de longitud k con pasos en el conjunto S , es una secuencia de vectores tales que cada diferencia consecutiva se encuentra en S. ^[1] Un camino reticular puede encontrarse en cualquier entramado en , [ ^1] pero el entramado entero es el más comúnmente utilizado. ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle v_{0},v_{1},\ldots ,v_{k}\in \mathbb {Z} ^{d}}$ ${\displaystyle v_{i}-v_{i-1}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \mathbb {Z} ^{d}}$

Un ejemplo de un camino reticular en ⁠ ⁠ ${\displaystyle \mathbb {Z} ^{2}}$ de longitud 5 con pasos en es . ${\displaystyle S=\lbrace (2,0),(1,1),(0,-1)\rbrace }$ ${\displaystyle L=\lbrace (-1,-2),(0,-1),(2,-1),(2,-2),(2,-3),(4,-3)\rbrace }$

Caminos reticulares del noreste

Un camino reticular del noreste (NE) es un camino reticular con escalones en . Los escalones se denominan escalones del norte y se indican con 's; los escalones se denominan escalones del este y se indican con 's. ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle S=\lbrace (0,1),(1,0)\rbrace }$ ${\displaystyle (0,1)}$ ${\displaystyle N}$ ${\displaystyle (1,0)}$ ${\displaystyle E}$

Los caminos de red NE suelen comenzar en el origen. Esta convención nos permite codificar toda la información sobre un camino de red NE en una sola palabra de permutación . La longitud de la palabra nos da el número de pasos del camino de red, . El orden de los y comunica la secuencia de . Además, el número de y el número de en la palabra determina el punto final de . ${\displaystyle L}$ ${\displaystyle k}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle L}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle L}$

Si la palabra de permutación para una ruta reticular NE contiene pasos y pasos, y si la ruta comienza en el origen, entonces la ruta necesariamente termina en . Esto se deduce porque has "caminado" exactamente pasos al norte y pasos al este desde . ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle e}$ ${\displaystyle E}$ ${\displaystyle (e,n)}$ ${\displaystyle n}$ ${\displaystyle e}$ ${\displaystyle (0,0)}$

Caminos reticulares NE que comienzan con exactamente uno y tres . El punto final está necesariamente en . ${\displaystyle (0,0)}$ ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle (3,1)}$

Contando caminos en red

Los caminos de celosía se utilizan a menudo para contar otros objetos combinatorios. De manera similar, hay muchos objetos combinatorios que cuentan la cantidad de caminos de celosía de un tipo determinado. Esto ocurre cuando los caminos de celosía están en biyección con el objeto en cuestión. Por ejemplo,

• Los caminos de Dyck se cuentan con el número Catalan . Un camino de Dyck es un camino reticular de a con pasos de a que nunca pasa por debajo del eje . ^[2] De manera equivalente, un camino de Dyck es un camino reticular NE de a que se encuentra estrictamente debajo (pero puede tocar) la diagonal . ^{[2] [3]} ${\displaystyle n^{\text{th}}}$ ${\displaystyle C_{n}}$ ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle (0,0)}$ ${\displaystyle (2n,0)}$ ${\displaystyle S=\lbrace (1,1),(1,-1)\rbrace }$ ${\displaystyle x}$ ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle y=x}$
• Los números de Schröder cuentan el número de caminos reticulares desde hasta con pasos hacia adentro y hacia afuera que nunca se elevan por encima de la diagonal . ^[2] ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle (1,0),(0,1)}$ ${\displaystyle (1,1)}$ ${\displaystyle y=x}$
• El número de rutas de red NE de a cuenta la cantidad de combinaciones de objetos de un conjunto de objetos. ${\displaystyle (0,0)}$ ${\displaystyle (a,b)}$ ${\displaystyle a}$ ${\displaystyle a+b}$

Combinaciones y caminos reticulares NE

Los caminos reticulares NE tienen estrechas conexiones con el número de combinaciones , que se cuentan mediante el coeficiente binomial y se organizan en el triángulo de Pascal . El diagrama siguiente muestra algunas de estas conexiones.

El número de caminos reticulares desde hasta es igual a . ${\displaystyle (0,0)}$ ${\displaystyle (2,3)}$ ${\displaystyle {\binom {2+3}{2}}={\binom {5}{2}}=10}$

El número de caminos reticulares desde hasta es igual al coeficiente binomial . El diagrama lo muestra para . Si uno gira el diagrama 135° en el sentido de las agujas del reloj sobre el origen y lo extiende para incluir todos los , se obtiene el triángulo de Pascal. Este resultado no es ninguna sorpresa, porque la entrada de la fila del Triángulo de Pascal es el coeficiente binomial . ${\displaystyle (0,0)}$ ${\displaystyle (n,k)}$ ${\displaystyle {\binom {n+k}{n}}}$ ${\displaystyle 0\leq k\leq n=4}$ ${\displaystyle n,k\in \mathbb {N} \cup \lbrace 0\rbrace }$ ${\displaystyle k^{\text{th}}}$ ${\displaystyle n^{\text{th}}}$ ${\displaystyle {\binom {n}{k}}}$

Problemas y pruebas

La representación gráfica de los caminos reticulares NE se presta a muchas demostraciones biyectivas que involucran combinaciones. A continuación se presentan algunos ejemplos.

• ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}}$.

Demostración : El lado derecho es igual al número de caminos reticulares NE desde hasta . Cada uno de estos caminos reticulares NE interseca exactamente uno de los puntos reticulares en la matriz rectangular con coordenadas para . Esto se muestra en la figura siguiente para : Cada camino reticular NE desde hasta interseca exactamente uno de los nodos coloreados. ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle (x,n-x)}$ ${\displaystyle x\in \lbrace 0,1,\ldots ,n\rbrace }$ ${\displaystyle n=4}$ ${\displaystyle (0,0)}$ ${\displaystyle (4,4)}$

Cada ruta de red NE pasa exactamente por un nodo de color.

En el lado izquierdo, el coeficiente binomial al cuadrado, , representa dos copias del conjunto de rutas de red NE desde el punto final adjunto hasta el punto de inicio. Gire la segunda copia 90° en el sentido de las agujas del reloj. Esto no cambia la combinatoria del objeto: . Por lo tanto, el número total de rutas de red permanece igual. ${\displaystyle {\binom {n}{k}}^{2}}$ ${\displaystyle (0,0)}$ ${\displaystyle (k,n-k)}$ ${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$

Conjuntos de trayectorias reticulares NE al cuadrado, con la segunda copia rotada 90° en el sentido de las agujas del reloj.

Superpongamos los caminos reticulares NE al cuadrado sobre la misma matriz rectangular, como se ve en la figura siguiente. Vemos que se tienen en cuenta todos los caminos reticulares NE desde hasta . En particular, observemos que cualquier camino reticular que pase por el punto reticular rojo (por ejemplo) se cuenta según el conjunto al cuadrado de caminos reticulares (que también se muestra en rojo). ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$ ${\displaystyle \Box }$

Conjuntos superpuestos de trayectorias reticulares NE elevadas al cuadrado. Se tienen en cuenta todas las trayectorias reticulares NE.

Véase también

• Tadepalli Venkata Narayana

Referencias

1. Stanley, Richard (2012). Combinatoria enumerativa, volumen 1 (2.ª edición). Cambridge University Press. pág. 21. ISBN 978-1-107-60262-5.
2. Stanley, Richard (2001). Combinatoria enumerativa, volumen 2. Cambridge University Press. págs. 173, 239. ISBN 978-0-521-78987-5.
3. "Wolfram MathWorld" . Consultado el 6 de marzo de 2014 .

^[1]

1. Song, Chunwei. Combinatoria de caminos en red y secuencias de conteo especiales: desde una perspectiva enumerativa (1.ª ed.). Boca Raton: CRC Press. ISBN 978-1032671758.