En combinatoria , un camino de celosía en de longitud con pasos en es una secuencia tal que cada diferencia consecutiva yace en . [1] Un camino de celosía puede encontrarse en cualquier celosía en, [1] pero el entramado de números enteros es el más utilizado.
Un ejemplo de un camino de celosía en de longitud 5 con escalones en es .
Caminos de celosía noreste
Una ruta de celosía del noreste (NE) es una ruta de celosía en con pasos en . La los pasos se denominan pasos norte y se indican con 's; la Los pasos se denominan pasos Este y se indican con 's.
Los caminos de celosía NE suelen comenzar en el origen. Esta convención nos permite codificar toda la información sobre una ruta de celosía NEen una sola palabra de permutación . La longitud de la palabra nos da el número de pasos del camino de celosía,. El orden del'arena comunica la secuencia de . Además, el número dey el número de 's en la palabra determina el punto final de .
Si la palabra de permutación para una ruta de celosía NE contiene pasos y pasos, y si el camino comienza en el origen, entonces el camino necesariamente termina en . Esto sigue porque has "caminado" exactamente pasos hacia el norte y pasos al este de .
Contando caminos de celosía
Las rutas de celosía se utilizan a menudo para contar otros objetos combinatorios. De manera similar, hay muchos objetos combinatorios que cuentan el número de caminos de celosía de cierto tipo. Esto ocurre cuando las rutas de celosía están en biyección con el objeto en cuestión. Por ejemplo,
- Los caminos de Dyck son contados por Número catalán . Un camino de Dyck es un camino de celosía en de a con pasos en que nunca pasa por debajo del -eje. [2] De manera equivalente, una ruta Dyck es una ruta reticular NE desde a que se encuentra estrictamente debajo (pero puede tocar) la diagonal . [2] [3]
- Los números de Schröder cuentan el número de caminos de celosía desde a con pasos en y que nunca se elevan por encima de la diagonal . [2]
- El número de caminos de celosía NE desde a cuenta el número de combinaciones de objetos de un conjunto de objetos.
Combinaciones y caminos de celosía NE
Las rutas de celosía NE tienen conexiones cercanas con el número de combinaciones , que se cuentan por 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 de celosía de a es igual al coeficiente binomial . El diagrama muestra esto para. Si se gira el diagrama 135 ° en el sentido de las agujas del reloj sobre el origen y se extiende para incluir todos, se obtiene el triángulo de Pascal. Este resultado no es ninguna sorpresa, porque el entrada de la fila del triángulo de Pascal es el coeficiente binomial .
Problemas y pruebas
La representación gráfica de las rutas de celosía NE se presta a muchas pruebas biyectivas que involucran combinaciones. Aquí están algunos ejemplos.
- .
Prueba : El lado derecho es igual al número de caminos de celosía NE desde a . Cada una de estas rutas de celosía NE interseca exactamente uno de los puntos de celosía en la matriz rectangular con coordenadas por . Esto se muestra en la figura siguiente para: Cada camino de celosía NE desde a intersecta exactamente uno de los nodos coloreados.
En el lado izquierdo, el coeficiente binomial al cuadrado,, representa dos copias del conjunto de rutas de celosía NE de a punto final adjunto al punto de inicio. Gire la segunda copia 90 ° en el sentido de las agujas del reloj. Esto no cambia la combinatoria del objeto:. Entonces, el número total de caminos de celosía sigue siendo el mismo.
Superponga las rutas de celosía NE cuadradas en la misma matriz rectangular, como se ve en la figura siguiente. Vemos que todos los caminos de celosía NE de a se contabilizan. En particular, observe que cualquier camino de celosía que pase a través del punto de celosía rojo (por ejemplo) se cuenta mediante el conjunto de caminos de celosía al cuadrado (también mostrado en rojo).
Referencias
- ↑ a b Stanley, Richard (2012). Combinatoria enumerativa, Volumen 1 (2 ed.). Prensa de la Universidad de Cambridge. pag. 21. ISBN 978-1-107-60262-5.
- ^ a b c Stanley, Richard (2001). Combinatoria enumerativa, volumen 2 . Prensa de la Universidad de Cambridge. págs. 173, 239. ISBN 978-0-521-78987-5.
- ^ "Wolfram MathWorld" . Consultado el 6 de marzo de 2014 .