Número de rutas de taxi en una ciudad triangular

Question

Estoy suponiendo un triángulo que es "casi" la mitad de una ciudad rectangular con geometría de taxis. Estoy tratando de encontrar el número de caminos en esta ciudad triangular.

Asumiendo que el paseo comienza desde la esquina de la ciudad. Si nos movemos p pasos en una dirección, y q pasos en la dirección perpendicular, el número de caminos en caso de una ciudad rectangular es conocido y viene dado por:

$$\binom{p+q}{p} ~ or ~ \binom{p+q}{q}$$

Por ejemplo, supongamos la ciudad girada 45 grados de la siguiente figura (izquierda).

Ciudades completas y medias

Si partimos del punto al que apunta la flecha, los números de los puntos de cruce se refieren al número de caminos posibles desde el punto inicial hasta cada punto de cruce.

Ahora, supongamos la figura de la derecha. De nuevo, los números en los puntos de cruce se refieren al número de caminos posibles desde el punto inicial hasta cada punto de cruce. He obtenido estos números mediante una combinación de recuento y observación.

La principal observación es que el número de caminos en la ciudad triangular es una proporción de la ciudad rectangular. Tomemos por ejemplo la fila 7, encontramos lo siguiente (¿Puede explicar por qué?):

924/(7/1)=132

462/(7/2)=132

210/(7/3)=90

84/(7/4)=48

28/(7/5)=20

7/(7/6)=6

1/(7/7)=1

Esto se aplica a todas las filas.

Ahora a mi pregunta. Supongamos la siguiente forma de una ciudad, donde las entradas están en el borde izquierdo, y las salidas están en el borde inferior.

Mi problema

Lo que quiero hacer es encontrar el número de caminos desde cualquiera de las entradas a cualquiera de las salidas. Espero que una fórmula, y una prueba.

En la figura 2 está lo que he conseguido hasta ahora. Si la salida es menor o igual que la entrada, se puede obtener directamente utilizando la fórmula para el caso rectangular.

Suponiendo que esto sea correcto, observa que hasta la diagonal, los números siguen las reglas del triángulo de Pascal. Después de la diagonal, que representa el límite de la ciudad, no sigue las mismas reglas, pero hay un patrón.

1ª diagonal después de la mitad (restar 1)

6= (6+1)-1

20=(6+15)-1

34=(15+20)-1

2º (restar 6)

20=(20+6)-6

48=(20+34)-6

62=(34+34)-6

3ª (restar 20)

4º (resta 48)

5º (restar 90)

6º (resta 132)

Cuáles son los números de la fila correspondiente a la entrada 7 (de nuevo, ¿puede explicar por qué?).

Answer 1

La secuencia $1,6,20,48,90,132,132$ se puede generar como $\displaystyle {5+i \choose i-1}\dfrac{8-i}{7}$ con $i$ corriendo de $1$ a $7$ aunque sería un poco más convencional escribir $\displaystyle {n+k \choose k}\dfrac{n-k+1}{n+1}$ con $n=6$ y $k$ corriendo de $0$ a $6$ .

La parte derecha del primer diagrama se conoce como Triángulo de Cataluña con la secuencia $1,1,2,5,14,42,132,\ldots$ siendo conocido como Números catalanes : aparecen con frecuencia en matemáticas.

Answer 2

Imagina que conectas las "entradas" a la izquierda de tu ciudad y las "salidas" al fondo, así (se muestra para 4 de cada en lugar de 7 de cada):

*
|
+-->:
|   ::.
+-->::::
|   :::::. <- dotted area corresponds to your drawing
+-->:::::::
|   ::::::::.
+-->::::::::::
    v  v  v  v
    |  |  |  |
    +--+--+--+--*

A continuación, cada ruta de algunos entrada a algunos corresponde a una ruta de * a * en el gráfico ampliado. Pero el gráfico expandido no es más que una "media ciudad" de tamaño 2 más que con la que se empezó, salvo que se elimina la intersección inferior izquierda.

Así que el número de soluciones es uno menos que el número de arriba a abajo en una "media ciudad" de tamaño $n+2$ .

El número de caminos a través de una "media ciudad" de tamaño $n$ es el $n$ th Número catalán -- lo que estás contando es el número de cadenas de $n$ "izquierda" y $n$ "derechos" de tal manera que ningún prefijo contenga más derechos que izquierdos.